Problema de flujo máximo

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Problema computacional en la teoría del gráfico

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

Historia

Did you mean:

The maximum flow problem was first formulated in 1954 by T. H. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.

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 un número asignado a ella que representa su capacidad. Asumiendo una condición de estado estable, encontrar un flujo máximo de una ciudad dada a la otra.

En su libro Flujos en red, en 1962, Ford y Fulkerson escribieron:

Fue planteado a los autores en la primavera de 1955 por T. E. Harris, quien, junto con el General F. S. 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 netas ferroviarias de Harris y Ross (ver 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-reetiqueta 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 sólo funcionan en grafos no dirigidos.

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

En 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, y Sushant Sachdeva publicaron un algoritmo de tiempo casi lineal funcionando en ${displaystyle O(|E|^{1+o(1)})}$ para el problema de flujo de costes mínimos del cual para el problema de flujo máximo es un caso particular. Para el problema del camino más corto (SSSP) de un solo proveedor con pesos negativos se ha reportado otro caso particular del problema del flujo de costes mínimos. Ambos algoritmos se consideraron mejores papeles en el Simposio 2022 sobre Fundaciones de Ciencias de la Computación.

Definición

Primero establecemos alguna notación:

Vamos $N=(V,E)$ ser una red con ${displaystyle s,tin V}$ ser la fuente y el lavabo de $N$ respectivamente.
Si $g$ es una función en los bordes de $N$ entonces su valor $(u,v)in E$ es denotado por ${displaystyle g_{uv}}$ o ${displaystyle g(u,v).}$

Definición. El capacidad de un borde es la cantidad máxima de flujo que puede pasar a través de un borde. Formally es un mapa ${displaystyle c:Eto mathbb {R} ^{+}.}$

Definición. A flujo es un mapa ${displaystyle f:Eto mathbb {R} }$ que satisface lo siguiente:

Limitación de la capacidad. El flujo de un borde no puede exceder su capacidad, es decir: ${displaystyle f_{uv}leq c_{uv}}$ para todos ${displaystyle (u,v)in E.}$
Conservación de los flujos. La suma de los flujos que entran en un nodo debe igualar la suma de los flujos que salen de ese nodo, excepto la fuente y el lavabo. O:

{displaystyle forall vin Vsetminus {s,t}:quad sum _{u:(u,v)in E}f_{uv}=sum _{u:(v,u)in E}f_{vu}.}

Remark. Los flujos son simétricos de sierra: ${displaystyle f_{uv}=-f_{vu}}$ para todos ${displaystyle (u,v)in E.}$

Definición. El valor del flujo es la cantidad de flujo que pasa de la fuente al fregadero. Formalmente para un flujo ${displaystyle f:Eto mathbb {R} ^{+}}$ es dado por:

{displaystyle |f|=sum _{v: (s,v)in E}f_{sv}-sum _{u: (u,s)in E}f_{us}.}

Definición. El máximo problema de flujo es recorrer tanto flujo como sea posible desde la fuente al fregadero, en otras palabras encontrar el flujo ${displaystyle f_{textrm {max}}}$ con valor máximo.

Tenga en cuenta que pueden existir varios flujos máximos, y si se permiten valores reales arbitrarios (o incluso racionales arbitrarios) de flujo (en lugar de solo números enteros), hay exactamente un flujo máximo, o infinitamente muchos, ya que hay infinitamente muchas combinaciones lineales de los flujos máximos base. En otras palabras, si mandamos $x$ unidades de flujo en el borde $u$ en un flujo máximo, y $x}" xmlns="http://www.w3.org/1998/Math/MathML">Sí.■x{displaystyle y títulox}x}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a22112f92b4b6d0c2f20283a6b5cb93e384091ca" style="vertical-align: -0.671ex; width:5.584ex; height:2.176ex;"/>$ unidades de flujo $u$ en otro flujo máximo, entonces para cada ${displaystyle Delta in [0,y-x]}$ podemos enviar ${displaystyle x+Delta }$ unidades $u$ y el flujo en los bordes restantes en consecuencia, para obtener otro flujo máximo. Si los valores de flujo pueden ser cualquier número real o racional, entonces hay infinitamente muchos tales $Delta$ valores para cada par $x,y$ .

Algoritmos

Las siguientes tablas enumeran algoritmos para resolver el problema de flujo máximo. Aquí, $V$ y $E$ denota el número de vértices y bordes de la red. El valor $U$ se refiere a la mayor capacidad de los bordes después de escalar todas las capacidades de los valores enteros (si la red contiene capacidades irracionales, $U$ puede ser infinito).

Método	Complejidad	Descripción
Programación lineal		Constraints given by the definition of a legal flow. Vea el programa lineal aquí.
algoritmo Ford-Fulkerson	${displaystyle O(E^{2}U)}$	Mientras exista un camino abierto a través del gráfico residual, envíe el mínimo de las capacidades residuales en ese camino.
Algoritmo de Edmonds–Karp	$O(VE^{2})$	Una especialización de Ford-Fulkerson, encontrando caminos crecientes con la búsqueda de la primera.
El algoritmo de Dinic	${displaystyle O(V^{2}E)}$	En cada fase los algoritmos construyen un gráfico con capas con búsqueda de la primera parte del gráfico residual. El flujo máximo en un gráfico capa se puede calcular en $O(VE)$ tiempo, y el número máximo de fases es ${displaystyle V-1}$ . En redes con capacidades unitarias, el algoritmo de Dinic termina en $O(min{V^{2/3}, E^{1/2}}E)$ tiempo.
MKM (Malhotra, Kumar, Maheshwari) algoritmo	${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	$O(VE log V)$	La estructura de datos de árboles dinámicos acelera la computación de flujo máximo en el gráfico de capas a $O(VE log V)$ .
Presión general – algoritmo de etiqueta	${displaystyle O(V^{2}E)}$	El algoritmo push relabel mantiene un preflujo, es decir, una función de flujo con la posibilidad de exceso en los vértices. El algoritmo funciona 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 controles de vértices a través de los cuales los bordes residuales pueden fluir. La función de altura es cambiada por la operación de relabel. Las definiciones adecuadas de estas operaciones garantizan que la función de flujo resultante sea un flujo máximo.
Algoritmo de la etiqueta de empuje con FIFO regla de selección de vertex	${displaystyle O(V^{3})}$	Presionar-relabel algoritmo variante que siempre selecciona el vertex más activo recientemente, y realiza operaciones de empuje mientras el exceso es positivo y hay bordes residuales admisibles de este vértice.
Algoritmo de la etiqueta de empuje con distancia máxima regla de selección de vertex	${displaystyle O(V^{2}{sqrt {E}})}$	Presion-relabel algoritmo variante que siempre selecciona el vértice más distante de $s$ o $t$ (es decir, la etiqueta más alta vértice) pero de lo contrario procede como el algoritmo FIFO.
Algoritmo de relabel con árboles dinámicos	${displaystyle Oleft(VElog {frac {V^{2}}{E}}right)}$	El algoritmo construye árboles de tamaño limitado en el gráfico residual respecto a la función de altura. Estos árboles proporcionan operaciones de empuje multinivel, es decir, empujando a lo largo de toda una saturación sendero en lugar de un solo borde.
KRT (King, Rao, Tarjan) algoritmo	${displaystyle Oleft(VElog _{frac {E}{Vlog V}}Vright)}$
algoritmo de flujo de bloqueo binario	${displaystyle Oleft(Ecdot min{V^{2/3},E^{1/2}}cdot log {frac {V^{2}}{E}}cdot log Uright)}$
James B Orlin + KRT (King, Rao, Tarjan) algoritmo	$O(VE)$	El algoritmo de Orlin resuelve el flujo máximo en $O(VE)$ tiempo para ${displaystyle Eleq O(V^{{frac {16}{15}}-epsilon })}$ mientras KRT lo resuelve $O(VE)$ para $V^{1+epsilon }}" xmlns="http://www.w3.org/1998/Math/MathML">E■V1+ε ε {displaystyle E hijos!V^{1+epsilon }" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ebfc237d73e4da6ffd2c5e516102db64fe4bdad" style="vertical-align: -0.338ex; width:9.791ex; height:2.676ex;"/>$ .
algoritmo de Kathuria-Liu-Sidford	${displaystyle E^{4/3+o(1)}U^{1/3}}$	Métodos de punto interior y potenciación de bordes utilizando ${displaystyle ell _{p}}$ - flujos de norm. Construye el algoritmo anterior de Madry, que logró el tiempo de ejecución ${displaystyle {tilde {O}}(E^{10/7}U^{1/7})}$ .
BLNPSSSW / algoritmo BLLSSSW	${displaystyle {tilde {O}}((E+V^{3/2})log U)}$	Métodos de puntos de interior y mantenimiento dinámico de flujos eléctricos con descomposiciones de expansión.
algoritmo 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 de aumento en el núcleo del algoritmo basado en el método de punto interior de [Mądry JACM '16]. Esto implica diseñar estructuras de datos que, en entornos limitados, devuelven los bordes con gran energía eléctrica en un gráfico sometido a actualizaciones de resistencia.
Chen, Kyng, Liu, Peng, El algoritmo de Gutenberg y Sachdeva	${displaystyle O(E^{1+o(1)}log U)}$	Chen, Kyng, Liu, Peng, El algoritmo de Gutenberg y Sachdeva resuelve el flujo máximo y el flujo de coste mínimo en tiempo casi lineal mediante la construcción del flujo a través de una secuencia de ${displaystyle E^{1+o(1)}}$ Ciclos mínimos no dirigidos aproximados, cada uno de los cuales es computado y procesado en amortizado ${displaystyle E^{o(1)}}$ tiempo utilizando una estructura dinámica de datos.

Para algoritmos adicionales, consulte Goldberg & Tarjano (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 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.

Aplicación

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

Dada una red $N=(V,E)$ con un conjunto de fuentes ${displaystyle S={s_{1},ldotss_{n}}}$ y un conjunto de lavabos ${displaystyle T={t_{1},ldotst_{m}}}$ en lugar de sólo una fuente y un lavabo, vamos a encontrar el flujo máximo a través de $N$ . Podemos transformar el problema multi-sink de múltiples fuentes en un problema de flujo máximo añadiendo un fuente consolidada conectar a cada vértice en $S$ y a sumideros consolidados conectado por cada vértice en $T$ (también conocido como supersource y supersink) con capacidad infinita en cada borde (Ver Fig. 4.1.1.).

Coincidencia bipartita de cardinalidad máxima

Dado un gráfico bipartito ${displaystyle G=(Xcup Y,E)}$ , vamos a encontrar una máxima cardenalidad que coincida en $G$ , que es una coincidencia que contiene el mayor número posible de bordes. Este problema se puede transformar en un problema de flujo máximo mediante la construcción de una red ${displaystyle N=(Xcup Ycup {s,t},E')}$ , donde

$E'$ contiene los bordes en $G$ dirigida desde $X$ a $Y$ .
${displaystyle (s,x)in E'}$ para cada uno $xin X$ y ${displaystyle (y,t)in E'}$ para cada uno $yin Y$ .
${displaystyle c(e)=1}$ para cada uno ${displaystyle ein E'}$ (Véase Fig. 4.3.1).

Luego el valor del flujo máximo en $N$ es igual al tamaño del máximo partido en $G$ , y una máxima cardenalidad que coincide se puede encontrar tomando los bordes que tienen flujo $1$ en un max-flow integral.

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

Dado un gráfico acíclico dirigido $G=(V,E)$ , vamos a encontrar el número mínimo de caminos descompuestos al vertex para cubrir cada vértice en $V$ . Podemos construir un gráfico bipartito ${displaystyle G'=(V_{textrm {out}}cup V_{textrm {in}},E')}$ desde $G$ , donde

${displaystyle V_{textrm {out}}={v_{textrm {out}}mid vin Vland v{text{ has outgoing edge(s)}}}}$
${displaystyle V_{textrm {in}}={v_{textrm {in}}mid vin Vland v{text{ has incoming edge(s)}}}}$
${displaystyle E'={(u_{textrm {out}},v_{textrm {in}})in V_{out}times V_{in}mid (u,v)in E}}$ .

Entonces se puede demostrar que $G'$ tiene una coincidencia $M$ de tamaño $m$ si $G$ tiene una cubierta de camino descomunal $C$ que contiene $m$ bordes y $n-m$ caminos, donde $n$ es el número de vértices en $G$ . Por lo tanto, el problema se puede resolver encontrando la máxima cardenalidad que coincide con $G'$ en su lugar.

Assume hemos encontrado una coincidencia $M$ de $G'$ , y construyó la cubierta $C$ de ella. Intuitivamente, si dos vértices ${displaystyle u_{mathrm {out} },v_{mathrm {in} }}$ son emparejados en $M$ , entonces el borde $(u,v)$ figura en $C$ . Claramente el número de bordes en $C$ es $m$ . Para ver eso $C$ es vertex-disjoint, considerar lo siguiente:

Cada vértice ${displaystyle v_{textrm {out}}}$ dentro $G'$ puede ser no empaquetado dentro $M$ , en cuyo caso no hay bordes saliendo $v$ dentro $C$ ; o puede ser emparejado, en cuyo caso hay exactamente un borde saliendo $v$ dentro $C$ . En cualquier caso, no más de un borde deja ningún vértice $v$ dentro $C$ .
Del mismo modo para cada vértice ${displaystyle v_{textrm {in}}}$ dentro $G'$ – si se combina, hay un solo borde entrante $v$ dentro $C$ ; de lo contrario $v$ no tiene bordes entrantes en $C$ .

Así ningún vértice tiene dos bordes entrantes o dos salientes en $C$ , que significa todos los caminos en $C$ son vertex-disjoint.

Para mostrar que la cubierta $C$ tiene tamaño $n-m$ , comenzamos con una cubierta vacía y lo construimos incrementalmente. Para añadir un vértice $u$ a la cubierta, podemos añadirlo a un camino existente, o crear un nuevo camino de la longitud cero comenzando en ese vértice. El caso anterior es aplicable siempre que sea $(u,v)in E$ y algún camino en la cubierta comienza en $v$ , o ${displaystyle (v,u)in E}$ y algún camino termina en $v$ . Este último caso es siempre aplicable. En el caso anterior, el número total de bordes en la cubierta se aumenta en 1 y el número de caminos se mantiene igual; en el último caso se aumenta el número de caminos y el número de bordes se mantiene igual. Ahora está claro que después de cubrir todo $n$ vértices, la suma del número de caminos y bordes en la cubierta es $n$ . Por lo tanto, si el número de bordes en la cubierta es $m$ , el número de caminos es $n-m$ .

Caudal máximo con capacidades de vértice

Vamos $N=(V,E)$ ser una red. Supongamos que hay capacidad en cada nodo además de la capacidad de borde, es decir, una asignación ${displaystyle c:Vto mathbb {R} ^{+},}$ tal que el flujo $f$ tiene que satisfacer no sólo la limitación de la capacidad y la conservación de los flujos, sino también la limitación de la capacidad del vértice

{displaystyle sum _{iin V}f_{iv}leq c(v)qquad forall vin Vbackslash {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 $N$ , podemos transformar el problema en el problema de flujo máximo en el sentido original ampliando $N$ . Primero, cada uno $vin V$ es reemplazado por $v_{text{in}}$ y $v_{text{out}}$ , donde $v_{text{in}}$ está conectado por bordes entrando $v$ y $v_{text{out}}$ está conectado a los bordes que salen de $v$ , luego asignar capacidad $c(v)$ a la conexión del borde $v_{text{in}}$ y $v_{text{out}}$ (véase Fig. 4.4.1). En esta red ampliada se elimina la limitación de capacidad del vértice y por lo tanto el problema se puede tratar como el problema de flujo máximo original.

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

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

1. Los caminos deben ser descomunales. Este problema se puede transformar a un problema de flujo máximo mediante la construcción de una red $N=(V,E)$ desde $G$ , con $s$ y $t$ ser la fuente y el lavabo de $N$ respectivamente, y asignando a cada borde una capacidad $1$ . En esta red, el flujo máximo es $k$ si hay $k$ caminos descomunales.

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

3. Además de los caminos que se encuentran en el borde-disjoint y/o vertex disjoint, los caminos también tienen una limitación de longitud: contamos sólo caminos cuya longitud es exactamente $k$ , o al menos $k$ . La mayoría de las variantes de este problema son NP-completo, excepto los pequeños valores de $k$ .

Problema de cierre

Un cierre de un gráfico dirigido es un conjunto de vértices C, de modo 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

En el problema de eliminación del béisbol hay n equipos compitiendo en una liga. En una etapa específica de la temporada liguera, 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 restantes 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 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 con $s, siendo t \in V$ 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 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 garantizar que uno de ellos gane. No es necesario restringir el valor del flujo en estos bordes. Finalmente, se hacen los bordes desde el nodo del equipo i hasta el nodo sumidero t y la capacidad de $w k + r k - w i$ está configurado 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

<math alttext="{displaystyle r(S-{k})=sum _{i,jin {S-{k}} atop ir()S− − {}k})=.. i,j▪ ▪ {}S− − {}k}}i.jrij{displaystyle r(S-{k})=sum _{i,jin ################################################################################################################################################################################################################################################################<img alt="{displaystyle r(S-{k})=sum _{i,jin {S-{k}} atop i

En este método se afirma que el 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 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 \in V$ como los nodos fuente y sumidero. Para el origen y destino de cada vuelo i, se agregan 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 agregan los siguientes bordes a E:

Un borde con capacidad [0, 1] entre s y cada uno s_i.
Un borde con capacidad [0, 1] entre cada uno d_i y t.
Un borde con capacidad [1, 1] entre cada par de s_i y d_i.
Un borde con capacidad [0, 1] entre cada uno d_i y s_j, si la fuente s_j es accesible con una cantidad razonable de tiempo y costo desde el destino de vuelo i.
Un borde 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 equivale a encontrar un horario factible para el conjunto de vuelos F con como máximo k tripulaciones.

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 utiliza un gráfico bipartito $G' = (A \cup Se crea 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 \in A$ está conectado a $j \in B$ . Una coincidencia en $G'$ induce una programación para F y, obviamente, una coincidencia bipartita máxima en este gráfico. produce un horario de aerolíneas con un número mínimo de tripulaciones. 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 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.

Añadir un nodo fuente $s$ y añadir bordes de ella a cada nodo de fábrica $f i$ con capacidad $p i$ Donde $p i$ es la tasa de producción de fábrica $f i$ .
Añadir un nodo de fregadero $t$ y añadir bordes de todos los pueblos $v i$ a $t$ con capacidad $d i$ Donde $d i$ es la tasa de demanda de 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 flujo(G)

{displaystyle =sum _{iin 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.

Segmentación de imágenes

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 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 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 _{iin A}a_{i}+sum _{iin B}b_{i}-sum _{begin{matrix}i,j{text{ adjacent}}\|Acap {i,j}|=1end{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), 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 _{iin A}b_{i}+sum _{iin B}a_{i}+sum _{begin{matrix}i,j{text{ adjacent}}\|Acap {i,j}|=1end{matrix}}p_{ij}}

porque

{displaystyle q(A,B)=sum _{iin Acup B}a_{i}+sum _{iin Acup B}b_{i}-q'(A,B).}

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 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 a_uvf_uv. Se requiere encontrar un flujo de un tamaño determinado 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 restricciones disyuntivas positivas 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.

Contenido relacionado

Más resultados...