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 (pi ) tiene preferencia solo por un subconjunto de humanos. Encuentre cualquier coincidencia de mascotas con humanos de modo que uno de sus humanos preferidos adopte el número máximo de mascotas.

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

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):

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 estacionario, encuentre un flujo máximo de una ciudad dada a la otra.

En su libro Flows in Network , ^[5] en 1962, Ford y Fulkerson escribieron:

Se lo planteó a los autores en la primavera de 1955 TE Harris, quien, junto con el general FS Ross (retirado), había formulado un modelo simplificado de flujo de tráfico ferroviario y había señalado 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 netas ferroviarias de Harris y Ross ^[3] (ver ^[1] p. 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 corto de Edmonds y Karp y, de forma independiente, Dinitz; el algoritmo de bloqueo de flujo 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 sólo 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 para 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 del camino más corto de fuente única (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 informática de 2022 . ^{[14] [15]} ${\displaystyle O(|E|^{1+o(1)})}$

Definición

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

Primero establecemos alguna notación:

• Sea una red siendo la fuente y el sumidero 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 satisface lo siguiente: ${\displaystyle f:E\to \mathbb {R} }$

• Restricció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)\in 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}>0}f_{uv}=\sum _{u:(v,u)\in E,f_{vu}>0}f_{vu}.}$

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

Definición. El valor del flujo es la cantidad de flujo que pasa desde 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}=\sum _{u:\ (u,t)\in E}f_{ut}.}$

Definición. El problema del flujo máximo es encaminar la mayor cantidad de flujo posible desde la fuente al 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 reales arbitrarios (o incluso racionales arbitrarios) (en lugar de sólo números enteros), hay exactamente un flujo máximo, o infinitos, ya que hay infinitas combinaciones lineales de flujos máximos. los caudales máximos 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 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 denota el número de vértices y aristas de la red. El valor se refiere a la capacidad de borde 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 del flujo integral

El teorema del 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 número entero, lo que se deriva directamente del teorema del corte mínimo del 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

Figura 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 una sola 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 y un sumidero consolidado conectado por cada vértice (también conocido como superfuente y supersumidero ) con capacidad infinita en cada borde ( Ver 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

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

Dado un gráfico bipartito , debemos encontrar una coincidencia de cardinalidad máxima en , es decir, una coincidencia que contiene 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 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 (Ver Fig. 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}$

Cobertura mínima de ruta 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értices 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{ 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\}}$.

Luego se puede demostrar que tiene una coincidencia de tamaño si y solo si tiene una cobertura de ruta disjunta de vértice que contiene bordes y rutas, donde es el número de vértices en . Por lo tanto, el problema se puede resolver encontrando la cardinalidad máxima que coincida . ${\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 construimos la portada a partir de ella. Intuitivamente, si dos vértices coinciden en , entonces el borde está contenido en . Claramente el número de aristas es . Para ver que es un vértice disjunto, 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 cuyo caso sale exactamente un borde . En cualquier caso, no más de una arista sale de cualquier 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 una única arista entrante en ; de lo contrario no tiene bordes entrantes . ${\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 separados de vértices. ${\displaystyle C}$ ${\displaystyle C}$

Para mostrar que la portada tiene tamaño , comenzamos con una portada vacía y la construimos de forma incremental. Para agregar un vértice a la portada, podemos agregarlo a un camino existente o crear un nuevo camino de longitud cero comenzando en ese vértice. El primer caso es aplicable siempre que alguna ruta en la portada comience en o alguna ruta termine en . Este último caso siempre es aplicable. En el primer caso, el número total de aristas de la cubierta aumenta en 1 y el número de caminos permanece igual; en el último caso, el número de caminos 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 aristas en la portada es , el número de caminos 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

Figura 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 hay capacidad en cada nodo además de la capacidad de borde, es decir, un mapeo tal que el flujo tiene que satisfacer no sólo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad de 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 , 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 los bordes que entran y está conectado con los bordes que salen de , luego asigna capacidad al borde que conecta y (ver Fig. 4.4.1). En esta red expandida, la restricción de capacidad del 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{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 gráfico dirigido y dos vértices y , debemos encontrar 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 de los bordes. Este problema se puede transformar en un problema de flujo máximo construyendo una red desde , siendo y 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 caminos de borde disjunto. ${\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, separados por vértices (excepto y ). Podemos construir una red con capacidades de vértices, donde las capacidades de todos los vértices y todas las aristas son . Entonces el valor del caudal 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 son disjuntos en los bordes y/o en los vértices, los caminos también tienen una restricción de longitud: solo contamos los caminos cuya longitud es exactamente , o como máximo . La mayoría de las variantes de este problema son NP-completas, excepto valores pequeños de . ^[26] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Problema de cierre

Un cierre de un gráfico dirigido es un conjunto de vértices C , tal que ninguna arista sale de C . El problema de cierre es la tarea de encontrar el cierre de peso máximo o mínimo en un gráfico dirigido ponderado por vértices. 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 problema de eliminación de béisbol.

En el problema de eliminación de 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 queda eliminado si no tiene posibilidades 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 de la temporada. Schwartz ^[27] propuso un método que reduce este problema al flujo máximo de la red. En este método se crea una red para determinar si el equipo k es eliminado.

Sea G = ( V , E ) una red en la que s , t ∈ V sea 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 conecta 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 hacen bordes desde el nodo del equipo _i hasta el nodo sumidero t y la capacidad de w _k + r _k – wi 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\}\} \atop i<j}r_{ij}}$.

En este método se afirma que el equipo k no se elimina si y sólo 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 de s a t .

programación de aerolíneas

En la industria aérea un problema importante es la programación de las tripulaciones de vuelo. El problema de programación de líneas aéreas 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 información sobre dónde y cuándo sale y llega cada vuelo. En una versión de programación de líneas aéreas, el objetivo es producir un horario factible con como máximo k tripulaciones.

Para resolver este problema se utiliza una variación del problema de circulación llamada circulación acotada, 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 fuente y sumidero. Para el origen y el destino de cada vuelo i , se agregan dos nodos a V , el nodo s _i como origen y el nodo d _i como nodo destino del vuelo i . También se agregan 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. Un borde 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 accesible en un tiempo y 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 horario factible para el conjunto de vuelos F con como máximo k tripulaciones. ^[28]

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 gráfico 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 horario para F y, obviamente, la máxima coincidencia bipartita en este gráfico produce un horario de aerolínea con un número mínimo de tripulaciones. ^[28] 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 de circulación-demanda

Hay algunas fábricas que producen bienes y algunas aldeas donde se deben entregar los bienes. Están conectados por una red de caminos y cada camino tiene una capacidad c para el máximo de mercancías que pueden fluir a través de él. 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 bordes desde él a cada nodo de fábrica fi con capacidad p _i donde p _i es la tasa de producción de _la fábrica fi _.
2. Agregue un nodo sumidero t y agregue bordes de todas las aldeas v _i a t con capacidad d _i donde d _i es la tasa de demanda de la aldea vi _.

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

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

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

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

Segmentación de imagen

Imagen de origen 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 alto cuando el píxel es verde, b _i cuando el píxel no es verde. Las penas p _ij son todas iguales. ^[30]

Kleinberg y Tardos presentan en su libro un algoritmo para segmentar una imagen. ^[31] 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 el penalización si dos píxeles adyacentes i y j se colocan uno en primer plano y el otro en segundo plano. 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}}$,

De hecho, para los píxeles en A (considerados como primer plano), obtenemos a _i ; para todos los píxeles en B (considerados como fondo), _ganamos bi . En el borde, entre dos píxeles adyacentes i y j , soltamos 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{ 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, consulte la figura de la derecha. Conectamos la fuente al píxel i por un borde de peso a _i . Conectamos el píxel i al sumidero por 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 del borde es f _uv , entonces el costo total es a _uv f _uv . 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 costos pueden ser positivos o negativos. Existen varios algoritmos de tiempo polinomial para este problema.

2. El problema del flujo máximo puede verse aumentado por restricciones disyuntivas : una restricción disyuntiva negativa dice que un cierto par de aristas no pueden tener simultáneamente un flujo distinto de cero; Una restricción disyuntiva positiva dice que, en un determinado 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 polinómico si se permiten flujos fraccionarios, pero puede ser fuertemente NP-difícil cuando los flujos deben ser integrales. ^[32]

Referencias

1. Schrijver, A. (2002). "Sobre la historia del transporte y los problemas de 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, Saúl I.; Assad, Arjang A. (2005). "Desarrollos matemáticos, algorítmicos y profesionales de la investigación operativa de 1951 a 1956". Una cronología comentada de la investigación de operaciones . Serie internacional en investigación de operaciones y ciencias 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) . Memorando 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, Jonás (2013). "Flujos casi máximos en tiempo casi lineal". Actas del 54º Simposio anual del IEEE sobre fundamentos de la informática . págs. 263–269. arXiv : 1304.2077 . doi :10.1109/FOCS.2013.36. ISBN 978-0-7695-5135-7. S2CID  14681906.
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 de múltiples productos" (PDF) . Actas del vigésimo quinto simposio anual ACM-SIAM sobre algoritmos discretos . pag. 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). "El nuevo algoritmo puede simplificar drásticamente las soluciones al problema del 'flujo máximo'". Noticias del MIT . Consultado el 8 de enero de 2014 .
9. Orlin, James B. (2013). "Flujos máximos en tiempo O (nm), o mejor". Actas del cuadragésimo quinto simposio anual de 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. S2CID  207205207.
10. Chen, L.; Kyng, R.; Liu, YP; Gutenberg, diputado; 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). "Los investigadores logran un algoritmo 'absurdamente rápido' para el flujo de red". Revista Quanta . Consultado el 8 de junio de 2022 .
12. Bernstein, Aarón; Nanongkai, Danupon; Wulff-Nilsen, Christian (30 de octubre de 2022). "Rutas más cortas de fuente única de 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". Revista Quanta . 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 FOCS 2022 al mejor artículo por 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) . Cartas de procesamiento de información . 7 (6): 277–278. doi :10.1016/0020-0190(78)90016-9.
17. Goldberg, AV ; Tarjan, RE (1988). "Un nuevo enfoque al 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 push de preflujo para máximo flujo de red". Fundamentos de la tecnología del software y la informática teórica . Apuntes de conferencias sobre 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. Rey, V.; Rao, S.; Tarjan, R. (1994). "Un algoritmo de flujo máximo determinista más rápido". Revista de algoritmos . 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. Katuria, T.; Liu, YP; Sidford, A. (16 a 19 de noviembre de 2020). Capacidad unitaria Maxflow en casi tiempo . Durham, Carolina del Norte, Estados Unidos: IEEE. págs. 119-130. ${\displaystyle O(m^{4/3})}$
22. Madry, Aleksander (9 a 11 de octubre de 2016). Cálculo del flujo máximo con flujos eléctricos crecientes . Nuevo Brunswick, Nueva Jersey: IEEE. págs. 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. Marca, J. vd; Lee, YT; Liu, YP; Saranurak, T.; Sidford, A; Canción, 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 totalmente dinámicos: flujo máximo disperso más rápido que Goldberg-Rao". arXiv : 2101.07233 [cs.DS].
26. Itai, A.; Perl, Y.; Siloaj, 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.
27. Schwartz, BL (1966). "Posibles ganadores en torneos parcialmente completados". Revisión SIAM . 8 (3): 302–308. Código bibliográfico : 1966SIAMR...8..302S. doi :10.1137/1008062. JSTOR  2028206.
28. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001). "26. Caudal máximo". 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)
29. Carl Kingsford. «Extensiones Max-flow: circulaciones con demandas» (PDF) .
30. "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 .
31. "Diseño de algoritmos". pearson.com . Consultado el 21 de diciembre de 2019 .
32. Schauer, Joaquín; Pferschy, Ulrich (1 de julio de 2013). "El problema del flujo máximo con restricciones disyuntivas". Revista de optimización combinatoria . 26 (1): 109–119. CiteSeerX 10.1.1.414.4496 . doi :10.1007/s10878-011-9438-7. ISSN  1382-6905. S2CID  6598669. 

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 preflujo-empuje". 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 de Sistemas . 26 (3): 362–391. doi :10.1016/0022-0000(83)90006-5. ISSN  0022-0000.
• Eugenio Lawler (2001). "4. Flujos de red". Optimización combinatoria: redes y matroides . Dover. págs. 109-177. ISBN 978-0-486-41453-9.