Red de flujo

En la teoría de grafos, una red de flujo (también conocida como red de transporte) es un gráfico dirigido donde cada borde tiene una capacidad y cada borde 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 denomina red, los vértices se denominan nodos y las aristas se denominan 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 tráfico en una red informática, circulación con demandas, fluidos en tuberías, corrientes en un circuito eléctrico o cualquier cosa similar en la que algo viaja a través de una red de nodos.

Definición

Una red es un gráfico G = (V, E), donde V es un conjunto de vértices y E es un conjunto de aristas de V, un subconjunto de V × V, junto con una función no negativa c: V × V → _∞, llamada función de capacidad. Sin pérdida de generalidad, podemos suponer que si (u, v) ∈ E entonces (v, u) también es miembro de E, ya que si (v, u) ∉ E entonces podemos sumar (v, u) a E y luego establecer c (v, u) = 0.

Si se distinguen dos nodos en G, una fuente s y un sumidero t, entonces (G, c, s, t) se denomina red de flujo.

Flujos

Hay varias nociones de una función de flujo que se pueden definir en un gráfico de flujo. 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? El ejemplo más simple de una función de flujo se conoce como pseudo-flujo.Un pseudo-flujo es una función f: V × V → que satisface las siguientes dos restricciones para todos los nodos u y v:

• Simetría sesgada: solo codifique el flujo neto de unidades entre un par de nodos u y v (consulte la intuición a continuación), es decir: f (u, v) = − f (v, u).
• Restricción de capacidad: el flujo de un arco no puede exceder su capacidad, es decir: f (u, v) ≤ c (u, v).

Dado un pseudo-flujo f en una red de flujo, a menudo es útil considerar el flujo neto que ingresa a un nodo dado u, es decir, la suma de los flujos que ingresan a u. La función de exceso x _f: V → está definida por x _f (u) = Σ _{v ∈ V} f (v, u). Se dice que un nodo u está activo si x _f (u) > 0, deficiente si x _f(u) < 0 o conservando si x _f (u) = 0.

Estas definiciones finales conducen a dos refuerzos de la definición de un pseudo-flujo: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 por la fuente, que "produce" flujo. Es decir: x _f (v) ≥ 0 para todo v ∈ V { s }.

Un flujo factible, o simplemente un flujo, es un pseudo-flujo que, para todo v ∈ V { s, t }, satisface la restricción adicional:

• Conservación del flujo: el flujo neto que ingresa al nodo v es 0, excepto por la fuente, que "produce" flujo, y el sumidero, que "consume" flujo. Es decir: x _f (v) = 0 para todo v ∈ V { s, t }.

El valor de un flujo factible f, denotado | f |, es el flujo neto hacia el sumidero t de la red de flujo. Es decir, | f | = X _F (t).

Intuición

En el contexto del análisis de flujo, solo hay interés en considerar cómo se transfieren las unidades entre nodos en un sentido holístico. Dicho de otra manera, no es necesario distinguir múltiples arcos entre un par de nodos:

• Dados dos nodos cualesquiera u y v, si hay dos arcos de u a v con capacidades 5 y 3 respectivamente, esto es equivalente a considerar un solo arco entre u y v con capacidad 8; solo es útil saber que 8 unidades se pueden transferir de u a v, no cómo se pueden transferir.
• Nuevamente, dados dos nodos u y v, si hay un flujo de 5 unidades de u a v, y otro flujo de 3 unidades de v a u, esto es equivalente a un flujo neto de 2 unidades de u a v, o un flujo neto de −2 unidades de v a u (por lo que el signo indica la dirección): solo es útil saber que un flujo neto de 2 unidades fluirá entre u y v, y la dirección en la que fluirán, no cómo ese flujo neto se consigue.

Por esta razón, la función de capacidad c: V × V → _∞, que no permite que múltiples arcos comiencen y terminen en los mismos nodos, es suficiente para el análisis de flujo. De manera similar, es suficiente imponer la restricción de simetría sesgada en las funciones de flujo para garantizar que el flujo entre dos vértices esté codificado por un solo número (para indicar la magnitud) y un signo (para indicar la dirección), conociendo el flujo entre u y v usted implícitamente, a través de la simetría sesgada, conoce el flujo entre v y u. Estas simplificaciones del modelo no siempre son inmediatamente intuitivas, pero son convenientes cuando llega el momento de analizar los flujos.

La restricción de capacidad simplemente asegura que un flujo en cualquier arco dentro de la red no pueda exceder la capacidad de ese arco.

Conceptos útiles para problemas de flujo

Derechos residuales de autor

La capacidad residual de un arco con respecto,. a un pseudoflujo f, denotado c _f, 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, denominada G _f (V, E _f), que modela la cantidad de capacidad disponible en el conjunto de arcos en G = (V, E). Más formalmente, dada una red de flujo G, la red residual G _f tiene el conjunto de nodos V, el conjunto de arcos E _f = { e ∈ V × V: c _f (e) > 0} y la función de capacidad c _f.

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 un camino de u a v en la red residual, aunque no haya un 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 lo mismo que aumentar el flujo de u a v.

Aumento de caminos

Una ruta de aumento es una ruta (u ₁, u ₂,..., u _k) en la red residual, donde u ₁ = s, u _k = t, y c _f (u _i, u _{i + 1}) > 0. Una red tiene un flujo máximo si y solo si no hay una ruta de aumento en la red residual G _f.

Múltiples fuentes y/o sumideros

A veces, cuando se modela una red con más de una fuente, se introduce una superfuente en el gráfico. Este consiste en un vértice conectado a cada una de las fuentes con aristas de capacidad infinita, de manera que actúe como una fuente global. Una construcción similar para sumideros se llama supersink.

Ejemplo

A la izquierda, verá una red de flujo con la fuente etiquetada como s, el receptor como t y cuatro nodos adicionales. Se denota el flujo y la capacidad . Observe cómo la red mantiene la simetría sesgada, las restricciones de capacidad y la 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 de entrada a t. Sabemos que ningún flujo aparece o desaparece en ninguno de los otros nodos.

A continuación, verá la red residual para el flujo dado. Observe cómo hay una capacidad residual positiva en algunos bordes donde la capacidad original es cero, por ejemplo para el borde . Este caudal no es un caudal máximo. Hay capacidad disponible a lo largo de las rutas , y , que luego son las rutas de aumento. La capacidad residual del primer camino es. Nótese que mientras exista algún camino con capacidad residual positiva, el caudal no será máximo. La capacidad residual para algún camino es la capacidad residual mínima de todos los bordes en ese camino.

Aplicaciones

Imagine una serie de tuberías de agua, encajando en una red. Cada tubería tiene un diámetro determinado, por lo que solo puede mantener un flujo de cierta cantidad de agua. En cualquier lugar donde las tuberías se encuentren, la cantidad total de agua que entra en esa unión debe ser igual a la cantidad que sale, de lo contrario nos quedaremos 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 pase de la fuente al sumidero, de modo que la cantidad total de agua que sale por la salida sea constante. Intuitivamente, el caudal total de una red es la velocidad a la que sale agua por el desagüe.

Los flujos pueden pertenecer a personas o materiales a través de redes de transporte, oa 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 este tipo de redes son bastante diferentes de los que surgen en las redes de flujo de tráfico o de fluidos. El campo del análisis de redes de ecosistemas, desarrollado por Robert Ulanowicz y otros, involucra 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 usar redes de flujo es encontrar lo que se llama el flujo máximo, que proporciona el flujo total más grande posible desde la fuente hasta el sumidero en un gráfico dado. Hay muchos otros problemas que se pueden resolver utilizando algoritmos de flujo máximo, si se modelan adecuadamente como redes de flujo, como la coincidencia bipartita, el problema de asignación y el problema de transporte. Los problemas de flujo máximo se pueden resolver de manera eficiente con el algoritmo push-relabel. El teorema max-flow min-cut 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 tal que la fuente está en una división y el fregadero está en otro.

inventor(es)	Año	Complejidad temporal(con n nodosy arcos m)
Algoritmo de Dinic	1969	O (mn)
Algoritmo de Edmonds-Karp	1972	O (m n)
Algoritmo MPM (Malhotra, Pramodh-Kumar y Maheshwari)	1978	O (n)
James B Orlin	2013	O (mn)

En un problema de flujo de múltiples productos, tiene múltiples fuentes y sumideros, y varios "productos básicos" que deben fluir desde una fuente determinada a un sumidero determinado. Esto podría ser, por ejemplo, varios bienes que se producen en varias fábricas y se deben entregar 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 dado y el costo de enviar el flujo a través del borde es . El objetivo es enviar una determinada cantidad de flujo desde la fuente hasta el sumidero, al precio más bajo posible.

En un problema de circulación, tiene un límite inferior en los bordes, además del límite superior . Cada borde también tiene un costo. A menudo, la conservación del flujo es válida para todos los nodos en un problema de circulación, y existe una conexión desde el sumidero hasta la fuente. De esta forma, puede dictar el caudal total con y . El flujo circula por la red, de ahí el nombre del problema.

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 una ganancia g, y una cantidad x fluye hacia el borde por su cola, entonces una cantidad gx sale 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 el seguimiento de usuarios de teléfonos móviles hasta la identificación de la fuente de origen de los brotes de enfermedades.