Red de flujo

En teoría de grafos , una red de flujo (también conocida como red de transporte ) es un grafo dirigido donde cada arista tiene una capacidad y recibe un flujo. La cantidad de flujo en una arista no puede exceder su capacidad. A menudo, en investigación operativa , un grafo dirigido se denomina red , los vértices se llaman nodos y las aristas, arcos . Un flujo debe cumplir la restricción de que la cantidad de flujo que entra en un nodo es igual a la cantidad de flujo que sale de él, a menos que sea una fuente , que solo tiene flujo saliente, o un sumidero , que solo tiene flujo entrante. Una red de flujo se puede utilizar para modelar el tráfico en una red informática, la circulación con demandas, los fluidos en tuberías, las corrientes en un circuito eléctrico o cualquier situación similar en la que algo se desplace a través de una red de nodos. Por lo tanto, los algoritmos eficientes para resolver flujos de red también se pueden aplicar para resolver problemas que se pueden reducir a una red de flujo, como el diseño de encuestas, la programación de vuelos, la segmentación de imágenes y el problema de correspondencia .

Definición

Una red es un grafo dirigido $G = (V, E) con una$ función de capacidad no negativa $c$ para cada arista, y sin arcos múltiples (es decir, aristas con los mismos nodos de origen y destino). Sin pérdida de generalidad , podemos asumir que si $($ $u$ $,$ $v$ $) \in$ $E$ , entonces $($ $v$ $,$ $u$ $)$ también es un miembro de $E$ . Además, si $($ $v$ $,$ $u$ $) \notin$ $E$ entonces podemos agregar $($ $v$ $,$ $u$ $)$ a $E$ y luego establecer $c$ $($ $v$ $,$ $u$ $) = 0$ .

Si se distinguen dos nodos en $G$ –uno como la fuente $s$ y el otro como el sumidero $t-$ entonces $(G, c, s, t)$ se denomina red de flujo . ^{[ 1 ]}

Flujos

Las funciones de flujo modelan el flujo neto de unidades entre pares de nodos y son útiles para plantear preguntas como: ¿cuál es el número máximo de unidades que se pueden transferir del nodo de origen s al nodo de destino t? El flujo entre dos nodos se utiliza para representar la cantidad neta de unidades que se transfieren de un nodo a otro.

La función de exceso $x f : V \to ℝ$ representa el flujo neto que entra en un nodo $u$ dado (es decir, la suma de los flujos que entran en $u$ ) y se define por $x_{f}(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).$ Se dice que un nodo $u está$ activo si $x f (u) > 0$ (es decir, el nodo $u$ consume flujo), deficiente si $x f (u) < 0$ (es decir, el nodo $u$ produce flujo) o conservador si $x f (u) = 0.$ En las redes de flujo, la fuente $s$ es deficiente y el sumidero $t$ es activo. Los pseudoflujos, los flujos factibles y los preflujos son ejemplos de funciones de flujo.

Un pseudoflujo es una función

f

de cada arista de la red que satisface las dos restricciones siguientes para todos los nodos

u

y

v

:

Restricción de simetría antisimétrica : El flujo en un arco de $u$ a $v$ es equivalente a la negación del flujo en el arco de $v$ a $u$ , es decir: $f (u, v) = - f (v, u)$ . El signo del flujo indica su dirección.
Restricción de capacidad : El flujo de un arco no puede exceder su capacidad, es decir: $f (u, v) \leq c (u, v)$ .

Un preflujo es un pseudoflujo que, para todo

v ∈ V \{ s }

, satisface la restricción adicional:

Flujos no deficientes : El flujo neto que entra al nodo $v$ es no negativo, excepto por 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 pseudoflujo que, para todo

v ∈ V \{ s , t }

, satisface la restricción adicional:

Restricción de conservación del flujo : El flujo neto total que entra en un nodo $v$ es cero para todos los nodos de la red excepto la fuente $s$ y el sumidero $t$ , es decir: $x f (v) = 0$ para todo $v ∈ V \{ s , t }$ . En otras palabras, para todos los nodos de la red excepto la fuente $s$ y el sumidero $t$ , la suma total del flujo entrante de un nodo es igual a su flujo saliente (es decir, $\sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)$ , para cada vértice $v ∈ V \{ s , t }$ ).

El valor $| f |$ de un flujo factible $f$ para una red, es el flujo neto hacia el sumidero $t$ de la red de flujo, es decir: $| f | = x f (t)$ . Nótese que el valor del flujo en una red también es igual al flujo saliente total de la fuente $s$ , es decir: $| f | = - x f (s)$ . Además, si definimos $A$ como un conjunto de nodos en $G$ tal que $s \in A$ y $t \notin A$ , el valor del flujo es igual al flujo neto total que sale de A (es decir $| f | = f out (A) - f in (A)$ ). ^{[ 2 ]} El valor del flujo en una red es la cantidad total de flujo de $s$ a $t$ .

Conceptos útiles para problemas de flujo

Descomposición del flujo

La descomposición de flujo ^{[ 3 ]} es un proceso que divide un flujo dado en un conjunto de flujos de ruta y flujos de ciclo. Todo flujo a través de una red puede descomponerse en una o más rutas y cantidades correspondientes, de modo que cada arista del flujo sea igual a la suma de todas las cantidades de las rutas que la atraviesan. La descomposición de flujo es una herramienta poderosa en problemas de optimización para maximizar o minimizar parámetros de flujo específicos.

Agregar arcos y flujos

No utilizamos múltiples arcos dentro de una red porque podemos combinarlos en un solo arco. Para combinar dos arcos en uno solo, sumamos sus capacidades y sus valores de flujo, y los asignamos al nuevo arco:

Dados dos nodos cualesquiera $u$ y $v$ , tener dos arcos de $u$ a $v$ con capacidades $c 1 (u,v)$ y $c 2 (u,v)$ respectivamente es equivalente a considerar solo un único arco de $u$ a $v$ con una capacidad igual a $c 1 (u,v)+ c 2 (u,v)$ .
Dados dos nodos cualesquiera $u$ y $v$ , tener dos arcos de $u$ a $v$ con pseudoflujos $f 1 (u,v)$ y $f 2 (u,v)$ respectivamente es equivalente a considerar solo un único arco de $u$ a $v$ con un pseudoflujo igual a $f 1 (u,v)+ f 2 (u,v)$ .

Además de las demás restricciones, es necesario tener en cuenta la restricción de simetría antisimétrica durante este paso para mantener la dirección del arco de pseudoflujo original. Agregar flujo a un arco equivale a agregar un arco con capacidad cero.

Derechos residuales de autor

La capacidad residual de un arco $e$ con respecto a un pseudoflujo $f$ se denota $c f$ , y 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 , denotada $G f (V, E f)$ , con una función de capacidad $c f$ que modela la cantidad de capacidad disponible en el conjunto de arcos en $G = (V, E)$ . Más específicamente, la función de capacidad $c f$ de cada arco $(u, v)$ en la red residual representa la cantidad de flujo que se puede transferir de $u$ a $v$ dado el estado actual del flujo dentro de la red.

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

Cabe señalar que puede existir un camino no saturado (un camino con capacidad disponible) de $u$ a $v$ en la red residual, aunque no exista tal camino 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 equivalente a aumentar el flujo de $u$ a $v$ .

Ampliando caminos

Un camino de aumento es un camino $(u 1, u 2, ..., u k)$ en la red residual, donde $u 1 = s$ , $u k = t$ , y $para todo u i, u i + 1 (c f (u i, u i + 1) > 0) (1 \leq i < k)$ . Más simplemente, un camino de aumento es un camino de flujo disponible desde la fuente hasta el sumidero. Una red está en flujo máximo si y solo si no hay ningún camino de aumento en la red residual $G f$ .

El cuello de botella es la capacidad residual mínima de todos los bordes en una ruta de aumento dada. ^{[ 2 ]} Véase el ejemplo explicado en la sección "Ejemplo" de este artículo. La red de flujo está en flujo máximo si y solo si tiene un cuello de botella con un valor igual a cero. Si existe alguna ruta de aumento, su peso de cuello de botella será mayor que 0. En otras palabras, si hay un valor de cuello de botella mayor que 0, entonces hay una ruta de aumento desde la fuente hasta el sumidero. Sin embargo, sabemos que si hay alguna ruta de aumento, entonces la red no está en flujo máximo, lo que a su vez significa que, si hay un valor de cuello de botella mayor que 0, entonces la red no está en flujo máximo.

El término "aumentar el flujo" para una ruta de aumento significa actualizar el flujo $f$ de cada arco en dicha ruta para que sea igual a la capacidad $c$ del cuello de botella. Aumentar el flujo equivale a impulsar flujo adicional a lo largo de la ruta de aumento hasta que no quede capacidad residual disponible en el cuello de botella.

Múltiples fuentes y/o sumideros

En ocasiones, al modelar una red con más de una fuente, se introduce una superfuente en el grafo. ^{[ 4 ]} Esta consiste en un vértice conectado a cada una de las fuentes mediante aristas de capacidad infinita, de modo que actúa como una fuente global. Una construcción similar para sumideros se denomina supersumidero . ^{[ 5 ]}

Ejemplo

En la Figura 1 se observa una red de flujo con una fuente etiquetada como $s$ , un sumidero $t$ y cuatro nodos adicionales. El flujo y la capacidad se denotan $f/c$ Observe cómo la red cumple con la restricción de capacidad y la restricción de conservación del flujo. El flujo total de $s$ a $t$ es 5, lo cual se puede ver fácilmente a partir del hecho de que el flujo saliente total de $s$ es 5, que también es el flujo entrante a $t$ . Debido a la restricción de simetría antisimétrica, de $c$ a $a$ es -2 porque el flujo de $a$ a $c$ es 2.

En la Figura 2 se observa la red residual para el mismo flujo dado. Nótese cómo hay capacidad residual positiva en algunos bordes donde la capacidad original es cero en la Figura 1, por ejemplo para el borde $(d,c)$ Esta red no está funcionando a su máxima capacidad . Hay capacidad disponible a lo largo de las rutas. $(s,a,c,t)$ , $(s,a,b,d,t)$ y $(s,a,b,d,c,t)$ , que son entonces las rutas de aumento.

El cuello de botella de la $(s,a,c,t)$ El camino es igual a $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))$ $=\min(5-3,3-2,2-1)$ $=\min(2,1,1)=1$ .

Aplicaciones

Imaginemos una serie de tuberías de agua conectadas en red. Cada tubería tiene un diámetro determinado, por lo que solo puede mantener un caudal específico. En cualquier punto donde se unen las tuberías, el caudal total de agua que entra debe ser igual al que sale; de lo contrario, nos quedaríamos sin agua rápidamente o se acumularía. Tenemos una entrada de agua, que es la fuente, y una salida, el fregadero. Un caudal constante sería una forma posible de que el agua vaya desde la fuente hasta el fregadero, de manera que el caudal total que sale por la salida sea constante. Intuitivamente, el caudal total de una red es la velocidad a la que el agua sale por la salida.

Los flujos pueden referirse a personas o materiales en redes de transporte, o a electricidad en sistemas de distribución eléctrica . En 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 de corrientes de Kirchhoff .

Las redes de flujo también encuentran aplicaciones en ecología : surgen de forma natural al considerar el flujo de nutrientes y energía entre diferentes organismos en una red trófica . Los problemas matemáticos asociados a estas redes son bastante diferentes de los que surgen en las redes de flujo de fluidos 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 los problemas de flujo

El problema más simple y común que utiliza redes de flujo es encontrar lo que se denomina flujo máximo , que proporciona el mayor flujo total posible desde el origen hasta el destino en un grafo dado. Existen 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 pueden resolverse en tiempo polinomial con varios algoritmos (véase la tabla). El teorema del corte mínimo de flujo máximo establece que encontrar un flujo de red máximo es equivalente a encontrar un corte de capacidad mínima que separe el origen y el destino, donde un corte es la división de vértices de tal manera que el origen se encuentre en una división y el destino en otra.

En un problema de flujo de múltiples mercancías , existen múltiples fuentes y sumideros, y diversas "mercancías" que deben fluir desde una fuente determinada hasta un sumidero específico. Esto podría ser, por ejemplo, diversos bienes producidos en distintas fábricas y entregados a diferentes clientes a través de la misma red de transporte.

En un problema de flujo de costo mínimo , cada arista $u,v$ tiene un costo determinado $k(u,v)$ y el costo de enviar el flujo $f(u,v)$ al otro lado del borde está $f(u,v)\cdot k(u,v)$ El objetivo es enviar una cantidad determinada de flujo desde la fuente hasta el sumidero, al menor precio posible.

En un problema de circulación , tienes un límite inferior. $\ell (u,v)$ en los bordes, además del límite superior $c(u,v)$ Cada arista también tiene un costo. A menudo, la conservación del flujo se cumple para todos los nodos en un problema de circulación, y hay una conexión desde el sumidero de vuelta a la fuente. De esta manera, puede dictar el flujo total con $\ell (t,s)$ y $c(t,s)$ El flujo circula a través de la red, de ahí el nombre del problema.

En una red con ganancias o red generalizada , cada arista tiene una ganancia , un número real (distinto de cero) tal que, si la arista tiene una ganancia g , y una cantidad x fluye hacia la arista 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 de origen más probable de la difusión de información a través de una red parcialmente observada. Esto se puede realizar en tiempo lineal para árboles y en tiempo cúbico para redes arbitrarias, y tiene aplicaciones que van desde el seguimiento de usuarios de teléfonos móviles hasta la identificación del origen de brotes de enfermedades. ^{[ 8 ]}

Véase también

Referencias

↑ AV Goldberg, É. Tardos y RE Tarjan, Algoritmos de flujo de red, Informe técnico STAN-CS-89-1252, Departamento de Ciencias de la Computación de la Universidad de Stanford, 1989
^ Kleinberg , Jon (2011). Diseño de algoritmos . Éva Tardos (2ª ed.). Boston, Massachusetts: Addison-Wesley. págs.342 , 346. ISBN 978-0-13-213108-7OCLC 796210667
↑ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Englewood Cliffs (NJ): Prentice Hall. ISBN 978-0-13-617549-0.
↑ Este artículo incorpora material de dominio público de Paul E. Black. "Supersource" . Diccionario de algoritmos y estructuras de datos . NIST .
↑ Este artículo incorpora material de dominio público de Paul E. Black. "Supersink" . Diccionario de algoritmos y estructuras de datos . NIST .
↑ Malhotra, VM; Kumar, M.Pramodh; Maheshwari, SN (1978). "Un $O(|V|^{3})$ Algoritmo para encontrar flujos máximos en redes" (PDF) . Information Processing Letters . 7 (6): 277– 278. doi : 10.1016/0020-0190(78)90016-9 . Archivado (PDF) del original el 18 de abril de 2021. Recuperado el 11 de julio de 2019 .
↑ Orlin, James B. (1 de junio de 2013). "Máximos flujos en tiempo O(nm), o mejor" . Actas del cuadragésimo quinto simposio anual de la ACM sobre Teoría de la Computación . STOC '13. Palo Alto, California, EE. UU.: Association for Computing Machinery. págs. 765–774 . doi : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207 .
↑ Pinto, PC; Thiran, P.; Vetterli, M. (2012). "Localización de la fuente de difusión en redes a gran escala" ( PDF) . Physical Review Letters . 109 (6) 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . PMID 23006310. S2CID 14526887. Archivado (PDF) del original el 22-10-2012 . Recuperado el 14-08-2012 .

Lecturas adicionales

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 ; James B. Orlin (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall. ISBN 0-13-617549-X.
Bollobás, Béla (1979). Teoría de grafos: Un curso introductorio . Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary ; Oellermann, Ortrud R. (1993). Teoría de grafos aplicada y algorítmica . Nueva York: McGraw-Hill. ISBN 0-07-557101-3.
Even, Shimon (1979). Algoritmos de grafos . 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 ; 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.

Enlaces externos

Problema de flujo máximo
Instancias de grafos reales
Librería Lemon C++ con varios algoritmos de circulación de flujo máximo y coste mínimo.
QuickGraph archivado el 21/01/2018 en Wayback Machine , estructuras de datos y algoritmos de grafos para .Net

[1] AV Goldberg, É. Tardos y RE Tarjan, Algoritmos de flujo de red, Informe técnico STAN-CS-89-1252, Departamento de Ciencias de la Computación de la Universidad de Stanford, 1989

[:0-2] Kleinberg , Jon (2011). Diseño de algoritmos . Éva Tardos (2ª ed.). Boston, Massachusetts: Addison-Wesley. págs.342 , 346. ISBN 978-0-13-213108-7OCLC 796210667

[3] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Englewood Cliffs (NJ): Prentice Hall. ISBN 978-0-13-617549-0.

[4] Este artículo incorpora material de dominio público de Paul E. Black. "Supersource" . Diccionario de algoritmos y estructuras de datos . NIST .

[5] Este artículo incorpora material de dominio público de Paul E. Black. "Supersink" . Diccionario de algoritmos y estructuras de datos . NIST .

[6] Malhotra, VM; Kumar, M.Pramodh; Maheshwari, SN (1978). "Un $O(|V|^{3})$ Algoritmo para encontrar flujos máximos en redes" (PDF) . Information Processing Letters . 7 (6): 277– 278. doi : 10.1016/0020-0190(78)90016-9 . Archivado (PDF) del original el 18 de abril de 2021. Recuperado el 11 de julio de 2019 .

[7] Orlin, James B. (1 de junio de 2013). "Máximos flujos en tiempo O(nm), o mejor" . Actas del cuadragésimo quinto simposio anual de la ACM sobre Teoría de la Computación . STOC '13. Palo Alto, California, EE. UU.: Association for Computing Machinery. págs. 765–774 . doi : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207 .

[8] Pinto, PC; Thiran, P.; Vetterli, M. (2012). "Localización de la fuente de difusión en redes a gran escala" ( PDF) . Physical Review Letters . 109 (6) 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . PMID 23006310. S2CID 14526887. Archivado (PDF) del original el 22-10-2012 . Recuperado el 14-08-2012 .

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 8 ]