Teorema de corte mínimo de flujo máximo

En informática y teoría de optimización , el teorema de flujo máximo y corte mínimo establece que en una red de flujo , la cantidad máxima de flujo que pasa de la fuente al sumidero es igual al peso total de los bordes en un corte mínimo , es decir, el peso total más pequeño de los bordes que, si se eliminaran, desconectarían la fuente del sumidero.

Este es un caso especial del teorema de dualidad para programas lineales y puede usarse para derivar el teorema de Menger y el teorema de Kőnig-Egerváry . ^[1]

Definiciones y declaraciones

El teorema equipara dos magnitudes: el caudal máximo que pasa por una red y la capacidad mínima de un corte de la red. Para enunciar el teorema, primero hay que definir cada uno de estos conceptos.

Red

Una red consta de

un grafo dirigido finito $N = (V, E)$ , donde V denota el conjunto finito de vértices y $E \subseteq V \times V$ es el conjunto de aristas dirigidas;
una fuente $s \in V$ y un sumidero $t \in V$ ;
una función de capacidad , que es una función denotada por $c$ $uv$ o $c$ $($ $u$ $,$ $v$ $)$ para $($ $u$ $,$ $v$ $) \in$ $E$ . Representa la cantidad máxima de flujo que puede pasar a través de un borde. $c:E\to \mathbb {R} ^{+}$

Flujos

Un flujo a través de una red es un mapeo denotado por o , sujeto a las siguientes dos restricciones: $f:E\to \mathbb {R} ^{+}$ $estilo de visualización f_ {uv}}$ $f(u,v)$

Restricción de capacidad : para cada borde , $(u,v)\en E$ $f_{uv}\leq c_{uv}.$
Conservación de flujos : para cada vértice excepto y (es decir, la fuente y el sumidero, respectivamente), se cumple la siguiente igualdad: ${\estilo de visualización v}$ ${\estilo de visualización s}$ ${\estilo de visualización t}$
$\suma \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\suma \nolimits _{\{w:(v,w)\in E\}}f_{vw}.$

Un flujo puede visualizarse como un flujo físico de un fluido a través de la red, siguiendo la dirección de cada borde. La restricción de capacidad dice entonces que el volumen que fluye a través de cada borde por unidad de tiempo es menor o igual a la capacidad máxima del borde, y la restricción de conservación dice que la cantidad que fluye hacia cada vértice es igual a la cantidad que fluye hacia afuera de cada vértice, aparte de los vértices de origen y destino.

El valor de un flujo se define por

|f|=\suma \nolimits _{\{v:(s,v)\en E\}}f_{sv}=\suma \nolimits _{\{v:(v,t)\en E\}}f_{vt},

donde como se indica arriba es la fuente y es el sumidero de la red. En la analogía de fluidos, representa la cantidad de fluido que ingresa a la red en la fuente. Debido al axioma de conservación para flujos, esto es lo mismo que la cantidad de flujo que sale de la red en el sumidero. ${\estilo de visualización s}$ ${\estilo de visualización t}$

El problema de flujo máximo solicita el flujo más grande en una red determinada.

Problema de flujo máximo. Maximizar, es decir, dirigir la mayor cantidad de flujo posible desdea. ${\estilo de visualización |f|}$ ${\estilo de visualización s}$ ${\estilo de visualización t}$

Recortes

La otra mitad del teorema de corte mínimo de flujo máximo se refiere a un aspecto diferente de una red: la colección de cortes. Un corte st $C = (S, T)$ es una partición de $V$ tal que $s \in S$ y $t \in T$ . Es decir, un corte s - t es una división de los vértices de la red en dos partes, con la fuente en una parte y el sumidero en la otra. El conjunto de cortes de un corte $C$ es el conjunto de aristas que conectan la parte fuente del corte con la parte sumidero: $Estilo de visualización X_{C}}$

X_{C}:=\{(u,v)\en E\ :\ u\en S,v\en T\}=(S\times T)\cap E.

Por lo tanto, si se eliminan todos los bordes del conjunto de corte de $C$ , no es posible ningún flujo positivo, porque no hay un camino en el gráfico resultante desde la fuente hasta el sumidero.

La capacidad de un corte st es la suma de las capacidades de los bordes en su conjunto de corte,

c(S,T)=\suma \nolimits _{(u,v)\en X_{C}}c_{uv}=\suma \nolimits _{(i,j)\en E}c_{ij}d_{ij},

donde si y , en caso contrario. $d_{ij}=1$ $i\in S$ $j\en T$ ${\estilo de visualización 0}$

Normalmente hay muchos cortes en un gráfico, pero los cortes con pesos más pequeños suelen ser más difíciles de encontrar.

Problema de corte st mínimo. Minimizar

c (S, T)

, es decir, determinar

S

T

de manera que la capacidad del corte st sea mínima.

Teorema principal

En la situación anterior, se puede demostrar que el valor de cualquier caudal que recorra una red es menor o igual a la capacidad de cualquier corte de st y que, además, existe un caudal con valor máximo y un corte con capacidad mínima. El teorema principal vincula el valor máximo del caudal con la capacidad mínima del corte de la red.

Teorema de corte mínimo de caudal máximo. El valor máximo de un caudal de st es igual a la capacidad mínima sobre todos los cortes de st.

Ejemplo

La figura de la derecha muestra un flujo en una red. La anotación numérica en cada flecha, en la forma f / c , indica el caudal ( f ) y la capacidad ( c ) de la flecha. Los caudales que emanan de la fuente suman cinco (2+3=5), al igual que los caudales que van al sumidero (2+3=5), lo que establece que el valor del caudal es 5.

Un corte s - t con valor 5 viene dado por S ={ s , p } y T ={ o , q , r , t }. Las capacidades de las aristas que cruzan este corte son 3 y 2, lo que da una capacidad de corte de 3+2=5. (La flecha de o a p no se considera, ya que apunta de T de nuevo a S ).

El valor del caudal es igual a la capacidad del corte, mostrando que el caudal es un caudal máximo y el corte es un corte mínimo.

Nótese que el flujo a través de cada una de las dos flechas que conectan S con T está a plena capacidad; esto siempre es así: un corte mínimo representa un 'cuello de botella' del sistema.

Formulación de programa lineal

El problema de flujo máximo y el problema de corte mínimo se pueden formular como dos programas lineales primal-duales . ^[2]

El LP de flujo máximo es sencillo. El LP dual se obtiene utilizando el algoritmo descrito en el programa lineal dual : las variables y las restricciones de signo del dual corresponden a las restricciones del primal, y las restricciones del dual corresponden a las variables y las restricciones de signo del primal. El LP resultante requiere cierta explicación. La interpretación de las variables en el LP de corte mínimo es:

d_{uv}={\begin{cases}1,&{\text{si }}u\in S{\text{ y }}v\in T{\text{ (la arista }}uv{\text{ está en el corte) }}\\0,&{\text{en caso contrario}}\end{cases}}

z_{v}={\begin{cases}1,&{\text{si }}v\in S\\0,&{\text{en caso contrario}}\end{cases}}

El objetivo de minimización suma la capacidad sobre todos los bordes que están contenidos en el corte.

Las restricciones garantizan que las variables efectivamente representen un corte legal: ^[3]

Las restricciones (equivalentes a ) garantizan que, para los nodos no terminales u,v , si u está en S y v está en T , entonces la arista ( u , v ) se cuenta en el corte ( ). $d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}\geq z_{u}-z_{v}$ $d_{uv}\geq 1$
Las restricciones (equivalentes a ) garantizan que, si v está en T , entonces la arista (s,v) se cuenta en el corte (ya que s está por definición en S ). $d_{sv}+z_{v}\geq 1$ $d_{sv}\geq 1-z_{v}$
Las restricciones (equivalentes a ) garantizan que, si u está en S , entonces la arista (u,t) se cuenta en el corte (ya que t está por definición en T ). $d_{ut}-z_{u}\geq 0$ $d_{ut}\geq z_{u}$

Tenga en cuenta que, dado que se trata de un problema de minimización, no tenemos que garantizar que un borde no esté en el corte; solo tenemos que garantizar que cada borde que debería estar en el corte se sume en la función objetivo.

La igualdad en el teorema de flujo máximo-corte mínimo se deriva del teorema de dualidad fuerte en programación lineal , que establece que si el programa primal tiene una solución óptima, x *, entonces el programa dual también tiene una solución óptima, y *, tal que los valores óptimos formados por las dos soluciones son iguales.

Solicitud

Teorema de flujo máximo de Cederbaum

El problema de flujo máximo se puede formular como la maximización de la corriente eléctrica a través de una red compuesta de elementos resistivos no lineales. ^[4] En esta formulación, el límite de la corriente $I$ $en$ entre los terminales de entrada de la red eléctrica a medida que el voltaje de entrada $V$ $en$ se acerca a , es igual al peso del conjunto de corte de peso mínimo. ${\estilo de visualización\infty}$

\lim _{V_{\text{en}}\to \infty }(I_{en})=\min _{X_{C}}\sum _{(u,v)\en X_{C}}c_{uv}

Teorema generalizado de flujo máximo y corte mínimo

Además de la capacidad de borde, considere que hay capacidad en cada vértice, es decir, una aplicación denotada por $c$ $($ $v$ $)$ , tal que el flujo $f$ tiene que satisfacer no solo la restricción de capacidad y la conservación de flujos, sino también la restricción de capacidad de vértice. $c:V\to \mathbb {R} ^{+}$

\para todo v\en V\setminus \{s,t\}:\qcuadrado \suma \nolimits _{\{u\en V\mid (u,v)\en E\}}f_{uv}\leq c(v).

En otras palabras, la cantidad de flujo que pasa a través de un vértice no puede exceder su capacidad. Defina un corte st como el conjunto de vértices y aristas tales que para cualquier camino desde s hasta t , el camino contiene un miembro del corte. En este caso, la capacidad del corte es la suma de la capacidad de cada arista y vértice en él.

En esta nueva definición, el teorema generalizado de flujo máximo y corte mínimo establece que el valor máximo de un flujo st es igual a la capacidad mínima de un corte st en el nuevo sentido.

Teorema de Menger

En el problema de caminos no dirigidos disjuntos en las aristas, se nos da un grafo no dirigido $G = (V, E)$ y dos vértices $s$ y $t$ , y tenemos que encontrar el número máximo de caminos disjuntos en las aristas st en $G$ .

El teorema de Menger establece que el número máximo de caminos st disjuntos en sus aristas en un grafo no dirigido es igual al número mínimo de aristas en un conjunto de corte st.

Problema de selección de proyectos

En el problema de selección de proyectos, hay $n$ proyectos y $m$ máquinas. Cada proyecto $p i$ produce un ingreso $r (p i)$ y cada máquina $q j$ cuesta $c (q j)$ para comprar. Queremos seleccionar un subconjunto del proyecto y comprar un subconjunto de las máquinas para maximizar la ganancia total (ingreso de los proyectos seleccionados menos costo de las máquinas compradas). Debemos cumplir la siguiente restricción: cada proyecto especifica un conjunto de máquinas que deben comprarse si se selecciona el proyecto. (Cada máquina, una vez comprada, puede usarse en cualquier proyecto seleccionado).

Para resolver el problema, sea $P$ el conjunto de proyectos no seleccionados y $Q$ el conjunto de máquinas compradas, entonces el problema se puede formular como,

\max\{g\}=\sum _{i}r(p_{i})-\sum _{p_{i}\in P}r(p_{i})-\sum _{q_{j}\in Q}c(q_{j}).

Dado que el primer término no depende de la elección de $P$ y $Q$ , este problema de maximización puede formularse como un problema de minimización, es decir,

\min\{g'\}=\sum _{p_{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).

El problema de minimización anterior puede entonces formularse como un problema de corte mínimo mediante la construcción de una red, donde la fuente está conectada a los proyectos con capacidad $r (p i)$ , y el sumidero está conectado por las máquinas con capacidad $c (q j)$ . Se agrega una arista $(p i, q j)$ con capacidad infinita si el proyecto $p i$ requiere la máquina $q j$ . El conjunto de corte st representa los proyectos y las máquinas en $P$ y $Q$ respectivamente. Por el teorema de corte mínimo de flujo máximo, se puede resolver el problema como un problema de flujo máximo .

La figura de la derecha ofrece una formulación en red del siguiente problema de selección de proyectos:

La capacidad mínima de un st cut es de 250 y la suma de los ingresos de cada proyecto es de 450; por lo tanto, la ganancia máxima g es 450 − 250 = 200, seleccionando los proyectos $p 2$ y $p 3$ .

La idea aquí es hacer que las ganancias de cada proyecto fluyan a través de las "tuberías" de sus máquinas. Si no podemos llenar la tubería desde una máquina, el rendimiento de la máquina es menor que su costo y el algoritmo de corte mínimo considerará más económico cortar la ventaja de ganancias del proyecto en lugar de la ventaja de costos de la máquina.

Problema de segmentación de imágenes

En el problema de segmentación de imágenes, hay $n$ píxeles. A cada píxel $i$ se le puede asignar un valor de primer plano $f i$ o un valor de fondo $b i$ . Existe una penalización de $p ij$ si los píxeles $i, j$ son adyacentes y tienen asignaciones diferentes. El problema consiste en asignar píxeles al primer plano o al fondo de modo que la suma de sus valores menos las penalizaciones sea máxima.

Sea $P$ el conjunto de píxeles asignados al primer plano y $Q$ el conjunto de puntos asignados al fondo, entonces el problema se puede formular como,

\max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.

Este problema de maximización puede formularse como un problema de minimización, es decir,

\min\{g'\}=\sum _{i\in P,j\in Q\lor j\in P,i\in Q}p_{ij}.

El problema de minimización anterior se puede formular como un problema de corte mínimo mediante la construcción de una red donde la fuente (nodo naranja) está conectada a todos los píxeles con capacidad $f i$ , y el sumidero (nodo violeta) está conectado por todos los píxeles con capacidad $b i$ . Se agregan dos aristas ( $i, j$ ) y ( $j, i$ ) con capacidad $p ij$ entre dos píxeles adyacentes. El conjunto de corte st representa entonces los píxeles asignados al primer plano en $P$ y los píxeles asignados al fondo en $Q$ .

Historia

Ford y Fulkerson dieron una explicación del descubrimiento del teorema en 1962: ^[5]

"En la primavera de 1955, TE Harris, junto con el general retirado FS Ross, había formulado un modelo simplificado del flujo de tráfico ferroviario y había señalado este problema en particular como el problema central sugerido por el modelo, planteó a los autores la determinación de un flujo máximo en estado estacionario desde un punto a otro en una red sujeta a limitaciones de capacidad en los arcos... No pasó mucho tiempo hasta que se conjeturó y estableció el resultado principal, el teorema 5.1, que llamamos teorema de flujo máximo y corte mínimo. ^[6] Desde entonces han aparecido varias pruebas". ^[7]^[8]^[9]

Prueba

Sea $G = (V, E)$ una red (grafo dirigido) con $s$ y $t$ siendo la fuente y el sumidero de $G$ respectivamente.

Considere el flujo $f$ calculado para $G$ mediante el algoritmo de Ford–Fulkerson . En el grafo residual $($ $G$ $f$ $)$ obtenido para $G$ (después de la asignación de flujo final mediante el algoritmo de Ford–Fulkerson ), defina dos subconjuntos de vértices de la siguiente manera:

$A$ : el conjunto de vértices alcanzables desde $s$ en $G f$
$A c$ : el conjunto de vértices restantes, es decir $V - A$

Reclamación. $valor(f) = c (A, A c)$ , donde la capacidad de un corte st se define por

c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}

Ahora, sabemos que, para cualquier subconjunto de vértices, $A$ . Por lo tanto, para $value($ $f$ $) =$ $c$ $($ $A$ $,$ $A$ $c$ $)$ necesitamos: $value(f)=f_{out}(A)-f_{in}(A)$

Todos los bordes salientes del corte deben estar completamente saturados .
Todos los bordes entrantes al corte deben tener flujo cero .

Para probar la afirmación anterior consideremos dos casos:

En $G$ , existe una arista saliente tal que no está saturada, es decir, $f$ $($ $x$ $,$ $y$ $) <$ $c$ $xy$ . Esto implica que existe una arista hacia delante de $x$ a $y$ en $G$ $f$ , por lo tanto, existe un camino de $s$ a $y$ en $G$ $f$ , lo cual es una contradicción. Por lo tanto, cualquier arista saliente $($ $x$ $,$ $y$ $)$ está completamente saturada. $(x,y),x\in A,y\in A^{c}$

En $G$ , existe un borde entrante tal que lleva algún flujo distinto de cero, es decir, $f$ $($ $y$ $,$ $x$ $) > 0$ . Esto implica que existe un borde regresivo de $x$ a $y$ en $G$ $f$ , por lo tanto, existe un camino de $s$ a $y$ en $G$ $f$ , lo que nuevamente es una contradicción. Por lo tanto, cualquier borde entrante $($ $y$ $,$ $x$ $)$ debe tener flujo cero. $(y,x),x\in A,y\in A^{c}$

Ambas afirmaciones anteriores demuestran que la capacidad de corte obtenida de la manera descrita anteriormente es igual al caudal obtenido en la red. Además, el caudal se obtuvo mediante el algoritmo de Ford-Fulkerson , por lo que también es el caudal máximo de la red.

Además, dado que cualquier flujo en la red es siempre menor o igual a la capacidad de cada corte posible en una red, el corte descrito anteriormente es también el corte mínimo que obtiene el flujo máximo .

Un corolario de esta prueba es que el flujo máximo a través de cualquier conjunto de aristas en un corte de un gráfico es igual a la capacidad mínima de todos los cortes anteriores.

Véase también

Referencias

^ Dantzig, GB; Fulkerson, DR (9 de septiembre de 1964). "Sobre el teorema de flujo máximo y corte mínimo de redes" (PDF) . RAND Corporation : 13. Archivado desde el original (PDF) el 5 de mayo de 2018.
^ Trevisan, Luca. "Conferencia 15 de CS261: Optimización" (PDF) .
^ Keller, Orgad. "Presentación de flujo máximo y corte mínimo de LP".
^ Cederbaum, I. (agosto de 1962). "Sobre el funcionamiento óptimo de las redes de comunicación". Journal of the Franklin Institute . 274 (2): 130–141. doi :10.1016/0016-0032(62)90401-5.
^ LR Ford Jr. y DR Fulkerson (1962) Flujos en redes , página 1, Princeton University Press MR 0159700
^ LR Ford Jr. y DR Fulkerson (1956) "Flujo máximo a través de una red", Revista Canadiense de Matemáticas 8: 399–404
^ P. Elias, A. Feinstein y CE Shannon (1956) "Una nota sobre el flujo máximo a través de una red", IRE. Transactions on Information Theory, 2(4): 117–119
^ George Dantzig y DR Fulkerson (1956) "Sobre el teorema de flujo máximo y corte mínimo de redes", en Linear Inequalities , Ann. Math. Studies, n.º 38, Princeton, Nueva Jersey
^ LR Ford y DR Fulkerson (1957) "Un algoritmo simple para encontrar los flujos máximos de la red y una aplicación al problema de Hitchcock", Revista Canadiense de Matemáticas 9: 210–18

Eugene Lawler (2001). "4.5. Implicaciones combinatorias del teorema de corte mínimo de flujo máximo, 4.6. Interpretación de programación lineal del teorema de corte mínimo de flujo máximo". Optimización combinatoria: redes y matroides . Dover. págs. 117–120. ISBN 0-486-41453-1.
Christos H. Papadimitriou , Kenneth Steiglitz (1998). "6.1 El teorema de flujo máximo y corte mínimo". Optimización combinatoria: algoritmos y complejidad . Dover. págs. 120–128. ISBN. 0-486-40258-4.
Vijay V. Vazirani (2004). "12. Introducción a la dualidad LP". Algoritmos de aproximación . Springer. pp. 93–100. ISBN 3-540-65367-8.