Problema de flujo máximo

Un algoritmo de tiempo fuertemente polinomial tiene límites de tiempo polinomiales que dependen solo del número de entradas, pero no de la magnitud de estos números. Aquí, las entradas son los vértices (numerados a continuación como${\displaystyle V}$) y bordes (numerados como${\displaystyle E}$). La complejidad de cada algoritmo se expresa utilizando la notación O grande .

Paralelamente al desarrollo de algoritmos de flujo fuertemente polinomiales, ha habido una larga línea de límites de tiempo pseudopolinomiales y débilmente polinomiales, cuyo tiempo de ejecución depende de la magnitud de las capacidades de entrada. Aquí, el valor${\displaystyle U}$Se refiere a la mayor capacidad de arista después de reescalar todas las capacidades a valores enteros . (Si la red contiene capacidades irracionales , este reescalado puede no ser posible y estos algoritmos pueden no producir soluciones exactas o pueden no converger incluso a una solución aproximada). La diferencia entre pseudopolinomio y débilmente polinomial es que una cota pseudopolinomial puede ser polinomial en ${\displaystyle U}$, pero para una cota débilmente polinómica puede ser polinómica solo en${\displaystyle \log U}$.

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

Dado un grafo bipartito${\displaystyle G=(X\cup Y,E)}$, debemos encontrar un emparejamiento de cardinalidad máxima en${\displaystyle G}$, es decir, un emparejamiento 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.${\displaystyle N=(X\cup Y\cup \{s,t\},E')}$, dónde

1. ${\displaystyle E'}$contiene los bordes en${\displaystyle G}$dirigido desde${\displaystyle X}$a${\displaystyle Y}$.
2. ${\displaystyle (s,x)\in E'}$para cada${\displaystyle x\in X}$y${\displaystyle (y,t)\in E'}$para cada${\displaystyle y\in Y}$.
3. ${\displaystyle c(e)=1}$para cada${\displaystyle e\in E'}$(Véase la figura 4.3.1).

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

Dado un grafo dirigido acíclico${\displaystyle G=(V,E)}$, debemos encontrar el número mínimo de caminos disjuntos en vértices para cubrir cada vértice en${\displaystyle V}$Podemos construir un grafo bipartito.${\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}$de${\displaystyle G}$, dónde

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${\displaystyle G'}$tiene un juego${\displaystyle M}$de tamaño${\displaystyle m}$si y solo si${\displaystyle G}$tiene una cobertura de caminos disjuntos en vértices${\displaystyle C}$que contiene${\displaystyle m}$bordes y${\displaystyle n-m}$senderos, donde${\displaystyle n}$es el número de vértices en${\displaystyle G}$Por lo tanto, el problema se puede resolver encontrando el emparejamiento de cardinalidad máxima en${\displaystyle G'}$en cambio.

Supongamos que hemos encontrado una coincidencia${\displaystyle M}$de${\displaystyle G'}$y construyó la portada${\displaystyle C}$de ello. Intuitivamente, si dos vértices${\displaystyle u_{\mathrm {out} },v_{\mathrm {in} }}$se emparejan en${\displaystyle M}$, luego el borde${\displaystyle (u,v)}$está contenido en${\displaystyle C}$. Claramente el número de aristas en${\displaystyle C}$es${\displaystyle m}$Para ver eso${\displaystyle C}$Si son disjuntos en vértices, considere lo siguiente:

1. Cada vértice${\displaystyle v_{\textrm {out}}}$en${\displaystyle G'}$puede no coincidir en${\displaystyle M}$, en cuyo caso no quedan bordes que salgan${\displaystyle v}$en${\displaystyle C}$; o puede coincidir , en cuyo caso queda exactamente una arista.${\displaystyle v}$en${\displaystyle C}$En cualquier caso, no más de una arista sale de ningún vértice.${\displaystyle v}$en${\displaystyle C}$.
2. De manera similar para cada vértice${\displaystyle v_{\textrm {in}}}$en${\displaystyle G'}$– si coincide, hay un único borde entrante${\displaystyle v}$en${\displaystyle C}$; de lo contrario${\displaystyle v}$no tiene aristas entrantes en${\displaystyle C}$.

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

Para demostrar que la portada${\displaystyle C}$tiene tamaño${\displaystyle n-m}$, comenzamos con una cubierta vacía y la construimos incrementalmente. Para agregar un vértice${\displaystyle u}$Para la cubierta, podemos agregarla 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${\displaystyle (u,v)\in E}$y algún camino en la portada comienza en${\displaystyle v}$, o${\displaystyle (v,u)\in E}$y algún camino termina en${\displaystyle v}$. Este último caso siempre es aplicable. En el primer caso, el número total de aristas en la cobertura aumenta en 1 y el número de caminos permanece igual; en el segundo caso, el número de caminos aumenta y el número de aristas permanece igual. Ahora está claro que después de cubrir todo${\displaystyle n}$vértices, la suma del número de caminos y aristas en la cubierta es${\displaystyle n}$. Por lo tanto, si el número de aristas en la cubierta es${\displaystyle m}$, el número de caminos es${\displaystyle n-m}$.

Dejar${\displaystyle N=(V,E)}$Sea una red. Supongamos que hay capacidad en cada nodo además de la capacidad de la arista, es decir, una asignación.${\displaystyle c:V\to \mathbb {R} ^{+},}$de tal manera que el flujo${\displaystyle f}$debe 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 \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 de${\displaystyle N}$, podemos transformar el problema en el problema de flujo máximo en el sentido original mediante la expansión${\displaystyle N}$. Primero, cada${\displaystyle v\in V}$es reemplazado por${\displaystyle v_{\text{in}}}$y${\displaystyle v_{\text{out}}}$, dónde${\displaystyle v_{\text{in}}}$está conectado por aristas que entran${\displaystyle v}$y${\displaystyle v_{\text{out}}}$está conectado a los bordes que salen de${\displaystyle v}$luego asignar capacidad${\displaystyle c(v)}$al borde que conecta${\displaystyle v_{\text{in}}}$y${\displaystyle v_{\text{out}}}$(véase la figura 4.4.1). En esta red ampliada, se elimina la restricción de capacidad de los vértices y, por lo tanto, el problema puede tratarse como el problema original de flujo máximo.

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

1. Los caminos deben ser disjuntos en aristas. Este problema se puede transformar en un problema de flujo máximo mediante la construcción de una red.${\displaystyle N=(V,E)}$de${\displaystyle G}$, con${\displaystyle s}$y${\displaystyle t}$ser la fuente y el sumidero de${\displaystyle N}$respectivamente, y asignando a cada arista una capacidad de${\displaystyle 1}$En esta red, el flujo máximo es${\displaystyle k}$si hay${\displaystyle k}$caminos disjuntos en aristas.

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

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

El cierre de un grafo dirigido es un conjunto de vértices C tal que ninguna arista sale de C. El problema del cierre consiste en encontrar el cierre de peso máximo o mínimo en un grafo dirigido ponderado por vértices. Puede resolverse en tiempo polinomial mediante una reducción al problema del flujo máximo.

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 es eliminado si no tiene ninguna posibilidad de terminar la temporada en primer lugar. La tarea del problema de eliminación de béisbol es determinar qué equipos son eliminados en cada punto durante la temporada. Schwartz ^{[ 44 ]} propuso un método que reduce este problema a un 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 donde s , t ∈ V son 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 mediante una arista 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 de flujo en estas aristas. Finalmente, se crean aristas desde el nodo de equipo i al nodo sumidero t y se establece la capacidad de w _k + r _k – w _i para evitar que el equipo i gane más que 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 de s a t .

En la industria aérea, un problema importante es la programación de las tripulaciones de vuelo. Este problema puede considerarse una aplicación del flujo máximo de red extendido. 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 la programación aérea, el objetivo es generar un horario factible con un máximo de k tripulaciones.

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

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 añaden dos nodos a V , el nodo s _i como origen y el nodo d _i como destino del vuelo i . También se añaden las siguientes aristas a E :

1. Una arista con capacidad [0, 1] entre s y 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. Una arista 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. Una arista con capacidad [0, ∞ ] entre s y t .

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

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 en 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 . Un emparejamiento en G' induce una programación para F y obviamente el emparejamiento bipartito máximo en este grafo produce una programación de aerolínea con el número mínimo de tripulaciones. ^{[ 45 ]} Como se menciona en la parte de Aplicación de este artículo, el emparejamiento bipartito de cardinalidad máxima es una aplicación del problema del flujo máximo.

Existen fábricas que producen bienes y pueblos a los que se deben entregar. Están conectados por una red de carreteras, cada una con una capacidad c para el flujo máximo de mercancías. El problema consiste en determinar si existe una circulación que satisfaga la demanda. Este problema puede transformarse en un problema de flujo máximo.

1. Agregue un nodo fuente 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 desde 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 solo si  :

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

Si existe circulación, analizar la solución de flujo máximo daría la respuesta sobre cuántos bienes deben enviarse por una ruta determinada para satisfacer la demanda.

El problema se puede extender agregando un límite inferior al flujo en algunos bordes. ^{[ 46 ]}

En su libro, Kleinberg y Tardos presentan un algoritmo para segmentar una imagen. ^{[ 48 ]} Presentan un algoritmo para encontrar el fondo y el primer plano en una imagen. Más precisamente, el algoritmo toma como entrada un mapa de bits modelado de la siguiente manera: a _i ≥ 0 es la probabilidad de que el píxel i pertenezca al primer plano, b _i ≥ 0 es 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 en A (considerados como primer plano), ganamos a _i ; para todos los píxeles en B (considerados como fondo), ganamos b _i . En el borde, entre dos píxeles adyacentes i y j , perdemos p _ij . Esto 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).}$

Ahora construimos la red cuyos nodos son el píxel, más una fuente y un sumidero (véase la figura de la derecha). Conectamos la fuente con el píxel i mediante una arista de peso a _i . Conectamos el píxel i con el sumidero mediante una arista de peso b _i . Conectamos el píxel i con el píxel j con un 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.