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.
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 ) ∈ E , entonces ( v , u ) también es un miembro de E . Además, si ( v , u ) ∉ 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]
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 x f : V → 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.
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 ∈ A y t ∉ 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 .
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.
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:
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 ]
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 .
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 ≤ 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.
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]
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.
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.
El cuello de botella del camino es igual a .
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.
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.
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.
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.
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]
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 .
