Red de flujo

Grafo dirigido donde las aristas tienen capacidad

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 cada arista recibe un flujo. La cantidad de flujo en una arista no puede exceder la capacidad de la arista. A menudo en investigación de operaciones , un grafo dirigido se llama red , los vértices se llaman nodos y las aristas se llaman arcos . Un flujo debe satisfacer la restricción de que la cantidad de flujo que entra en un nodo sea 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 se puede utilizar para modelar el tráfico en una red de computadoras, la 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 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 suponer 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 fuente $s$ y el otro como 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 cuando se plantean preguntas como: ¿cuál es la cantidad máxima de unidades que se pueden transferir desde el nodo de origen s al nodo receptor t? La cantidad de flujo entre dos nodos se utiliza para representar la cantidad neta de unidades que se transfieren de un nodo al otro.

La función de exceso $\mathbb {R}$ representa el flujo neto que entra en un nodo dado $u$ (es decir, la suma de los flujos que entran en $u$ ) y está definida por Se dice que un nodo $u$ es 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 conservante si $x$ $f$ $($ $u$ $) = 0$ . En 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. $x_{f}(u)=\sum _{w\in V}f(w,u).$

Un pseudoflujo es una función

f

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

u

y

v

:

Restricción de simetría oblicua : 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 la dirección del flujo.
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$ 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 pseudoflujo que, para todo

v ∈ V \{ s , t

}, satisface la restricción adicional:

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

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 total saliente de la fuente $s$ , es decir: $| f | = - x f (s)$ . Además, si definimos $A$ como un conjunto de nodos en $G$ tales 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 desde $s$ hasta $t$ .

Conceptos útiles para problemas de flujo

Descomposición del flujo

La descomposición del flujo ^[3] es un proceso que consiste en descomponer un flujo determinado en una colección de flujos de trayectorias y flujos de ciclos. Cada flujo que atraviesa una red se puede descomponer en una o más trayectorias y sus cantidades correspondientes, de modo que cada arista del flujo sea igual a la suma de todas las cantidades de trayectorias que pasan por él. La descomposición del flujo es una herramienta poderosa en los problemas de optimización para maximizar o minimizar parámetros de flujo específicos.

Añadiendo arcos y flujos

No utilizamos varios arcos dentro de una red porque podemos combinarlos en un solo arco. Para combinar dos arcos en un solo arco, sumamos sus capacidades y sus valores de caudal 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 $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)$ .

Junto con las demás restricciones, durante este paso se debe recordar la restricción de simetría oblicua para mantener la dirección del arco de pseudoflujo original. Agregar flujo a un arco es lo mismo que agregar un arco con capacidad cero. ^{[ cita requerida ]}

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 flujo máximo en una red de flujo.

Obsérvese que puede haber una ruta no saturada (una ruta con capacidad disponible) de $u$ a $v$ en la red residual, aunque no exista tal ruta de $u$ a $v$ en la red original. ^{[ cita requerida ]} 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$ .

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)$ . En términos más simples, 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 un 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] Vea 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 esta ruta de aumento para que sea igual a la capacidad $c$ del cuello de botella. Aumentar el flujo corresponde 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 con aristas de capacidad infinita, de modo que actúe como una fuente global. Una construcción similar para los sumideros se denomina supersumidero . ^[5]

Ejemplo

En la Figura 1 se ve una red de flujo con una fuente etiquetada como $s$ , un sumidero $como t$ y cuatro nodos adicionales. El flujo y la capacidad se denotan como . Observe cómo la red mantiene la restricción de capacidad y la restricción de conservación de flujo. La cantidad total de flujo de $s$ a $t$ es 5, lo que 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$ . Por la restricción de simetría oblicua, de $c$ a $a$ es -2 porque el flujo de $a$ a $c$ es 2. ${\estilo de visualización f/c}$

En la Figura 2 se ve la red residual para el mismo flujo dado. Observe cómo hay capacidad residual positiva en algunos bordes donde la capacidad original es cero en la Figura 1, por ejemplo para el borde . Esta red no está en el flujo máximo . Hay capacidad disponible a lo largo de las rutas , y , que son las rutas de aumento. ${\estilo de visualización (d,c)}$ $(s,a,c,t)$ ${\estilo de visualización (s,a,b,d,t)}$ ${\estilo de visualización (s,a,b,d,c,t)}$

El cuello de botella del camino es igual a . $(s,a,c,t)$ $\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 que encajan en una red. Cada tubería tiene un diámetro determinado, por lo que solo puede mantener un flujo de una cierta cantidad de agua. En cualquier punto en el que se encuentren las tuberías, la cantidad total de agua que entra en esa unión debe ser igual a la cantidad que sale, de lo contrario nos quedaríamos rápidamente sin agua o tendríamos una acumulación de agua. Tenemos una entrada de agua, que es la fuente, y una salida, el sumidero. Un flujo sería entonces una forma posible de que el agua llegue desde la fuente hasta el sumidero de modo que la cantidad total de agua que sale por la salida sea constante. Intuitivamente, el flujo total de una red es la velocidad a la que el agua sale por la salida.

Los flujos pueden estar relacionados con personas o materiales a través de redes de transporte, o con 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 de corrientes de Kirchhoff .

Las redes de flujo también encuentran aplicaciones en ecología : las redes de flujo surgen de manera natural 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 redes de flujo de fluidos o 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 más común que utiliza redes de flujo es encontrar lo que se llama el flujo máximo , que proporciona el mayor flujo total posible desde la fuente hasta el sumidero en un grafo dado. Hay muchos otros problemas que se pueden resolver 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 en tiempo polinomial con varios algoritmos (ver tabla). El teorema de 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 separa 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 sumidero está en otra.

Algoritmos conocidos para el problema de flujo máximo
Inventor(es)	Año	Complejidad temporal (con $n$ nodos y $m$ arcos)
Algoritmo de Dinic	1970	$O (mn2) $
Algoritmo de Edmonds-Karp	1972	$O (m 2 n)$
Algoritmo MPM (Malhotra, Pramodh-Kumar y Maheshwari) ^[6]	1978	$O (número 3)$
Algoritmo push-reetiqueta ( Goldberg y Tarjan )	1988	$O (n 2 m)$
James B. Orlin ^[7]	2013	$O (mn)$
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva	2022	$O(m^{1+o(1)})$

En un problema de flujo de múltiples productos , existen múltiples fuentes y sumideros, y varios "productos" que deben fluir desde una fuente determinada a un sumidero determinado. Por ejemplo, pueden ser diversos bienes que se producen en distintas fábricas y que deben entregarse a distintos 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 cantidad determinada de flujo desde la fuente hasta el sumidero, al precio más bajo posible. ${\estilo de visualización u,v}$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$

En un problema de circulación , además del límite superior, se aplica un límite inferior a los bordes . Cada borde 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 existe una conexión desde el sumidero hasta la fuente. De esta manera, se puede determinar el flujo total con y . El flujo circula a través de la red, de ahí el nombre del problema. $\ell(u,v)$ $c(u,v)$ $\ell(t,s)$ $c(t,s)$

En una red con ganancias o red generalizada, cada arista tiene una ganancia , un número real (no 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 difusión de información a través de una red parcialmente observada. Esto se puede hacer 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 de la fuente de 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
^ ab Kleinberg, Jon (2011). Diseño de algoritmos. Éva Tardos (2ª ed.). Boston, Massachusetts: Addison-Wesley. págs.342, 346. ISBN 978-0-13-213108-7.OCLC 796210667 .
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Englewood Cliffs (Nueva Jersey): 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 algoritmo O ( | V | 3 ) {\displaystyle O(|V|^{3})} 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) desde el original el 2021-04-18 . Consultado el 2019-07-11 .
^ Orlin, James B. (1 de junio de 2013). "Flujos máximos 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.S2CID207205207 .
^ 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) desde el original el 22 de octubre de 2012 . Consultado el 14 de agosto de 2012 .

Lectura adicional

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 algorítmica y aplicada . 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 de grafos algorítmicos . 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 gráficos reales
Biblioteca Lemon C++ con varios algoritmos de circulación de flujo máximo y costo mínimo
QuickGraph Archivado el 21 de enero de 2018 en Wayback Machine , estructuras de datos gráficos y algoritmos 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-7.OCLC 796210667 .

[3] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Englewood Cliffs (Nueva Jersey): 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 algoritmo O ( | V | 3 ) {\displaystyle O(|V|^{3})} 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) desde el original el 2021-04-18 . Consultado el 2019-07-11 .

[7] Orlin, James B. (1 de junio de 2013). "Flujos máximos 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.S2CID207205207 .

[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) desde el original el 22 de octubre de 2012 . Consultado el 14 de agosto de 2012 .