Problema de flujo máximo - Maximum flow problem

Red de flujo para el problema: cada ser humano (r i ) está dispuesto a adoptar un gato (w i 1) y / o un perro (w i 2). Sin embargo, cada mascota (p i ) tiene preferencia por solo un subconjunto de los humanos. Encuentre cualquier coincidencia de mascotas con humanos de manera que el número máximo de mascotas sea adoptado por uno de sus humanos preferidos.

En la teoría de la optimización , los problemas de caudal máximo implican encontrar un caudal factible a través de una red de caudal que obtenga el caudal máximo posible.

El problema de flujo máximo puede verse como un caso especial de problemas de flujo de red más complejos, como el problema de circulación . El valor máximo de un flujo st (es decir, el flujo desde la fuente s al sumidero t) es igual a la capacidad mínima de un corte st (es decir, el corte seccionando s de t) en la red, como se indica en el flujo máximo mín. teorema de corte .

Historia

El problema de flujo máximo fue formulado por primera vez en 1954 por TE Harris y FS Ross como un modelo simplificado del flujo de tráfico ferroviario soviético.

En 1955, Lester R. Ford, Jr. y Delbert R. Fulkerson crearon el primer algoritmo conocido, el algoritmo Ford-Fulkerson . En su artículo de 1955, Ford y Fulkerson escribieron que el problema de Harris y Ross se formula de la siguiente manera (ver p. 5):

Considere una red ferroviaria que conecta dos ciudades a través de varias ciudades intermedias, donde cada enlace de la red tiene asignado un número que representa su capacidad. Suponiendo una condición de estado estable, encuentre un flujo máximo de una ciudad determinada a la otra.

En su libro Flows in Network , en 1962, Ford y Fulkerson escribieron:

Fue planteado a los autores en la primavera de 1955 por TE Harris, quien, junto con el general FS Ross (Ret.), Había formulado un modelo simplificado de flujo de tráfico ferroviario, y señaló este problema particular como el central sugerido por el modelo [11].

donde [11] se refiere al informe secreto de 1955 Fundamentos de un método para evaluar las capacidades de las redes ferroviarias de Harris y Ross (ver p. 5).

A lo largo de los años, se descubrieron varias soluciones mejoradas para el problema de flujo máximo, en particular el algoritmo de ruta de aumento más corto de Edmonds y Karp e independientemente Dinitz; el algoritmo de bloqueo de flujo de Dinitz; el algoritmo push-reetiquetado de Goldberg y Tarjan ; y el algoritmo de flujo de bloqueo binario de Goldberg y Rao. Los algoritmos de Sherman y Kelner, Lee, Orecchia y Sidford, respectivamente, encuentran un flujo máximo aproximadamente óptimo, pero solo funcionan en gráficos no dirigidos.

En 2013, James B. Orlin publicó un artículo que describe un algoritmo. ${\ Displaystyle O (| V || E |)}$

Definición

Una red de flujo, con fuente sy sumidero t . Los números al lado del borde son las capacidades.

Primero establecemos alguna notación:

• Sea una red siendo la fuente y el sumidero de respectivamente.${\ Displaystyle N = (V, E)}$${\ Displaystyle s, t \ in V}$${\ Displaystyle N}$
• Si es función en los bordes de entonces su valor en se denota por o${\ Displaystyle g}$${\ Displaystyle N}$${\ Displaystyle (u, v) \ in E}$${\ Displaystyle g_ {uv}}$${\ Displaystyle g (u, v).}$

Definición. La capacidad de un borde es la cantidad máxima de flujo que puede pasar a través de un borde. Formalmente es un mapa${\ Displaystyle c: E \ to \ mathbb {R} ^ {+}.}$

Definición. Un flujo es un mapa que satisface lo siguiente: ${\ Displaystyle f: E \ to \ mathbb {R}}$

• Limitación de capacidad . El flujo de un borde no puede exceder su capacidad, es decir: para todos${\ Displaystyle f_ {uv} \ leq c_ {uv}}$${\ Displaystyle (u, v) \ en E.}$
• Conservación de caudales. La suma de los flujos que ingresan a un nodo debe ser igual a la suma de los flujos que salen de ese nodo, excepto la fuente y el sumidero. O:

${\ Displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ quad \ sum _ {u: (u, v) \ in E} f_ {uv} = \ sum _ {u: (v, u) \ in E} f_ {vu}.}$

Observación . Los flujos son simétricos sesgados: para todos${\ Displaystyle f_ {uv} = - f_ {vu}}$${\ Displaystyle (u, v) \ en E.}$

Definición. El valor del flujo es la cantidad de flujo que pasa de la fuente al sumidero. Formalmente para un flujo viene dado por: ${\ Displaystyle f: E \ to \ mathbb {R} ^ {+}}$

${\ Displaystyle | f | = \ sum _ {v: (s, v) \ in E} f_ {sv}.}$

Definición. El problema de flujo máximo es enrutar tanto flujo como sea posible desde la fuente hasta el sumidero, en otras palabras, encontrar el flujo con el valor máximo. ${\ Displaystyle f _ {\ textrm {max}}}$

Tenga en cuenta que pueden existir varios flujos máximos, y si se permiten valores de flujo arbitrarios reales (o incluso racionales arbitrarios) (en lugar de solo números enteros), hay exactamente un flujo máximo o infinitos, ya que hay infinitas combinaciones lineales de los flujos máximos de base. En otras palabras, si enviamos unidades de flujo en el borde en un flujo máximo y unidades de flujo en otro flujo máximo, entonces para cada uno podemos enviar unidades y enrutar el flujo en los bordes restantes en consecuencia, para obtener otro flujo máximo. Si los valores de flujo pueden ser números reales o racionales, entonces hay infinitos valores para cada par . ${\ Displaystyle x}$${\ Displaystyle u}$${\ Displaystyle y> x}$${\ Displaystyle u}$${\ Displaystyle \ Delta \ en [0, yx]}$${\ Displaystyle x + \ Delta}$${\ Displaystyle u}$${\ Displaystyle \ Delta}$${\ Displaystyle x, y}$

Algoritmos

La siguiente tabla enumera los algoritmos para resolver el problema de flujo máximo.

Método	Complejidad	Descripción
Programación lineal		Restricciones dadas por la definición de flujo legal . Vea el programa lineal aquí.
Algoritmo de Ford-Fulkerson	${\ Displaystyle O (E \ vert f_ {max} \ vert)}$	Siempre que haya un camino abierto a través del gráfico residual, envíe el mínimo de las capacidades residuales en el camino. Solo se garantiza que el algoritmo terminará si todos los pesos son racionales , en cuyo caso la cantidad agregada al flujo en cada paso es al menos el máximo común divisor de los pesos. De lo contrario, es posible que el algoritmo no converja al valor máximo. Sin embargo, si el algoritmo termina, se garantiza que encontrará el valor máximo.
Algoritmo de Edmonds-Karp	${\ Displaystyle O (VE ^ {2})}$	Una especialización de Ford-Fulkerson, que encuentra caminos cada vez mayores con una búsqueda que prioriza la amplitud .
Algoritmo de Dinic	${\ Displaystyle O (V ^ {2} E)}$	En cada fase, los algoritmos construyen un gráfico en capas con búsqueda de amplitud primero en el gráfico residual . El flujo máximo en un gráfico en capas se puede calcular en el tiempo y el número máximo de fases es . En redes con capacidades unitarias, el algoritmo de Dinic termina en el tiempo. ${\ Displaystyle O (VE)}$${\ Displaystyle V-1}$${\ Displaystyle O (\ min \ {V ^ {2/3}, E ^ {1/2} \} E)}$
Algoritmo MKM (Malhotra, Kumar, Maheshwari)	${\ Displaystyle O (V ^ {3})}$	Una modificación del algoritmo de Dinic con un enfoque diferente para construir flujos de bloqueo. Consulte el papel original .
Algoritmo de Dinic con árboles dinámicos	${\ Displaystyle O (VE \ log V)}$	La estructura de datos de árboles dinámicos acelera el cálculo de flujo máximo en el gráfico en capas . ${\ Displaystyle O (VE \ log V)}$
Algoritmo general de inserción y reetiquetado	${\ Displaystyle O (V ^ {2} E)}$	El algoritmo push relabel mantiene un preflujo, es decir, una función de flujo con posibilidad de exceso en los vértices. El algoritmo se ejecuta mientras hay un vértice con exceso positivo, es decir, un vértice activo en el gráfico. La operación de empuje aumenta el flujo en un borde residual, y una función de altura en los vértices controla a través de los cuales se pueden empujar los bordes residuales. La función de altura se cambia mediante la operación de reetiquetado. Las definiciones adecuadas de estas operaciones garantizan que la función de flujo resultante sea un flujo máximo.
Algoritmo push-reetiquetado con regla de selección de vértice FIFO	${\ Displaystyle O (V ^ {3})}$	Variante del algoritmo push-reetiquetado que siempre selecciona el vértice activo más recientemente y realiza operaciones push mientras el exceso es positivo y hay bordes residuales admisibles de este vértice.
Algoritmo push-reetiquetado con regla de selección de vértice de distancia máxima	${\ Displaystyle O (V ^ {2} {\ sqrt {E}})}$	Variante del algoritmo push-reetiquetado que siempre selecciona el vértice más distante de o (es decir, el vértice de etiqueta más alto) pero de lo contrario procede como el algoritmo FIFO. ${\ Displaystyle s}$${\ Displaystyle t}$
Algoritmo push-reetiquetado con árboles dinámicos	${\ Displaystyle O \ left (VE \ log {\ frac {V ^ {2}} {E}} \ right)}$	El algoritmo construye árboles de tamaño limitado en el gráfico residual con respecto a la función de altura. Estos árboles proporcionan operaciones de empuje multinivel, es decir, empujando a lo largo de una ruta de saturación completa en lugar de un solo borde.
Algoritmo de KRT (King, Rao, Tarjan)	${\ Displaystyle O \ left (VE \ log _ {\ frac {E} {V \ log V}} V \ right)}$
Algoritmo de flujo de bloqueo binario	${\ Displaystyle O \ left (E \ cdot \ min \ {V ^ {2/3}, E ^ {1/2} \} \ cdot \ log {\ frac {V ^ {2}} {E}} \ cdot \ log U \ right)}$	El valor U corresponde a la capacidad máxima de la red.
Algoritmo de James B Orlin + KRT (King, Rao, Tarjan)	${\ Displaystyle O (VE)}$	Resuelve el algoritmo de Orlin max-fluyen en tiempo para mientras KRT lo resuelve en para . ${\ Displaystyle O (VE)}$${\ Displaystyle E \ leq O (V ^ {{\ frac {16} {15}} - \ epsilon})}$${\ Displaystyle O (VE)}$${\ Displaystyle E> V ^ {1+ \ epsilon}}$
Algoritmo de Kathuria-Liu-Sidford	${\ Displaystyle E ^ {4/3 + o (1)} U ^ {1/3}}$	Métodos de puntos interiores y refuerzo de bordes mediante flujos -norm. Se basa en el algoritmo anterior de Madry, que logró el tiempo de ejecución . ${\ Displaystyle \ ell _ {p}}$${\ Displaystyle {\ tilde {O}} (E ^ {10/7} U ^ {1/7})}$
Algoritmo BLNPSSSW / BLLSSSW	${\ Displaystyle {\ tilde {O}} ((E + V ^ {3/2}) \ log U)}$	Métodos de puntos interiores y mantenimiento dinámico de flujos eléctricos con descomposición de expansores.
Algoritmo de Gao-Liu-Peng	${\ Displaystyle {\ tilde {O}} (E ^ {{\ frac {3} {2}} - {\ frac {1} {328}}} \ log U)}$	El algoritmo de Gao, Liu y Peng gira en torno al mantenimiento dinámico de los flujos eléctricos crecientes en el núcleo del algoritmo basado en el método del punto interior de [Mądry JACM '16]. Esto implica diseñar estructuras de datos que, en entornos limitados, devuelvan bordes con gran energía eléctrica en un gráfico que experimenta actualizaciones de resistencia.

Para algoritmos adicionales, vea Goldberg y Tarjan (1988) .

Teorema del flujo integral

El teorema del flujo integral establece que

Si cada borde en una red de flujo tiene capacidad integral, entonces existe un flujo máximo integral.

La afirmación no es solo que el valor del flujo es un número entero, lo que se deriva directamente del teorema de corte mínimo de flujo máximo , sino que el flujo en cada borde es integral. Esto es crucial para muchas aplicaciones combinatorias (ver más abajo), donde el flujo a través de un borde puede codificar si el elemento correspondiente a ese borde debe incluirse en el conjunto buscado o no.

Solicitud

Problema de flujo máximo de múltiples fuentes y múltiples sumideros

Fig. 4.1.1. Transformación de un problema de flujo máximo de múltiples fuentes y múltiples sumideros en un problema de flujo máximo de un solo sumidero de una sola fuente

Dada una red con un conjunto de fuentes y un conjunto de sumideros en lugar de solo una fuente y un sumidero, debemos encontrar el flujo máximo a través . Podemos transformar el problema de múltiples fuentes de múltiples sumideros en un problema de flujo máximo agregando una fuente consolidada que se conecta a cada vértice en y un sumidero consolidado conectado por cada vértice en (también conocido como superfuente y supersink ) con capacidad infinita en cada borde ( Consulte la Fig. 4.1.1.). ${\ Displaystyle N = (V, E)}$${\ Displaystyle S = \ {s_ {1}, \ ldots, s_ {n} \}}$${\ Displaystyle T = \ {t_ {1}, \ ldots, t_ {m} \}}$${\ Displaystyle N}$${\ Displaystyle S}$${\ Displaystyle T}$

Coincidencia bipartita de cardinalidad máxima

Fig. 4.3.1. Transformación de un problema de emparejamiento bipartito máximo en un problema de flujo máximo

Dado un grafo bipartito , hemos de encontrar una coincidencia máxima cardinalidad en , que es un juego que contiene el mayor número posible de aristas. Este problema se puede transformar en un problema de flujo máximo mediante la construcción de una red , donde ${\ Displaystyle G = (X \ cup Y, E)}$${\ Displaystyle G}$${\ Displaystyle N = (X \ cup Y \ cup \ {s, t \}, E ')}$

1. ${\ Displaystyle E '}$contiene los bordes en la dirección de a .${\ Displaystyle G}$${\ Displaystyle X}$${\ Displaystyle Y}$
2. ${\ displaystyle (s, x) \ in E '}$para cada uno y para cada uno .${\ Displaystyle x \ in X}$${\ Displaystyle (y, t) \ in E '}$${\ Displaystyle y \ in Y}$
3. ${\ Displaystyle c (e) = 1}$para cada uno (Ver Fig. 4.3.1).${\ Displaystyle e \ in E '}$

Entonces, el valor del flujo máximo de entrada es igual al tamaño de la máxima coincidencia de entrada , y se puede encontrar una coincidencia máxima de cardinalidad tomando esos bordes que tienen flujo en un flujo máximo integral. ${\ Displaystyle N}$${\ Displaystyle G}$${\ Displaystyle 1}$

Cobertura de trayectoria mínima en gráfico acíclico dirigido

Dado un gráfico acíclico dirigido , debemos encontrar el número mínimo de caminos disjuntos de vértice para cubrir cada vértice . Podemos construir un gráfico bipartito a partir de donde ${\ Displaystyle G = (V, E)}$${\ Displaystyle V}$${\ Displaystyle G '= (V _ {\ textrm {out}} \ cup V _ {\ textrm {in}}, E')}$${\ Displaystyle G}$

1. ${\ Displaystyle V _ {\ textrm {out}} = \ {v _ {\ textrm {out}} \ mid v \ in V \ land v {\ text {tiene borde (s) de salida}} \}}$
2. ${\ displaystyle V _ {\ textrm {in}} = \ {v _ {\ textrm {in}} \ mid v \ in V \ land v {\ text {tiene borde (s) entrante}} \}}$
3. ${\ Displaystyle E '= \ {(u _ {\ textrm {out}}, v _ {\ textrm {in}}) \ in V_ {out} \ times V_ {in} \ mid (u, v) \ in E \ }}$.

Entonces se puede mostrar que tiene una coincidencia de tamaño si y solo si tiene una cubierta de ruta de vértice disjunta de bordes y rutas de contención , donde está el número de vértices en . Por lo tanto, el problema se puede resolver encontrando la máxima coincidencia de cardinalidad en su lugar. ${\ Displaystyle G '}$${\ Displaystyle M}$${\ Displaystyle m}$${\ Displaystyle G}$${\ Displaystyle C}$${\ Displaystyle m}$${\ Displaystyle nm}$${\ Displaystyle n}$${\ Displaystyle G}$${\ Displaystyle G '}$

Intuitivamente, si dos vértices coinciden , entonces el borde está contenido en . Claramente, el número de aristas es . Para ver que es vértice-disjunto, considere lo siguiente: ${\ Displaystyle u _ {\ mathrm {out}}, v _ {\ mathrm {in}}}$${\ Displaystyle M}$${\ Displaystyle (u, v)}$${\ Displaystyle C}$${\ Displaystyle C}$${\ Displaystyle m}$${\ Displaystyle C}$

1. Cada vértice en puede no coincidir en , en cuyo caso no quedan bordes en ; o puede ser igualada , en cuyo caso no es exactamente uno de los bordes dejando en . En cualquier caso, no más de un borde deja ningún vértice adentro .${\ Displaystyle v _ {\ textrm {out}}}$${\ Displaystyle G '}$${\ Displaystyle M}$${\ Displaystyle v}$${\ Displaystyle C}$${\ Displaystyle v}$${\ Displaystyle C}$${\ Displaystyle v}$${\ Displaystyle C}$
2. De manera similar, para cada vértice en - si coincide, hay un solo borde entrante en in ; de lo contrario, no tiene bordes entrantes en .${\ Displaystyle v _ {\ textrm {en}}}$${\ Displaystyle G '}$${\ Displaystyle v}$${\ Displaystyle C}$${\ Displaystyle v}$${\ Displaystyle C}$

Por lo tanto, ningún vértice tiene dos aristas entrantes o dos salientes , lo que significa que todas las rutas de entrada son vértices disjuntos. ${\ Displaystyle C}$${\ Displaystyle C}$

Para mostrar que la cubierta tiene tamaño , comenzamos con una cubierta vacía y la construimos de forma incremental. Para agregar un vértice a la cubierta, podemos agregarlo a una ruta existente o crear una nueva ruta de longitud cero comenzando en ese vértice. El primer caso es aplicable siempre que cualquiera y alguna ruta en la portada comience en , o y alguna ruta termine en . El último caso es siempre aplicable. En el primer caso, el número total de bordes en la cubierta se incrementa en 1 y el número de caminos permanece igual; en el último caso, el número de trayectorias aumenta y el número de aristas permanece igual. Ahora está claro que después de cubrir todos los vértices, la suma del número de caminos y aristas en la cubierta es . Por lo tanto, si el número de bordes en la cubierta es , el número de caminos es . ${\ Displaystyle C}$${\ Displaystyle nm}$${\ Displaystyle u}$${\ Displaystyle (u, v) \ in E}$${\ Displaystyle v}$${\ Displaystyle (v, u) \ in E}$${\ Displaystyle v}$${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle m}$${\ Displaystyle nm}$

Caudal máximo con capacidades de vértice

Fig. 4.4.1. Transformación de un problema de flujo máximo con restricción de capacidades de vértice en el problema de flujo máximo original mediante división de nodos

Sea una red. Suponga que hay capacidad en cada nodo además de la capacidad de borde, es decir, un mapeo tal que el flujo tiene que satisfacer no solo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad del vértice. ${\ Displaystyle N = (V, E)}$${\ Displaystyle c: V \ to \ mathbb {R} ^ {+},}$${\ Displaystyle f}$

${\ Displaystyle \ sum _ {i \ in V} f_ {iv} \ leq c (v) \ qquad \ forall v \ in V \ backslash \ {s, t \}.}$

En otras palabras, la cantidad de flujo que pasa por un vértice no puede exceder su capacidad. Para encontrar el flujo máximo a través , podemos transformar el problema en el problema del flujo máximo en el sentido original expandiéndonos . Primero, cada uno es reemplazado por y , donde está conectado por bordes que entran y está conectado a bordes que salen , luego asigne capacidad al borde que conecta y (ver Fig. 4.4.1). En esta red expandida, la restricción de capacidad de vértice se elimina y, por lo tanto, el problema puede tratarse como el problema de flujo máximo original. ${\ Displaystyle N}$${\ Displaystyle N}$${\ Displaystyle v \ in V}$${\ Displaystyle v _ {\ text {en}}}$${\ Displaystyle v _ {\ text {out}}}$${\ Displaystyle v _ {\ text {en}}}$${\ Displaystyle v}$${\ Displaystyle v _ {\ text {out}}}$${\ Displaystyle v}$${\ Displaystyle c (v)}$${\ Displaystyle v _ {\ text {en}}}$${\ Displaystyle v _ {\ text {out}}}$

Número máximo de trayectos de sa t

Dado un gráfico dirigido y dos vértices y , debemos encontrar el número máximo de caminos de a . Este problema tiene varias variantes: ${\ Displaystyle G = (V, E)}$${\ Displaystyle s}$${\ Displaystyle t}$${\ Displaystyle s}$${\ Displaystyle t}$

1. Los caminos deben estar separados de los bordes. Este problema puede transformarse en un problema de flujo máximo construyendo una red desde , con y siendo la fuente y el sumidero de respectivamente, y asignando a cada borde una capacidad de . En esta red, el flujo máximo es si hay rutas de borde disjuntas. ${\ Displaystyle N = (V, E)}$${\ Displaystyle G}$${\ Displaystyle s}$${\ Displaystyle t}$${\ Displaystyle N}$${\ Displaystyle 1}$${\ Displaystyle k}$${\ Displaystyle k}$

2. Los caminos deben ser independientes, es decir, disjuntos de vértice (excepto para y ). Podemos construir una red desde con capacidades de vértice, donde están las capacidades de todos los vértices y todos los bordes . Entonces, el valor del caudal máximo es igual al número máximo de trayectos independientes desde a . ${\ Displaystyle s}$${\ Displaystyle t}$${\ Displaystyle N = (V, E)}$${\ Displaystyle G}$${\ Displaystyle 1}$${\ Displaystyle s}$${\ Displaystyle t}$

3. Además de que las trayectorias son disjuntos de borde y / o vértice, las trayectorias también tienen una restricción de longitud: contamos sólo las trayectorias cuya longitud es exacta , o como máximo . La mayoría de las variantes de este problema son NP-completas, excepto por pequeños valores de . ${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle k}$

Problema de cierre

Un cierre de un grafo dirigido es un conjunto de vértices C , de manera que no hay bordes dejan C . El problema de cierre es la tarea de encontrar el cierre de peso máximo o de peso mínimo en un gráfico dirigido ponderado por vértice. Puede resolverse en tiempo polinomial utilizando una reducción al problema de flujo máximo.

Aplicaciones del mundo real

Eliminación de béisbol

Construcción de flujo de red para el problema de eliminación de béisbol.

En el problema de la eliminación del béisbol , hay n equipos compitiendo en una liga. En una etapa específica de la temporada de la liga, w _i es el número de victorias y r _i es el número de juegos que quedan por jugar para el equipo i y r _ij es el número de juegos que quedan contra el equipo j . Un equipo es eliminado si no tiene la oportunidad de terminar la temporada en primer lugar. La tarea del problema de eliminación del béisbol es determinar qué equipos son eliminados en cada punto durante la temporada. Schwartz propuso un método que reduce este problema al máximo flujo de red. En este método se crea una red para determinar si se elimina el equipo k .

Sea G = ( V , E ) una red con s , siendo t ∈ V la fuente y el sumidero respectivamente. Uno agrega un nodo de juego _ij , que representa el número de jugadas entre estos dos equipos. También agregamos un nodo de equipo para cada equipo y conectamos cada nodo de juego { i , j } con i < j a V , y conectamos cada uno de ellos desde s por un borde con capacidad r _ij , que representa el número de jugadas entre estos dos. equipos. También agregamos un nodo de equipo para cada equipo y conectamos cada nodo de juego { i , j } con dos nodos de equipo i y j para asegurarnos de que uno de ellos gane. No es necesario restringir el valor de flujo en estos bordes. Finalmente, los bordes se hacen desde el nodo del equipo i al nodo sumidero t y la capacidad de w _k + r _k - w _i se establece para evitar que el equipo i gane más de w _k + r _k . Sea S el conjunto de todos los equipos que participan en la liga y sea

${\ Displaystyle r (S - \ {k \}) = \ sum _ {i, j \ in \ {S - \ {k \} \} \ encima de i <j} r_ {ij}}$.

En este método se afirma equipo k no se elimina si y sólo si un valor de flujo de tamaño r ( S - { k }) existe en la red G . En el artículo mencionado se demuestra que este valor de flujo es el valor del flujo máximo de s a t .

Programación de aerolíneas

En la industria de las aerolíneas, un problema importante es la programación de las tripulaciones de vuelo. El problema de la programación de la aerolínea puede considerarse como una aplicación del flujo máximo extendido de la red. La entrada de este problema es un conjunto de vuelos F que contiene la información sobre dónde y cuándo sale y llega cada vuelo. En una versión de la programación de las aerolíneas, el objetivo es producir un programa factible con un máximo de k tripulaciones.

Para resolver este problema, se utiliza una variación del problema de circulación llamado circulación limitada, que es la generalización de los problemas de flujo de la red , con la restricción adicional de un límite inferior en los flujos de borde.

Sea G = ( V , E ) una red con s , t ∈ V como los nodos fuente y sumidero. Para la fuente y el destino de cada vuelo i , se agregan dos nodos a V , el nodo s _i como la fuente y el nodo d _i como el nodo de destino del vuelo i . También se agregan los siguientes bordes a E :

1. Una arista con capacidad [0, 1] entre sy cada s _i .
2. Una arista con capacidad [0, 1] entre cada d _i y t .
3. Una arista con capacidad [1, 1] entre cada par de s _i y d _i .
4. Un borde con capacidad [0, 1] entre cada d _i y s _j , si la fuente s _j es alcanzable con una cantidad razonable de tiempo y costo desde el destino del vuelo i .
5. Un borde con capacidad de [0, ∞ ] entre s y t .

En el método mencionado, se afirma y demostró que la búsqueda de un valor de flujo de k en G entre s y t es igual a la búsqueda de un horario factible para el vuelo establecido F con al mayoría de k tripulaciones.

Otra versión de la programación de las aerolíneas es encontrar las tripulaciones mínimas necesarias para realizar todos los vuelos. Con el fin de encontrar una respuesta a este problema, un grafo bipartito G' = ( A ∪ B , E ) se crea en cada vuelo tiene una copia en el conjunto A y el conjunto B . Si el mismo plano puede realizar vuelo j después de vuelo i , i ∈ A está conectado a j ∈ B . Una coincidencia en G ' induce un horario para F y, obviamente, la máxima coincidencia bipartita en este gráfico produce un horario de línea aérea con un número mínimo de tripulaciones. Como se menciona en la parte Aplicación de este artículo, la coincidencia bipartita de cardinalidad máxima es una aplicación del problema de flujo máximo.

Problema de circulación-demanda

Hay algunas fábricas que producen bienes y algunos pueblos donde los bienes deben entregarse. Están conectados por una red de carreteras y cada carretera tiene una capacidad c para el máximo de mercancías que pueden fluir a través de ella. El problema es encontrar si existe una circulación que satisfaga la demanda. Este problema se puede transformar en un problema de flujo máximo.

1. Agregue un nodo de origen sy agregue bordes desde él a cada nodo de fábrica f _i con capacidad p _i donde p _i es la tasa de producción de la fábrica f _i .
2. Añadir un nodo receptor, t y añadir bordes de todos los pueblos v _i a camiseta T con capacidad d _i , donde D _i es la tasa de demanda del pueblo v _i .

Sea G = ( V , E ) esta nueva red. Existe una circulación que satisface la demanda si y solo si:

Valor máximo de caudal ( G ) .${\ Displaystyle = \ sum _ {i \ in v} d_ {i}}$

Si existe una circulación, mirar la solución de flujo máximo daría la respuesta sobre la cantidad de mercancías que deben enviarse por una carretera en particular para satisfacer las demandas.

El problema se puede ampliar agregando un límite inferior al flujo en algunos bordes.

Segmentación de imagen

Imagen original de tamaño 8x8.

Red construida a partir del mapa de bits. La fuente está a la izquierda, el fregadero a la derecha. Cuanto más oscuro es un borde, mayor es su capacidad. a _i es alta cuando el píxel es verde, b _i cuando el píxel no es verde. Las penas p _ij son todas iguales.

En su libro, Kleinberg y Tardos presentan un algoritmo para segmentar una imagen. Presentan un algoritmo para encontrar el fondo y el primer plano en una imagen. Más precisamente, el algoritmo toma un mapa de bits como entrada modelada de la siguiente manera: a _i ≥ 0 es la probabilidad de que el píxel i pertenezca al primer plano, b _i ≥ 0 en la probabilidad de que el píxel i pertenezca al fondo, y p _ij es la penalización si dos píxeles adyacentes i y j se colocan uno en primer plano y el otro en el fondo. El objetivo es encontrar una partición ( A , B ) del conjunto de píxeles que maximice la siguiente cantidad

${\ Displaystyle q (A, B) = \ sum _ {i \ in A} a_ {i} + \ sum _ {i \ in B} b_ {i} - \ sum _ {\ begin {matrix} i, j {\ text {adyacente}} \\ | A \ cap \ {i, j \} | = 1 \ end {matriz}} p_ {ij}}$,

De hecho, para los píxeles en A (considerados como el primer plano), obtenemos una _i ; para todos los píxeles de B (considerados como el fondo), obtenemos b _i . En el borde, entre dos píxeles adyacentes i y j , perdemos p _ij . Equivale a minimizar la cantidad

${\ Displaystyle q '(A, B) = \ sum _ {i \ in A} b_ {i} + \ sum _ {i \ in B} a_ {i} + \ sum _ {\ begin {matrix} i, j {\ text {adyacente}} \\ | A \ cap \ {i, j \} | = 1 \ end {matriz}} p_ {ij}}$

porque

${\ Displaystyle q (A, B) = \ sum _ {i \ in A \ cup B} a_ {i} + \ sum _ {i \ in A \ cup B} b_ {i} -q '(A, B ).}$

Corte mínimo mostrado en la red (triángulos VS círculos).

Ahora construimos la red cuyos nodos son el píxel, más una fuente y un sumidero, vea la Figura a la derecha. Conectamos la fuente al píxel i por un borde de peso a _i . Conectamos el píxel i al fregadero por un borde de peso b _i . Conectamos el píxel i al píxel j con peso p _ij . Ahora, queda por calcular un corte mínimo en esa red (o equivalentemente un flujo máximo). La última figura muestra un corte mínimo.

Extensiones

1. En el problema de flujo de costo mínimo , cada borde ( u , v) también tiene un coeficiente de costo a _uv además de su capacidad. Si el flujo a través del borde es f _uv , entonces el costo total es un _uv f _uv . Se requiere encontrar un flujo de un tamaño d dado , con el menor costo. En la mayoría de las variantes, los coeficientes de costo pueden ser positivos o negativos. Existen varios algoritmos de tiempo polinomial para este problema.

2. El problema de flujo máximo puede aumentarse mediante restricciones disyuntivas : una restricción disyuntiva negativa dice que un cierto par de aristas no puede tener simultáneamente un flujo distinto de cero; una restricción disyuntiva positiva dice que, en un cierto par de aristas, al menos uno debe tener un flujo distinto de cero. Con restricciones negativas, el problema se vuelve fuertemente NP-difícil incluso para redes simples. Con restricciones positivas, el problema es polinomial si se permiten flujos fraccionarios, pero puede ser fuertemente NP-duro cuando los flujos deben ser integrales.

Referencias

Otras lecturas

• Joseph Cheriyan y Kurt Mehlhorn (1999). "Un análisis de la regla de selección de más alto nivel en el algoritmo de flujo máximo de empuje de preflujo". Cartas de procesamiento de información . 69 (5): 239–242. CiteSeerX  10.1.1.42.8563 . doi : 10.1016 / S0020-0190 (99) 00019-8 .
• Daniel D. Sleator y Robert E. Tarjan (1983). "Una estructura de datos para árboles dinámicos" (PDF) . Revista de Ciencias de la Computación y Sistemas . 26 (3): 362–391. doi : 10.1016 / 0022-0000 (83) 90006-5 . ISSN  0022-0000 .
• Eugene Lawler (2001). "4. Flujos de red". Optimización combinatoria: redes y matroides . Dover. págs. 109-177. ISBN 978-0-486-41453-9.