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 cada arista 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 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 ingresa a 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 se puede utilizar para modelar el tráfico en una red informática, la circulación con demandas, los fluidos en las tuberías, las 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 dirigido $G = (V, E) con una$ función de capacidad $c$ no negativa para cada borde y sin múltiples arcos (es decir, bordes 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 miembro de $E.$ Además, si $($ $v$ $,$ $u$ $) \notin$ $E$ entonces podemos sumar $($ $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 hacen preguntas como ¿ cuál es el número máximo de unidades que se pueden transferir desde el nodo fuente s al nodo sumidero 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}$ $u$ dado (es decir, la suma de los flujos que ingresan $a u$ ) y está definida por

x_{f}(u)=\sum _ {w\in V}f(w,u).

u es

activo

x f (u) > 0

u

deficiente

x f (u) < 0

u

conservante

x f (u) = 0

s

t

Los pseudoflujos, los flujos factibles y los preflujos son ejemplos de funciones de flujo.

Un pseudoflujo es una función

f

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

u

v

Restricción de simetría sesgada : 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 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 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 ingresa a 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$ $}$ ). $s$ $t$ $s$ $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 | = xf (t)$ . $$ Tenga en cuenta 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$ 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 en un))$ . ^[2] El valor del flujo en una red es la cantidad total de flujo desde $sa$ $t$ .

Conceptos útiles para problemas de flujo.

Descomposición del flujo

La descomposición del flujo ^[3] es un proceso de descomponer un flujo dado en una colección de flujos de trayectoria y flujos de ciclo. Cada flujo a través de una red se puede descomponer en uno o más caminos y cantidades correspondientes, de modo que cada borde del flujo sea igual a la suma de todas las cantidades de caminos que lo 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 combinar esos arcos en un solo arco. Para combinar dos arcos en un solo arco, 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 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 arco de $u$ a $v$ con un pseudoflujo. -flujo igual a $f 1 (u,v)+f 2 (u,v)$ .

Junto con las otras restricciones, la restricción de simetría sesgada debe recordarse durante este paso 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 necesaria ]}

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.

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

Caminos de aumento

Una ruta aumentante es una ruta $(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 yo, u yo + 1) > 0) (1 \leq yo < k)$ . Más simplemente, una ruta de aumento es una ruta de flujo disponible desde la fuente hasta el sumidero. Una red tiene un flujo máximo si y solo si no hay una ruta 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 determinada. ^[2] Ver ejemplo explicado en la sección "Ejemplo" de este artículo. La red de flujo está en flujo máximo si y sólo 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 tiene el 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 tiene el 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 igualar la capacidad $c$ del cuello de botella. Aumentar el flujo corresponde a empujar flujo adicional a lo largo del camino de aumento hasta que no quede capacidad residual disponible en el cuello de botella.

Múltiples fuentes y/o sumideros

A veces, al modelar una red con más de una fuente, se introduce una superfuente en el gráfico. ^[4] 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 sumideros se llama supersumidero . ^[5]

Ejemplo

En la Figura 1, ve una red de flujo con fuente etiquetada como $s$ , sumidero $t$ y cuatro nodos adicionales. Se denota el flujo y la capacidad . Observe cómo la red mantiene la restricción de simetría sesgada, la restricción de capacidad y la restricción de conservación del flujo. La cantidad total de flujo de $s$ a $t$ es 5, lo que se puede ver fácilmente por el hecho de que el flujo total de salida de $s$ es 5, que también es el flujo entrante a $t$ . Tenga en cuenta que la Figura 1 suele escribirse en el estilo de notación de la Figura 2. $f/c$

En la Figura 3 se ve la red residual para el 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á al máximo de caudal . Hay capacidad disponible a lo largo de las rutas , y , que son entonces las rutas de aumento. $(d,c)$ $(s,a,c,t)$ $(s,a,b,d,t)$ $(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

Imagínese una serie de tuberías de agua, encajando en una red. Cada tubería tiene un diámetro determinado, por lo que sólo puede mantener un flujo de una determinada cantidad de agua. En cualquier lugar donde se encuentren las tuberías, la cantidad total de agua que entra en ese cruce 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 llegue desde la fuente hasta el fregadero, de modo que la cantidad total de agua que sale por la salida sea constante. Intuitivamente, el caudal total de una red es el ritmo al que sale agua por la salida.

Los flujos pueden pertenecer a personas o materiales a través de redes de transporte, o a 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 redes de fluidos o flujo 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 utilizar 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 determinado. 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 en tiempo polinómico con varios algoritmos (ver tabla). El teorema del flujo máximo y del 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 modo que la fuente esté en una división y el El lavabo está en otro.

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 hasta un sumidero determinado. Podrían tratarse, por ejemplo, de diversos bienes que se producen en distintas fábricas y que deben entregarse 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 cantidad determinada de flujo desde la fuente al sumidero, al menor precio posible. $u,v$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$

En un problema de circulación , tienes un límite inferior en los bordes, además del límite superior . Cada arista también tiene un coste. 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 hasta la fuente. De esta manera, puedes dictar el flujo total con y . El flujo circula por 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 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 en tiempo cúbico para redes arbitrarias y tiene aplicaciones que van desde rastrear usuarios de teléfonos móviles hasta identificar la fuente de origen de brotes de enfermedades. ^[8]

Ver también

Referencias

^ AV Goldberg, É. Tardos y RE Tarjan, Algoritmos de flujo de red, Tech. Informe STAN-CS-89-1252, Departamento de informática 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. "Superfuente". Diccionario de Algoritmos y Estructuras de Datos . NIST .
^ Este artículo incorpora material de dominio público de Paul E. Black. "Superdisipador". 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) . Cartas de procesamiento de información . 7 (6): 277–278. doi :10.1016/0020-0190(78)90016-9. Archivado (PDF) desde el original el 18 de abril de 2021 . Consultado el 11 de julio de 2019 .
^ 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 ACM sobre Teoría de la Computación . ESTOC '13. Palo Alto, California, EE.UU.: Asociación de Maquinaria de Computación. págs. 765–774. doi :10.1145/2488608.2488705. hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207 – a través del acceso abierto del MIT https://dspace.mit.edu/handle/1721.1/88020. {{cite book}}: Enlace externo en |via=( ayuda )
^ Pinto, ordenador personal; Tiran, P.; Vetterli, M. (2012). «Localizar la fuente de difusión en redes de gran escala» (PDF) . Cartas de revisión física . 109 (6): 068702. arXiv : 1208.2534 . Código bibliográfico : 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 .

Otras lecturas

George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 8: Algoritmos de flujo de red". Algoritmos en pocas palabras . Medios Oreilly . 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.{{cite book}}: Mantenimiento CS1: 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.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
Incluso, Shimon (1979). Algoritmos de gráficos . Rockville, Maryland: Prensa de Ciencias de la Computación. ISBN 0-914894-21-8.
Gibbons, Alan (1985). Teoría algorítmica de grafos . Cambridge: Prensa de la Universidad de Cambridge. 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.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )

enlaces externos

Wikimedia Commons tiene medios relacionados con las redes Flow.

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 , grafica estructuras de datos y algoritmos para .Net