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

Flow decomposition^[3] is a process of breaking down a given flow into a collection of path flows and cycle flows. Every flow through a network can be decomposed into one or more paths and corresponding quantities, such that each edge in the flow equals the sum of all quantities of paths that pass through it. Flow decomposition is a powerful tool in optimization problems to maximize or minimize specific flow parameters.

Adding arcs and flows

We do not use multiple arcs within a network because we can combine those arcs into a single arc. To combine two arcs into a single arc, we add their capacities and their flow values, and assign those to the new arc:

Given any two nodes $u$ and $v$ , having two arcs from $u$ to $v$ with capacities $c 1 (u,v)$ and $c 2 (u,v)$ respectively is equivalent to considering only a single arc from $u$ to $v$ with a capacity equal to $c 1 (u,v)+ c 2 (u,v)$ .
Given any two nodes $u$ and $v$ , having two arcs from $u$ to $v$ with pseudo-flows $f 1 (u,v)$ and $f 2 (u,v)$ respectively is equivalent to considering only a single arc from $u$ to $v$ with a pseudo-flow equal to $f 1 (u,v)+ f 2 (u,v)$ .

Along with the other constraints, the skew symmetry constraint must be remembered during this step to maintain the direction of the original pseudo-flow arc. Adding flow to an arc is the same as adding an arc with the capacity of zero.

Residuals

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$ .

The bottleneck is the minimum residual capacity of all the edges in a given augmenting path.^[2] See example explained in the "Example" section of this article. The flow network is at maximum flow if and only if it has a bottleneck with a value equal to zero. If any augmenting path exists, its bottleneck weight will be greater than 0. In other words, if there is a bottleneck value greater than 0, then there is an augmenting path from the source to the sink. However, we know that if there is any augmenting path, then the network is not at maximum flow, which in turn means that, if there is a bottleneck value greater than 0, then the network is not at maximum flow.

The term "augmenting the flow" for an augmenting path means updating the flow $f$ of each arc in this augmenting path to equal the capacity $c$ of the bottleneck. Augmenting the flow corresponds to pushing additional flow along the augmenting path until there is no remaining available residual capacity in the bottleneck.

Multiple sources and/or sinks

Sometimes, when modeling a network with more than one source, a supersource is introduced to the graph.^[4] This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.^[5]

Example

In Figure 1 you see a flow network with source labeled $s$ , sink $t$ , and four additional nodes. The flow and capacity is denoted $f/c$ . Notice how the network upholds the capacity constraint and flow conservation constraint. The total amount of flow from $s$ to $t$ is 5, which can be easily seen from the fact that the total outgoing flow from $s$ is 5, which is also the incoming flow to $t$ . By the skew symmetry constraint, from $c$ to $a$ is -2 because the flow from $a$ to $c$ is 2.

In Figure 2 you see the residual network for the same given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero in Figure 1, for example for the edge $(d,c)$ . This network is not at maximum flow. There is available capacity along the paths $(s,a,c,t)$ , $(s,a,b,d,t)$ and $(s,a,b,d,c,t)$ , which are then the augmenting paths.

The bottleneck of the $(s,a,c,t)$ path is equal to $\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$ .

Applications

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.

In a multi-commodity flow problem, you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the same transportation network.

In a minimum cost flow problem, each edge $u,v$ has a given cost $k(u,v)$ , and the cost of sending the flow $f(u,v)$ across the edge is $f(u,v)\cdot k(u,v)$ . The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In a circulation problem, you have a lower bound $\ell (u,v)$ on the edges, in addition to the upper bound $c(u,v)$ . Each edge also has a cost. Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with $\ell (t,s)$ and $c(t,s)$ . The flow circulates through the network, hence the name of the problem.

In a network with gains or generalized network each edge has a gain, a real number (not zero) such that, if the edge has gain g, and an amount x flows into the edge at its tail, then an amount gx flows out at the head.

In a source localization problem, an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating source of disease outbreaks.^[8]

References

↑ 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, P.C.; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks"(PDF). Physical Review Letters. 109 (6) 068702. arXiv:1208.2534. Bibcode:2012PhRvL.109f8702P. doi:10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887. Archived(PDF) from the original on 2012-10-22. Retrieved 2012-08-14.

External links

Maximum Flow Problem
Real graph instances
Lemon C++ library with several maximum flow and minimum cost circulation algorithms
QuickGraphArchived 2018-01-21 at the Wayback Machine, graph data structures and algorithms for .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, P.C.; Thiran, P.; Vetterli, M. (2012). "Locating the source of diffusion in large-scale networks"(PDF). Physical Review Letters. 109 (6) 068702. arXiv:1208.2534. Bibcode:2012PhRvL.109f8702P. doi:10.1103/PhysRevLett.109.068702. PMID 23006310. S2CID 14526887. Archived(PDF) from the original on 2012-10-22. Retrieved 2012-08-14.

[ 1 ]

[3]

[4]

[5]

[8]

Red de flujo

Definición

Flujos