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 desde 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 quitaran, desconectarían la fuente del fregadero.

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 declaración

El teorema equipara dos cantidades: el caudal máximo a través de una red y la capacidad mínima de un corte de la red. Para enunciar el teorema, primero se debe definir cada una de estas nociones.

Red

Una red consta de

un gráfico 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 aplicació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 dos restricciones siguientes: $f:E\to \mathbb {R} ^{+}$ ${\ Displaystyle 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 aparte de y (es decir, la fuente y el sumidero, respectivamente), se cumple la siguiente igualdad: $v$ $s$ $t$
$\sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}} f_ {vw}.$

Un flujo se puede visualizar 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 fuera de cada vértice, aparte de los vértices fuente y sumidero.

El valor de un flujo está definido por

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

donde como arriba es la fuente y es el sumidero de la red. En la analogía del fluido, representa la cantidad de fluido que ingresa a la red en la fuente. Debido al axioma de conservación de los flujos, esto es lo mismo que la cantidad de flujo que sale de la red en el sumidero. $s$ $t$

El problema del flujo máximo requiere el flujo más grande en una red determinada.

Problema de flujo máximo. Maximizar, es decir, encaminar la mayor cantidad de flujo posible desdehacia. $|f|$ $s$ $t$

cortes

La otra mitad del teorema de flujo máximo y corte mínimo se refiere a un aspecto diferente de una red: el conjunto de cortes. Un st corte $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 corte de un corte $C$ es el conjunto de aristas que conectan la parte fuente del corte con la parte sumidero: $X_{C}$

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

Por lo tanto, si se eliminan todos los bordes en el conjunto de corte de $C$ , entonces no es posible un 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 cortes,

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

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

Generalmente 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 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 flujo a través de una red es menor o igual a la capacidad de cualquier corte , y que además existe un flujo 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 de corte de la red.

Teorema de corte mínimo de flujo máximo. El valor máximo de un flujo st es igual a la capacidad mínima en todos los cortes 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 flujo ( f ) y la capacidad ( c ) de la flecha. Los flujos que emanan de la fuente suman cinco (2+3=5), al igual que los flujos hacia el sumidero (2+3=5), estableciendo que el valor del flujo 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 atraviesan este corte son 3 y 2, dando una capacidad de corte de 3+2=5. (La flecha de o a p no se considera, ya que apunta de T 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.

Tenga en cuenta que el flujo a través de cada una de las dos flechas que conectan S con T está a plena capacidad; siempre es así: un recorte 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 duales primarios . ^[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 restricciones de signo del dual corresponden a las restricciones del primal, y las restricciones del dual corresponden a las variables y restricciones de signo del primal. El LP resultante requiere alguna explicación. La interpretación de las variables en el LP de corte mínimo es:

d_{uv}={\begin{cases}1,&{\text{if }}u\in S{\text{ and }}v\in T{\text{ (the edge }}uv{\text{ is in the cut) }}\\0,&{\text{otherwise}}\end{cases}}

z_{v}={\begin{cases}1,&{\text{if }}v\in S\\0,&{\text{otherwise}}\end{cases}}

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

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

Las restricciones (equivalentes a ) garantizan que, para 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 el borde (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 el borde (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 y corte mínimo se deriva del teorema de dualidad fuerte en programación lineal , que establece que si el programa primario 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 del flujo máximo de Cederbaum

El problema del 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$ $entre$ los terminales de entrada de la red eléctrica a medida que se acerca el voltaje de entrada $V$ $in$ , es igual al peso del conjunto de corte de peso mínimo. $\infty$

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

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

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

\forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u\in V\mid (u,v)\in E\}}f_{uv}\leq c(v).

En otras palabras, la cantidad de flujo que pasa por un vértice no puede exceder su capacidad. Defina un corte st como el conjunto de vértices y aristas de manera que para cualquier ruta de s a t , la ruta contenga un miembro del corte. En este caso, la capacidad del corte es la suma de la capacidad de cada arista y vértice del mismo.

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 de bordes disjuntos, se nos da un gráfico no dirigido G $= (V, E)$ y dos vértices $s$ y $t$ , y tenemos que encontrar el número máximo de caminos st de bordes disjuntos en $G.$

El teorema de Menger establece que el número máximo de caminos st con aristas disjuntas en un gráfico 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 ingresos $r (p i)$ y cada máquina $q j$ cuesta $c (q j)$ comprar. Cada proyecto requiere una cantidad de máquinas y cada máquina puede ser compartida por varios proyectos. El problema es determinar qué proyectos y máquinas deben seleccionarse y comprarse respectivamente, para maximizar el beneficio.

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 se puede formular 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 (pi)$ y el sumidero está conectado mediante 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 una máquina $q j$ . El primer conjunto de cortes representa los proyectos y máquinas en $P$ y $Q$ respectivamente. Según el teorema del corte mínimo del flujo máximo, se puede resolver el problema como un problema de flujo máximo .

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

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

La idea aquí es hacer "fluir" las ganancias de cada proyecto a través de las "tuberías" de sus máquinas. Si no podemos llenar la tubería con una máquina, el rendimiento de la máquina es menor que su costo, y al algoritmo de corte mínimo le resultará más barato reducir 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$ . Hay una penalización de $p ij$ si los píxeles $i, j$ son adyacentes y tienen asignaciones diferentes. El problema es 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 se puede formular 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 construyendo una red donde la fuente (nodo naranja) está conectada a todos los píxeles con capacidad $f i$ y el sumidero (nodo morado) está conectado por todos los píxeles con capacidad. $b i$ . Se agregan dos bordes ( $i, j$ ) y ( $j, i$ ) con capacidad $p ij$ entre dos píxeles adyacentes. El st cut-set representa los píxeles asignados al primer plano en $P$ y los píxeles asignados al fondo en $Q.$

Historia

Ford y Fulkerson dieron un relato del descubrimiento del teorema en 1962: ^[5]

"La determinación de un flujo máximo en estado estacionario de un punto a otro en una red sujeta a limitaciones de capacidad en los arcos... fue planteada a los autores en la primavera de 1955 por TE Harris, quien, junto con el General FS 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. No pasó mucho tiempo hasta que se obtuvo el resultado principal, el teorema 5.1, al que llamamos teorema de flujo máximo y corte mínimo. fue conjeturado y establecido ^[6] Desde entonces han aparecido varias pruebas ". ^[7]^[8]^[9]

Prueba

Sea $G = (V, E)$ una red (gráfico dirigido) donde $s$ y $t$ son la fuente y el sumidero de $G$ respectivamente.

Considere el flujo $f$ calculado para $G$ mediante el algoritmo de Ford-Fulkerson . En el gráfico residual $($ $G$ $f$ $)$ obtenido para $G$ (después de la asignación de flujo final mediante el algoritmo 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$

Afirmar. $valor (f) = c (A, A c)$ , donde la capacidad de un corte st está definida 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 $valor($ $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 consideramos dos casos:

En $G$ , existe un borde saliente tal que no está saturado, es decir, $f$ $($ $x$ $,$ $y$ $) <$ $c$ $xy$ . Esto implica que existe un borde delantero 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 borde saliente $($ $x$ $,$ $y$ $)$ está completamente saturado. $(x,y),x\in A,y\in A^{c}$

En $G$ , existe un borde entrante tal que transporta algún flujo distinto de cero, es decir, $f$ $($ $y$ $,$ $x$ $) > 0$ . Esto implica que existe un borde hacia atrás 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 prueban que la capacidad de corte obtenida de la forma descrita anteriormente es igual al caudal obtenido en la red. Además, el flujo se obtuvo mediante el algoritmo Ford-Fulkerson , por lo que también es el flujo 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.

Ver también

Referencias

^ Dantzig, GB; Fulkerson, DR (9 de septiembre de 1964). "Sobre el teorema de redes de flujo máximo y corte mínimo" (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 LP de flujo máximo y corte mínimo".
^ Cederbaum, I. (agosto de 1962). "Sobre el funcionamiento óptimo de las redes de comunicación". Revista del Instituto Franklin . 274 : 130-141.
^ 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", Canadian Journal of Mathematics 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. Transacciones sobre teoría de la información, 2 (4): 117-119
^ George Dantzig y DR Fulkerson (1956) "Sobre el teorema de redes Max-Flow MinCut", en Desigualdades lineales , Ann. Matemáticas. Estudios, núm. 38, Princeton, Nueva Jersey
^ LR Ford y DR Fulkerson (1957) "Un algoritmo simple para encontrar los flujos máximos de red y una aplicación al problema de Hitchcock", Canadian Journal of Mathematics 9: 210–18

Eugenio 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 . Saltador. págs. 93-100. ISBN 3-540-65367-8.