Red de flujo - Flow network

En la teoría de grafos , una red de flujo (también conocida como red de transporte ) es un gráfico dirigido donde cada borde tiene una capacidad y cada borde recibe un flujo. La cantidad de flujo en un borde no puede exceder la capacidad del borde. A menudo, en la investigación de operaciones , un grafo dirigido se denomina red , los vértices se denominan nodos y los bordes se denominan arcos . Un flujo debe satisfacer la restricción de que la cantidad de flujo en un nodo es igual a la cantidad de flujo que sale de él, a menos que sea una fuente , que solo tiene flujo de salida, o un sumidero , que solo tiene flujo de entrada. Una red se puede utilizar para modelar el tráfico en una red informática, circulación con demandas, fluidos en tuberías, corrientes en un circuito eléctrico o cualquier cosa similar en la que algo viaje a través de una red de nodos.

Definición

Una red es un gráfico $G = (V, E)$ , donde $V$ es un conjunto de vértices y $E$ es un conjunto de $V$ bordes 's - un subconjunto de $V \times V$ - junto con un no negativo función ${\ Displaystyle \ mathbb {R}}$ , llamada función de capacidad . Sin pérdida de generalidad , podemos suponer que si $(u, v) \in E$ entonces $(v, u)$ también es miembro de $E$ , ya que si $(v, u) \notin E$ entonces podemos sumar $(v, u)$ a E y luego establezca $c (v, u) = 0$ .

Si se distinguen dos nodos en $G$ , una fuente $sy$ un sumidero $t$ , entonces $(G, c, s, t)$ se llama red de flujo .

Flujos

Hay varias nociones de función de flujo que se pueden definir en un diagrama de flujo. Las funciones de flujo modelan el flujo neto de unidades entre pares de nodos y son útiles cuando se hacen preguntas como ¿cuál es el número máximo de unidades que se pueden transferir desde el nodo fuente s al nodo receptor t? El ejemplo más simple de una función de flujo se conoce como pseudo-flujo.

Un pseudo-flujo es una función

{\ Displaystyle \ mathbb {R}}

que satisface las siguientes dos restricciones para todos los nodos

u

y

v

:

Simetría sesgada : codifique solo el flujo neto de unidades entre un par de nodos $u$ y $v$ (consulte la intuición a continuación), es decir: $f (u, v) = - f (v, u)$ .
Restricción de capacidad : el flujo de un arco no puede exceder su capacidad, es decir: $f (u, v) \leq c (u, v)$ .

Dado un pseudo-flujo $f$ en una red de flujo, a menudo es útil considerar el flujo neto que ingresa a un nodo $u$ dado , es decir, la suma de los flujos que ingresan a $u$ . La función de exceso ${\ Displaystyle \ mathbb {R}}$ está definida por $x f (u) = Σ v \in V f (v, u)$ . Se dice que un nodo $u$ está activo si $x f (u)> 0$ , deficiente si $x f (u) <0$ o conservador si $x f (u) = 0$ .

Estas definiciones finales conducen a dos refuerzos de la definición de pseudo-flujo:

Un preflujo es un pseudoflujo que, para todo

v ∈ V \ { s

}, satisface la restricción adicional:

Flujos no deficientes : El flujo neto que ingresa al nodo $v$ no es negativo, excepto para la fuente, que "produce" flujo. Es decir: $x f (v) \geq 0$ para todo $v ∈ V \ { s$ }.

Un flujo factible , o simplemente un flujo , es un pseudo-flujo que, para todo

v ∈ V \ { s , t

}, satisface la restricción adicional:

Conservación del flujo : El flujo neto que ingresa al nodo $v$ es 0, excepto para la fuente, que "produce" flujo, y el sumidero, que "consume" flujo. Es decir: $x f (v) = 0$ para todo $v ∈ V \ { s , t$ }.

El valor de un flujo factible $f$ , denotado $| f |$ , es el flujo neto hacia el sumidero $t$ de la red de flujo. Es decir, $| f | = x f (t)$ .

Intuición

En el contexto del análisis de flujo, solo hay interés en considerar cómo se transfieren las unidades entre nodos en un sentido holístico. Dicho de otra manera, no es necesario distinguir varios arcos entre un par de nodos:

Dados cualesquiera dos nodos $u$ y $v$ , si hay dos arcos de $u$ a $v$ con capacidades $5$ y $3$ respectivamente, esto equivale a considerar solo un arco único entre $u$ y $v$ con capacidad $8$ ; solo es útil saber que $8$ unidades se pueden transferir de $u$ a $v$ , no cómo se pueden transferir.
Nuevamente, dados dos nodos $u$ y $v$ , si hay un flujo de $5$ unidades de $u$ a $v$ , y otro flujo de $3$ unidades de $v$ a $u$ , esto es equivalente a un flujo neto de $2$ unidades de $u$ a $v$ , o un flujo neto de $-2$ unidades de $v$ a $u$ (modo signo indica la dirección) - sólo es útil saber que un flujo neto de $2$ unidades fluirá entre $u$ y $v$ , y la dirección que fluirá, no la forma que el flujo neto se consigue.

Por esta razón, la función de capacidad ${\ Displaystyle \ mathbb {R}}$ , que no permite que varios arcos comiencen y terminen en los mismos nodos, es suficiente para el análisis de flujo. De manera similar, es suficiente imponer la restricción de simetría sesgada en las funciones de flujo para garantizar que el flujo entre dos vértices esté codificado por un solo número (para indicar la magnitud) y un signo (para indicar la dirección), conociendo el flujo entre $u$ y $v.$ implícitamente, a través de la simetría sesgada, conoce el flujo entre $v$ y $u$ . Estas simplificaciones del modelo no siempre son intuitivas de inmediato, pero son convenientes cuando llega el momento de analizar los flujos.

La restricción de capacidad simplemente asegura que un flujo en cualquier arco dentro de la red no puede exceder la capacidad de ese arco.

Conceptos útiles para problemas de flujo

Derechos residuales de autor

La capacidad residual de un arco con respecto a un pseudo-flujo $f$ , denotado $c f$ , es la diferencia entre la capacidad del arco y su flujo. Es decir, $c f (e) = c (e) - f (e)$ . A partir de esto, podemos construir una red residual , denominada $G f (V, E f)$ , que modela la cantidad de capacidad disponible en el conjunto de arcos en $G = (V, E)$ . Más formalmente, dada una red de flujo $G$ , la red residual $G f$ tiene el conjunto de nodos $V$ , el conjunto de arcos $E f = {e \in V \times V : c f (e)> 0}$ y la función de capacidad $c f$ .

Este concepto se utiliza en el algoritmo de Ford-Fulkerson que calcula el flujo máximo en una red de flujo.

Tenga en cuenta que puede haber una ruta de $u$ a $v$ en la red residual, aunque no haya una ruta de $u$ a $v$ en la red original. Dado que los flujos en direcciones opuestas se cancelan, disminuir el flujo de $v$ a $u$ es lo mismo que aumentar el flujo de $u$ a $v$ .

Aumento de caminos

Una ruta de aumento es una ruta $(u 1, u 2, ..., u k)$ en la red residual, donde $u 1 = s$ , $u k = t$ , y $c f (u i, u i + 1)> 0$ . Una red está en flujo máximo si y solo si no hay una ruta de aumento en la red residual $G f$ .

Varias fuentes y / o sumideros

A veces, al modelar una red con más de una fuente, se introduce una superfuente en el gráfico. Consiste en un vértice conectado a cada una de las fuentes con aristas de capacidad infinita, para actuar como una fuente global. Una construcción similar para los lavabos se llama superdisipador .

Ejemplo

Una red de flujo que muestra el flujo y la capacidad.

A la izquierda, verá una red de flujo con la fuente etiquetada como $s$ , sumidero $t$ y cuatro nodos adicionales. Se indica el flujo y la capacidad . Observe cómo la red mantiene la simetría sesgada, las limitaciones de capacidad y la conservación del flujo. La cantidad total de flujo de $s$ a $t$ es 5, que se puede ver fácilmente desde el hecho de que el flujo saliente total a partir de $s$ es 5, que es también el flujo de entrada a $t$ . Sabemos que ningún flujo aparece ni desaparece en ninguno de los otros nodos. ${\ Displaystyle f / c}$

Red residual para la red de flujo anterior, mostrando capacidades residuales.

A continuación, verá la red residual para el flujo dado. Observe cómo hay capacidad residual positiva en algunos bordes donde la capacidad original es cero, por ejemplo, para el borde . Este flujo no es un flujo máximo . Hay capacidad disponible a lo largo de los caminos , y cuáles son los caminos en aumento. La capacidad residual del primer camino es . Observe que mientras exista algún camino con una capacidad residual positiva, el flujo no será máximo. La capacidad residual para algún camino es la capacidad residual mínima de todos los bordes en ese camino. ${\ Displaystyle (d, c)}$ ${\ Displaystyle (s, a, c, t)}$ ${\ Displaystyle (s, a, b, d, t)}$ ${\ Displaystyle (s, a, b, d, c, t)}$ ${\ Displaystyle \ min (c (s, a) -f (s, a), c (a, c) -f (a, c), c (c, t) -f (c, t))}$ ${\ Displaystyle = \ min (5-3,3-2,2-1) = \ min (2,1,1) = 1}$

Aplicaciones

Imagínese una serie de tuberías de agua que encajan en una red. Cada tubería tiene un diámetro determinado, por lo que solo puede mantener un flujo de una determinada cantidad de agua. En cualquier lugar donde se unan las tuberías, la cantidad total de agua que ingresa a esa unión debe ser igual a la cantidad que sale, de lo contrario nos quedaríamos sin agua rápidamente o tendríamos una acumulación de agua. Tenemos una entrada de agua, que es la fuente, y una salida, el fregadero. Entonces, un flujo sería una forma posible de que el agua pase de la fuente al sumidero para que la cantidad total de agua que sale de la salida sea constante. Intuitivamente, el caudal total de una red es la velocidad a la que sale el agua por la salida.

Los flujos pueden pertenecer a personas o materiales a través de redes de transporte, o electricidad a través de sistemas de distribución eléctrica . Para cualquier red física de este tipo, el flujo que ingresa a cualquier nodo intermedio debe ser igual al flujo que sale de ese nodo. Esta restricción de conservación es equivalente a la ley actual de Kirchhoff .

Las redes de flujo también encuentran aplicaciones en ecología : las redes de flujo surgen naturalmente cuando se considera el flujo de nutrientes y energía entre diferentes organismos en una red alimentaria . Los problemas matemáticos asociados con tales redes son bastante diferentes de los que surgen en las redes de flujo fluido o de tráfico. El campo del análisis de redes de ecosistemas, desarrollado por Robert Ulanowicz y otros, implica el uso de conceptos de la teoría de la información y la termodinámica para estudiar la evolución de estas redes a lo largo del tiempo.

Clasificación de problemas de flujo

El problema más simple y común al usar redes de flujo es encontrar lo que se llama flujo máximo , que proporciona el flujo total más grande posible desde la fuente hasta el sumidero en un gráfico dado. Hay muchos otros problemas que pueden resolverse utilizando algoritmos de flujo máximo, si se modelan adecuadamente como redes de flujo, como el emparejamiento bipartito , el problema de asignación y el problema de transporte . Los problemas de flujo máximo se pueden resolver de manera eficiente con el algoritmo de empujar y volver a etiquetar . El teorema de flujo máximo y corte mínimo establece que encontrar un flujo de red máximo es equivalente a encontrar un corte de capacidad mínima que separe la fuente y el sumidero, donde un corte es la división de vértices de manera que la fuente está en una división y el el fregadero está en otro.

Algoritmos conocidos para el problema de flujo máximo
Inventor (es)	Año	Complejidad temporal (con $n$ nodos y $m$ arcos)
Algoritmo de Dinic	1969	$O (mn 2)$
Algoritmo de Edmonds-Karp	1972	$O (m 2 n)$
MPM (Malhotra, Pramodh-Kumar, y Maheshwari) algoritmo	1978	$O (n 3)$
James B. Orlin	2013	$O (mn)$

En un problema de flujo de múltiples productos básicos , tiene múltiples fuentes y sumideros, y varios "productos básicos" que deben fluir desde una fuente determinada a un sumidero determinado. Esto podría ser, por ejemplo, varios productos que se producen en varias fábricas y que se entregarán a varios clientes determinados a través de la misma red de transporte.

En un problema de flujo de costo mínimo , cada borde tiene un costo determinado y el costo de enviar el flujo a través del borde es . El objetivo es enviar una determinada cantidad de flujo desde la fuente hasta el sumidero, al precio más bajo posible. ${\ Displaystyle u, v}$ ${\ Displaystyle k (u, v)}$ ${\ Displaystyle f (u, v)}$ ${\ Displaystyle f (u, v) \ cdot k (u, v)}$

En un problema de circulación , tiene un límite inferior en los bordes, además del límite superior . Cada borde también tiene un costo. A menudo, la conservación del flujo se mantiene para todos los nodos en un problema de circulación y existe una conexión desde el sumidero hasta la fuente. De esta forma, puede dictar el caudal total con y . El flujo circula por la red, de ahí el nombre del problema. ${\ Displaystyle \ ell (u, v)}$ ${\ Displaystyle c (u, v)}$ ${\ Displaystyle \ ell (t, s)}$ ${\ Displaystyle c (t, s)}$

En una red con ganancias o red generalizada, cada borde tiene una ganancia , un número real (no cero) tal que, si el borde tiene ganancia g , y una cantidad x fluye hacia el borde en su cola, entonces una cantidad gx fluye hacia afuera en la cabeza.

En un problema de localización de fuentes , un algoritmo intenta identificar el nodo fuente más probable de difusión de información a través de una red parcialmente observada. Esto se puede hacer en tiempo lineal para árboles y tiempo cúbico para redes arbitrarias y tiene aplicaciones que van desde el seguimiento de los usuarios de teléfonos móviles hasta la identificación de la fuente de origen de los brotes de enfermedades.

Ver también

Referencias

Otras lecturas

George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 8: Algoritmos de flujo de red". Algoritmos en pocas palabras . Oreilly Media . págs. 226–250. ISBN 978-0-596-51624-6.
Ravindra K. Ahuja , Thomas L. Magnanti y James B. Orlin (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.CS1 maint: varios nombres: lista de autores ( enlace )
Bollobás, Béla (1979). Teoría de grafos: un curso introductorio . Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary y Oellermann, Ortrud R. (1993). Teoría de grafos aplicada y algorítmica . Nueva York: McGraw-Hill. ISBN 0-07-557101-3.CS1 maint: varios nombres: lista de autores ( enlace )
Incluso, Shimon (1979). Algoritmos gráficos . Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8.
Gibbons, Alan (1985). Teoría algorítmica de grafos . Cambridge: Cambridge University Press. ISBN 0-521-28881-9.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001) [1990]. "26". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 696–697. ISBN 0-262-03293-7.CS1 maint: varios nombres: lista de autores ( enlace )

enlaces externos

Problema de flujo máximo
Instancias de grafos reales
Biblioteca Lemon C ++ con varios algoritmos de circulación de flujo máximo y costo mínimo
QuickGraph , estructuras de datos gráficos y algoritmos para .Net

Languages

In other projects