Problema de flujo máximo

Problema computacional en teoría de grafos

Red de flujo para el problema: cada 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 solo por un subconjunto de los humanos. Encuentre cualquier coincidencia de mascotas con humanos de modo que la mayor cantidad de mascotas sean adoptadas por uno de sus humanos preferidos.

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

El problema del 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, flujo desde la fuente s hasta el sumidero t) es igual a la capacidad mínima de un corte st (es decir, corte que separa s de t) en la red, como se indica en el teorema de flujo máximo y corte mínimo .

Historia

El problema del 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. ^{[1] [2] [3]}

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

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

En su libro Flows in Network , ^[5] 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 (retirado), había formulado un modelo simplificado del 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 la red ferroviaria de Harris y Ross ^[3] (véase ^[1] pág. 5).

A lo largo de los años, se descubrieron varias soluciones mejoradas al problema del flujo máximo, en particular el algoritmo de ruta de aumento más corta de Edmonds y Karp e independientemente de Dinitz; el algoritmo de flujo de bloqueo de Dinitz; el algoritmo push-relabel de Goldberg y Tarjan ; y el algoritmo de flujo de bloqueo binario de Goldberg y Rao. Los algoritmos de Sherman ^[6] y Kelner, Lee, Orecchia y Sidford, ^{[7] [8]} respectivamente, encuentran un flujo máximo aproximadamente óptimo pero solo funcionan en grafos no dirigidos.

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

En 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg y Sushant Sachdeva publicaron un algoritmo de tiempo casi lineal que se ejecuta en el problema de flujo de costo mínimo , del cual el problema de flujo máximo es un caso particular. ^{[10] [11]} Para el problema de la ruta más corta de una sola fuente (SSSP) con pesos negativos, también se ha informado de otro caso particular de problema de flujo de costo mínimo: un algoritmo en tiempo casi lineal. ^{[12] [13] Ambos algoritmos fueron considerados los mejores artículos en el} Simposio sobre Fundamentos de la Ciencia de la Computación de 2022. ^{[14] [15]} ${\displaystyle O(|E|^{1+o(1)})}$

Definición

Una red de flujo, con fuente s y sumidero t . Los números junto a los bordes son las capacidades.

Primero establecemos alguna notación:

• Sea una red con siendo la fuente y el sumidero de respectivamente. ${\displaystyle N=(V,E)}$ ${\displaystyle s,t\in V}$ ${\displaystyle N}$
• Si es una 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 cumple con lo siguiente: ${\displaystyle f:E\to \mathbb {R} }$

• Restricción de capacidad . El flujo de un borde no puede exceder su capacidad, en otras palabras: para todos ${\displaystyle f_{uv}\leq c_{uv}}$ ${\displaystyle (u,v)\in E.}$
• Conservación de flujos. La suma de los flujos que entran en un nodo debe ser igual a la suma de los flujos que salen de ese nodo, excepto el de origen y el de destino. O bien:

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

Observación . Los flujos son asimétricos: para todos ${\displaystyle f_{uv}=-f_{vu}}$ ${\displaystyle (u,v)\in E.}$

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

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

Definición. El problema del caudal máximo consiste en dirigir la mayor cantidad de caudal posible desde la fuente hasta el sumidero, es decir, encontrar el caudal con valor máximo. ${\displaystyle f_{\textrm {max}}}$

Obsérvese que pueden existir varios caudales máximos y, si se permiten valores reales arbitrarios (o incluso racionales arbitrarios) de caudal (en lugar de solo números enteros), existe exactamente un caudal máximo o infinitos, ya que existen infinitas combinaciones lineales de los caudales máximos de base. En otras palabras, si enviamos unidades de caudal en el borde en un caudal máximo y unidades de caudal en en otro caudal máximo, entonces para cada uno podemos enviar unidades en y enrutar el flujo en los bordes restantes en consecuencia, para obtener otro caudal máximo. Si los valores de caudal pueden ser cualquier número real o racional, entonces existen infinitos valores de este tipo para cada par . ${\displaystyle x}$ ${\displaystyle u}$ ${\displaystyle y>x}$ ${\displaystyle u}$ ${\displaystyle \Delta \in [0,y-x]}$ ${\displaystyle x+\Delta }$ ${\displaystyle u}$ ${\displaystyle \Delta }$ ${\displaystyle x,y}$

Algoritmos

La siguiente tabla enumera algoritmos para resolver el problema de flujo máximo. Aquí, y denotan el número de vértices y aristas de la red. El valor se refiere a la capacidad de arista más grande después de reescalar todas las capacidades a valores enteros (si la red contiene capacidades irracionales , puede ser infinita). ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle U}$ ${\displaystyle U}$

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

Teorema de flujo integral

El teorema de flujo integral establece que

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

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

Solicitud

Problema de caudal 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 una sola fuente y un solo sumidero

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 de . Podemos transformar el problema de múltiples fuentes y 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 supersumidero ) con capacidad infinita en cada borde (ver Figura 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 , debemos encontrar una correspondencia de cardinalidad máxima en , es decir, una correspondencia que contenga el mayor número posible de aristas. Este problema se puede transformar en un problema de flujo máximo construyendo 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 dirección desde a . ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle Y}$
2. ${\displaystyle (s,x)\in E'}$para cada uno y para cada . ${\displaystyle x\in X}$ ${\displaystyle (y,t)\in E'}$ ${\displaystyle y\in Y}$
3. ${\displaystyle c(e)=1}$para cada uno (ver figura 4.3.1). ${\displaystyle e\in E'}$

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

Recorrido mínimo de la trayectoria en un gráfico acíclico dirigido

Dado un grafo acíclico dirigido , debemos encontrar el número mínimo de caminos disjuntos en sus vértices para cubrir cada vértice en . Podemos construir un grafo 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{ has outgoing edge(s)}}\}}$
2. ${\displaystyle V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has incoming edge(s)}}\}}$
3. ${\displaystyle E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}$.

Entonces se puede demostrar que tiene una coincidencia de tamaño si y solo si tiene una cubierta de caminos disjuntos en vértices que contiene aristas y caminos, donde es el número de vértices en . Por lo tanto, el problema se puede resolver encontrando la coincidencia de cardinalidad máxima en en su lugar. ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle n-m}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle G'}$

Supongamos que hemos encontrado una coincidencia de , y hemos construido la cubierta a partir de ella. Intuitivamente, si dos vértices coinciden en , entonces la arista está contenida en . Claramente, el número de aristas en es . Para ver que es disjunto en cuanto a vértices, considere lo siguiente: ${\displaystyle M}$ ${\displaystyle G'}$ ${\displaystyle C}$ ${\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 hay aristas que salgan en ; o puede coincidir en , en cuyo caso hay exactamente una arista que sale en . En cualquier caso, no más de una arista sale de ningún vértice en . ${\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 único borde entrante en en ; de lo contrario, no tiene bordes entrantes en . ${\displaystyle v_{\textrm {in}}}$ ${\displaystyle G'}$ ${\displaystyle v}$ ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle C}$

Por lo tanto, ningún vértice tiene dos aristas entrantes o dos salientes en , lo que significa que todos los caminos en son disjuntos en sus vértices. ${\displaystyle C}$ ${\displaystyle C}$

Para demostrar que la cubierta tiene un 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 que comience en ese vértice. El primer caso es aplicable siempre que y alguna ruta en la cubierta comience en , o y alguna ruta termine en . El último caso es siempre aplicable. En el primer caso, el número total de aristas en la cubierta se incrementa en 1 y el número de rutas permanece igual; en el último caso, el número de rutas 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 rutas y aristas en la cubierta es . Por lo tanto, si el número de aristas en la cubierta es , el número de rutas es . ${\displaystyle C}$ ${\displaystyle n-m}$ ${\displaystyle u}$ ${\displaystyle (u,v)\in E}$ ${\displaystyle v}$ ${\displaystyle (v,u)\in E}$ ${\displaystyle v}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n-m}$

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. Supongamos que en cada nodo existe capacidad además de la capacidad de los bordes, es decir, una asignación tal que el flujo debe satisfacer no solo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad de los vértices. ${\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 a través de un vértice no puede exceder su capacidad. Para encontrar el flujo máximo a través de , podemos transformar el problema en el problema de flujo máximo en el sentido original expandiendo . Primero, cada uno se reemplaza por y , donde está conectado por aristas que entran y está conectado a aristas que salen de , luego asigna capacidad a la arista que conecta y (ver Fig. 4.4.1). En esta red expandida, se elimina la restricción de capacidad del vértice 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{in}}}$ ${\displaystyle v_{\text{out}}}$ ${\displaystyle v_{\text{in}}}$ ${\displaystyle v}$ ${\displaystyle v_{\text{out}}}$ ${\displaystyle v}$ ${\displaystyle c(v)}$ ${\displaystyle v_{\text{in}}}$ ${\displaystyle v_{\text{out}}}$

Número máximo de caminos de s a t

Dado un grafo dirigido y dos vértices y , debemos hallar el número máximo de caminos desde hasta . Este problema tiene varias variantes: ${\displaystyle G=(V,E)}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$

1. Los caminos deben estar separados por aristas. Este problema se puede transformar en un problema de flujo máximo construyendo una red a partir de , donde y son la fuente y el sumidero de respectivamente, y asignando a cada arista una capacidad de . En esta red, el flujo máximo es si y solo si hay caminos separados por aristas. ${\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 en sus vértices (excepto y ). Podemos construir una red a partir de con capacidades de vértice, donde las capacidades de todos los vértices y todas las aristas son . Entonces el valor del flujo máximo es igual al número máximo de caminos independientes desde hasta . ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle N=(V,E)}$ ${\displaystyle G}$ ${\displaystyle 1}$ ${\displaystyle s}$ ${\displaystyle t}$

3. Además de que los caminos no tienen aristas unidas o vértices unidas, también tienen una restricción de longitud: contamos solo los caminos cuya longitud sea exactamente , o como máximo . La mayoría de las variantes de este problema son NP-completas, excepto para valores pequeños de . ^[27] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Problema de cierre

Un cierre de un grafo dirigido es un conjunto de vértices C , de modo que ninguna arista salga de C . El problema de cierre es la tarea de encontrar el cierre de peso máximo o peso mínimo en un grafo dirigido ponderado por vértices. Puede resolverse en tiempo polinómico utilizando una reducción al problema de flujo máximo.

Aplicaciones en el mundo real

Eliminatoria del béisbol

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

En el problema de 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 ninguna posibilidad 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 ^[28] propuso un método que reduce este problema al flujo máximo de red. En este método se crea una red para determinar si el equipo k es eliminado.

Sea G = ( V , E ) una red con s , t ∈ V siendo la fuente y el sumidero respectivamente. Se 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 asegurar que uno de ellos gane. No es necesario restringir el valor del flujo en estos bordes. Finalmente, se crean bordes desde el nodo de equipo i hasta el nodo sumidero t y se establece la capacidad de w _k + r _k – w _i 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\}\} \atop i<j}r_{ij}}$.

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

Programación de vuelos

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 vuelos puede considerarse como una aplicación del flujo máximo de red extendido. 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 vuelos, 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 llamada circulación limitada, que es la generalización de los problemas de flujo de 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 nodos de origen y destino. Para el origen y el destino de cada vuelo i , se suman dos nodos a V , el nodo s _i como origen y el nodo d _i como nodo de destino del vuelo i . También se suman las siguientes aristas a E :

1. Un borde con capacidad [0, 1] entre s y cada s _i .
2. Un borde 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 de tiempo y un costo razonables desde el destino del vuelo i .
5. Una arista con capacidad [0, ∞ ] entre s y t .

En el método mencionado, se afirma y demuestra que encontrar un valor de flujo de k en G entre s y t es igual a encontrar un programa factible para el conjunto de vuelos F con un máximo de k tripulaciones. ^[29]

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

Problema circulación-demanda

Existen algunas fábricas que producen bienes y algunos pueblos a los que se deben entregar los bienes. Están conectados por una red de carreteras, cada una de las cuales tiene una capacidad c para el máximo de bienes que pueden circular por 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 s y agregue aristas 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. Agregue un nodo sumidero t y agregue aristas de todas las aldeas v _i a t con capacidad d _i donde d _i es la tasa de demanda de la aldea v _i .

Sea G = ( V , E ) esta nueva red. Existe una circulación que satisface la demanda si y sólo 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 de cuántas mercancías deben enviarse por una ruta particular para satisfacer las demandas.

El problema se puede ampliar añadiendo un límite inferior al flujo en algunos bordes. ^[30]

Segmentación de imágenes

Imagen de origen de tamaño 8x8.

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

En su libro, Kleinberg y Tardos presentan un algoritmo para segmentar una imagen. ^[32] 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 modelado 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 el 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{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}$,

En efecto, para los píxeles de A (considerados como primer plano), ganamos a _i ; para todos los píxeles de B (considerados como el fondo), ganamos b _i . En el borde, entre dos píxeles adyacentes i y j , perdemos p _ij . Es equivalente 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{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}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, ver Figura a la derecha. Conectamos la fuente al píxel i mediante un borde de peso a _i . Conectamos el píxel i al sumidero mediante un borde de peso b _i . Conectamos el píxel i al píxel j con peso p _ij . Ahora, queda 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 arista ( u _, v) también tiene un coeficiente _de costo auv además de su capacidad. Si el flujo a través de la arista es fuv , entonces el costo total es auv _fuv . Se requiere encontrar un flujo de un tamaño dado d , 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 del flujo máximo puede ampliarse con 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 una 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-difícil cuando los flujos deben ser integrales. ^[33]

Referencias

1. Schrijver, A. (2002). "Sobre la historia de los problemas de transporte y flujo máximo". Programación matemática . 91 (3): 437–445. CiteSeerX  10.1.1.23.5134 . doi :10.1007/s101070100259. S2CID  10210675.
2. Gass, Saul I.; Assad, Arjang A. (2005). "Desarrollos matemáticos, algorítmicos y profesionales de la investigación de operaciones de 1951 a 1956". Una cronología anotada de la investigación de operaciones . Serie internacional en investigación de operaciones y ciencia de la gestión. Vol. 75. págs. 79–110. doi :10.1007/0-387-25837-X_5. ISBN 978-1-4020-8116-3.
3. Harris, TE ; Ross, FS (1955). "Fundamentos de un método para evaluar las capacidades de la red ferroviaria" (PDF) . Memorándum de investigación . Archivado desde el original (PDF) el 8 de enero de 2014.
4. Ford, LR ; Fulkerson, DR (1956). "Flujo máximo a través de una red". Revista Canadiense de Matemáticas . 8 : 399–404. doi : 10.4153/CJM-1956-045-5 .
5. Ford, LR, Jr.; Fulkerson, DR, Flujos en redes , Princeton University Press (1962).
6. Sherman, Jonah (2013). "Flujos casi máximos en tiempo casi lineal". Actas del 54.º Simposio anual IEEE sobre fundamentos de la informática . pp. 263–269. arXiv : 1304.2077 . doi :10.1109/FOCS.2013.36. ISBN . 978-0-7695-5135-7.S2CID14681906  .​
7. Kelner, JA; Lee, YT; Orecchia, L.; Sidford, A. (2014). "Un algoritmo de tiempo casi lineal para el flujo máximo aproximado en gráficos no dirigidos y sus generalizaciones multiproducto" (PDF) . Actas del vigésimo quinto simposio anual ACM-SIAM sobre algoritmos discretos . pág. 217. arXiv : 1304.2338 . doi :10.1137/1.9781611973402.16. ISBN . 978-1-61197-338-9. S2CID  10733914. Archivado desde el original (PDF) el 3 de marzo de 2016.
8. Knight, Helen (7 de enero de 2014). «Un nuevo algoritmo puede simplificar drásticamente las soluciones al problema del «flujo máximo». MIT News . Consultado el 8 de enero de 2014 .
9. Orlin, James B. (2013). "Max flow in O(nm) time, or better" (Flujos máximos en tiempo O(nm), o mejor). Actas del cuadragésimo quinto simposio anual de la ACM sobre teoría de la computación . págs. 765–774. CiteSeerX 10.1.1.259.5759 . doi :10.1145/2488608.2488705. ISBN.  9781450320290.S2CID207205207  .​
10. Chen, L.; Kyng, R.; Liu, YP; Gutenberg, MP; Sachdeva, S. (2022). "Flujo máximo y flujo de costo mínimo en tiempo casi lineal". arXiv : 2203.00671 [cs.DS].
11. Klarreich, Erica (8 de junio de 2022). "Investigadores logran un algoritmo 'absurdamente rápido' para el flujo de red". Quanta Magazine . Consultado el 8 de junio de 2022 .
12. Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (30 de octubre de 2022). "Caminos más cortos de una sola fuente con peso negativo en tiempo casi lineal". arXiv : 2203.03456 [cs.DS].
13. Brubaker, Ben (18 de enero de 2023). "Finalmente, un algoritmo rápido para caminos más cortos en gráficos negativos". Quanta Magazine . Consultado el 25 de enero de 2023 .
14. "FOCS 2022". focs2022.eecs.berkeley.edu . Consultado el 25 de enero de 2023 .
15. Santosh, Nagarakatte. "Premio al mejor artículo de FOCS 2022 para el artículo del profesor Aaron Bernstein". www.cs.rutgers.edu . Consultado el 25 de enero de 2023 .
16. 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) . Information Processing Letters . 7 (6): 277–278. doi :10.1016/0020-0190(78)90016-9.
17. Goldberg, AV ; Tarjan, RE (1988). "Un nuevo enfoque para el problema del flujo máximo". Revista de la ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID  52152408.
18. Cheriyan, J.; Maheshwari, SN (1988). "Análisis de algoritmos de empuje de preflujo para el flujo máximo de red". Fundamentos de tecnología de software y ciencia informática teórica . Apuntes de clase en informática. Vol. 338. págs. 30–48. doi :10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4. ISSN  0302-9743.
19. King, V.; Rao, S.; Tarjan, R. (1994). "Un algoritmo de flujo máximo determinista más rápido". Journal of Algorithms . 17 (3): 447–474. doi :10.1006/jagm.1994.1044. S2CID  15493.
20. Goldberg, AV ; Rao, S. (1998). "Más allá de la barrera de descomposición del flujo". Revista de la ACM . 45 (5): 783. doi : 10.1145/290179.290181 . S2CID  96030.
21. Kathuria, T.; Liu, YP; Sidford, A. (16-19 de noviembre de 2020). Capacidad unitaria Maxflow in Almost Time . Durham, NC, EE. UU.: IEEE. págs. 119-130. ${\displaystyle O(m^{4/3})}$
22. Madry, Aleksander (9–11 de octubre de 2016). Cálculo del caudal máximo con aumento de caudales eléctricos . New Brunswick, New Jersey: IEEE. pp. 593–602.
23. Marca, J. vd; Lee, YT; Nanongkai, D.; Peng, R.; Saranurak, T.; Sidford, A.; Canción, Z.; Wang, D. (16 a 19 de noviembre de 2020). "Emparejamiento bipartito en tiempo casi lineal en gráficos moderadamente densos" . Durham, Carolina del Norte, Estados Unidos: IEEE. págs. 919–930.
24. Brand, J. vd; Lee, YT; Liu, YP; Saranurak, T.; Sidford, A; Song, Z.; Wang, D. (2021). "Flujos de costos mínimos, MDP y regresión ℓ1 en tiempo casi lineal para instancias densas". arXiv : 2101.05719 [cs.DS].
25. Gao, Y.; Liu, YP; Peng, R. (2021). "Flujos eléctricos completamente dinámicos: flujo máximo disperso más rápido que Goldberg-Rao". arXiv : 2101.07233 [cs.DS].
26. Bernstein, A.; Blikstad, J.; Saranurak, T.; Tu, T. (2024). "Flujo máximo aumentando las rutas en el tiempo". arXiv : 2406.03648 [cs.DS]. ${\displaystyle n^{2+o(1)}}$
27. Itai, A.; Perl, Y.; Shiloach, Y. (1982). "La complejidad de encontrar caminos máximos disjuntos con restricciones de longitud". Redes . 12 (3): 277–286. doi :10.1002/net.3230120306. ISSN  1097-0037.
28. Schwartz, BL (1966). "Posibles ganadores en torneos parcialmente completados". SIAM Review . 8 (3): 302–308. Bibcode :1966SIAMR...8..302S. doi :10.1137/1008062. JSTOR  2028206.
29. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001). "26. Maximum Flow". Introducción a los algoritmos, segunda edición . MIT Press y McGraw-Hill. págs. 643–668. ISBN 978-0-262-03293-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
30. Carl Kingsford. "Extensiones de caudal máximo: circulaciones con demandas" (PDF) .
31. "Proyecto imagesegmentationwithmaxflow, que contiene el código fuente para producir estas ilustraciones". GitLab . Archivado desde el original el 22 de diciembre de 2019 . Consultado el 22 de diciembre de 2019 .
32. "Diseño de algoritmos". pearson.com . Consultado el 21 de diciembre de 2019 .
33. Schauer, Joachim; Pferschy, Ulrich (1 de julio de 2013). "El problema del flujo máximo con restricciones disyuntivas". Journal of Combinatorial Optimization . 26 (1): 109–119. CiteSeerX 10.1.1.414.4496 . doi :10.1007/s10878-011-9438-7. ISSN  1382-6905. S2CID  6598669. 

Lectura adicional

• Joseph Cheriyan y Kurt Mehlhorn (1999). "Análisis de la regla de selección de nivel más alto en el algoritmo de flujo máximo de preflujo-empuje". Information Processing Letters . 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 de 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.