En informática y teoría de la 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 el menor peso total de los bordes que, si se quitaran, desconectaría la fuente del fregadero.
El flujo max min-corte teorema es un caso especial de la teorema de dualidad para programas lineales y se puede utilizar para derivar el teorema de Menger y el teorema de König-Egerváry . [1]
Definiciones y declaración
El teorema relaciona dos cantidades: el caudal máximo a través de una red, y la capacidad mínima de un corte de la red, es decir, la capacidad mínima la alcanza el caudal.
Para enunciar el teorema, primero se debe definir cada una de estas cantidades.
Sea N = ( V , E ) una gráfica dirigida , donde V denota el conjunto de vértices y E es el conjunto de aristas. Sean s ∈ V y t ∈ V la fuente y el sumidero de N , respectivamente.
La capacidad de un borde es un mapeodenotada por c uv o c ( u , v ) , donde u , v ∈ V . Representa la cantidad máxima de flujo que puede pasar a través de un borde.
Flujos
Un flujo es un mapeo denotado por o , sujeto a las dos limitaciones siguientes:
- Restricción de capacidad : para cada borde,
- Conservación de Flujos : Para cada vértice aparte de y (es decir, la fuente y el sumidero , respectivamente), se cumple la siguiente igualdad:
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 que 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 sumidero.
El valor de un flujo se define por
donde como arriba es el nodo de origen yes el nodo receptor . En la analogía del fluido, representa la cantidad de fluido que ingresa a la red en el nodo 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 nodo sumidero.
El problema de flujo máximo solicita el flujo más grande en una red determinada.
Problema de flujo máximo. Maximizar, es decir, encaminar tanto flujo como sea posible desde a .
Cortes
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 st cortó C = ( S , T ) es una partición de V tal que s ∈ S y t ∈ T . Es decir, s - t cut 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 bordes que conectan la parte de origen del corte con la parte del fregadero:
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 una ruta en el gráfico resultante desde la fuente hasta el sumidero.
La capacidad de un corte st es el peso total de sus bordes,
dónde Si y , de lo contrario.
Por lo general, 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 en st mínimo. Minimice c ( S , T ) , es decir, determine S y T de manera que la capacidad del corte ST sea mínima.
Teorema principal
El teorema principal vincula el flujo máximo a través de una red con el corte mínimo 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.
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 primarios y duales. [2]
Flujo máximo (primario) | Corte mínimo (doble) | |
---|---|---|
variables | [una variable por borde] | [una variable por borde] [una variable por nodo no terminal] |
objetivo | maximizar [flujo total máximo de la fuente] | minimizar [capacidad mínima total de bordes en corte] |
limitaciones | sujeto a [una restricción por borde y una restricción por nodo no terminal] | sujeto a [una restricción por borde] |
firmar restricciones |
El LP de flujo máximo es sencillo. El LP dual se obtiene utilizando el algoritmo descrito en el programa lineal dual . El LP resultante requiere alguna explicación. La interpretación de las variables en el LP min-cut es:
El objetivo de minimización suma la capacidad sobre todos los bordes que están contenidos en el corte.
Las limitaciones garantizan que las variables representen efectivamente un recorte legal: [3]
- Las limitaciones (equivalente a ) Garantía de que, para los nodos no terminales U, V , si u es en S y v es en T , a continuación, el borde ( u , v ) se cuenta en el corte ().
- Las limitaciones (equivalente 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 ).
- Las limitaciones (equivalente 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 ).
Tenga en cuenta que, dado que este es 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.
Ejemplo
La figura de la derecha es una red que tiene un valor de flujo de 7. La anotación numérica en cada flecha, en la forma x / y , indica el flujo ( x ) y la capacidad ( y ). Los flujos que emanan de la fuente suman siete (4 + 3 = 7), al igual que los flujos hacia el sumidero (3 + 4 = 7).
El vértice en blanco y los vértices en gris forman los subconjuntos S y T de un corte st, cuyo cut-set contiene los bordes discontinuos. Dado que la capacidad del corte st es 7, que es igual al valor del flujo, el teorema de corte mínimo de flujo máximo indica que el valor del flujo y la capacidad del corte st son óptimos en esta red.
Tenga en cuenta que el flujo a través de cada uno de los bordes punteados está a plena capacidad: este es el "cuello de botella" del sistema. Por el contrario, hay capacidad de reserva en la parte derecha de la red. En particular, el flujo del nodo uno al nodo dos no necesita ser igual a 1. Si no hubiera flujo entre los nodos uno y dos, entonces las entradas al sumidero cambiarían a 4/4 y 3/5; el flujo total aún sería siete (4 + 3 = 7). Por otro lado, si el flujo del nodo uno al nodo dos se duplicara a 2, entonces las entradas al sumidero cambiarían a 2/4 y 5/5; el flujo total volvería a permanecer en siete (2 + 5 = 7).
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 por 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 como el voltaje de entrada V en enfoques , es igual al peso del conjunto de corte de peso mínimo.
Teorema de corte mínimo de flujo máximo generalizado
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 flujos, sino también la restricción de capacidad del vértice
En otras palabras, la cantidad de flujo que pasa por un vértice no puede exceder su capacidad. Definir un corte st para el conjunto de vértices y aristas tal que para cualquier trayectoria desde s a t , la ruta contiene un miembro del corte. En este caso, la capacidad del corte es la suma de la capacidad de cada borde y vértice en el 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 no dirigido problema caminos borde-disjuntos, 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 borde-disjuntos caminos st en G .
El teorema de Menger establece que el número máximo de caminos st disjuntos de aristas en un gráfico no dirigido es igual al número mínimo de aristas en un conjunto de cortes 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 comprar c ( q j ) . Cada proyecto requiere varias 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, de modo que se maximice 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,
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,
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 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 st cut-set representa los proyectos y las máquinas en P y Q respectivamente. Mediante el teorema de flujo máximo y corte mínimo, 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:
Proyecto r ( p i ) | Máquina c ( q j ) | ||
---|---|---|---|
1 | 100 | 200 | El proyecto 1 requiere las máquinas 1 y 2. |
2 | 200 | 100 | El proyecto 2 requiere la máquina 2. |
3 | 150 | 50 | El proyecto 3 requiere la máquina 3. |
La capacidad mínima de un corte st es 250 y la suma de los ingresos de cada proyecto es 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" los beneficios del proyecto a través de las "tuberías" de la máquina. Si no podemos llenar la tubería, el retorno de la máquina es menor que su costo, y el algoritmo de corte mínimo encontrará que es más barato reducir la ventaja de las ganancias del proyecto en lugar del costo 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 es asignar píxeles al primer plano o al fondo de manera 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,
Este problema de maximización se puede formular como un problema de minimización, es decir,
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 púrpura) está conectado por todos los píxeles con capacidad. b i . Se añaden dos bordes ( i, j ) y ( j, i ) con capacidad p ij entre dos píxeles adyacentes. El corte-set st representa entonces los píxeles asignados al primer plano en P y los píxeles asignado a fondo en Q .
Historia
Ford y Fulkerson dieron una descripción del descubrimiento del teorema en 1962: [5]
"La determinación de un flujo de estado estable máximo de un punto a otro en una red sujeta a limitaciones de capacidad en los arcos ... fue propuesto 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 había identificado este problema particular como el central sugerido por el modelo. No pasó mucho tiempo hasta que el resultado principal, el teorema 5.1, que llamamos el teorema de flujo máximo y corte mínimo, fue conjeturado y establecido. [6] Desde entonces han aparecido varias pruebas ". [7] [8] [9]
Prueba
Deje que G = ( V , E ) ser una red (gráfico dirigido) con s y t es la fuente y el disipador de G respectivamente.
Considere el flujo f calculado para G por el algoritmo de Ford-Fulkerson . En el gráfico residual ( G f ) obtenido para G (después de la asignación de flujo final por 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
Afirmar. valor ( f ) = c ( A , A c ) , donde la capacidad de un corte st se define por
- .
Ahora sabemos, para cualquier subconjunto de vértices, A . Por lo tanto, para el valor ( f ) = c ( A , A c ) necesitamos:
- 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 una ventaja 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 desde s a y en G f , que es una contradicción. Por lo tanto, cualquier borde saliente ( x , y ) está completamente saturado.
- En G , existe un borde entrante tal que lleve algún flujo distinto de cero, es decir, f ( y , x )> 0 . Esto implica, que existe un filo hacia atrás desde x a y en G f , por lo tanto, existe un camino desde s a y en G f , que es de nuevo una contradicción. Por lo tanto, cualquier borde entrante ( y , x ) debe tener flujo cero.
Ambas afirmaciones anteriores prueban que la capacidad de corte obtenida de la manera descrita anteriormente es igual al caudal obtenido en la red. Además, el flujo se obtuvo mediante el algoritmo de 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 bordes 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 las redes de corte mínimo de flujo máximo de redes" (PDF) . Corporación RAND : 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 min-cut max-flow" .
- ^ Cederbaum, I. (agosto de 1962). "Sobre el óptimo funcionamiento 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 MR0159700
- ^ 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 las redes MinCut de flujo máximo", en Desigualdades lineales , Ann. Matemáticas. Estudios, no. 38, Princeton, Nueva Jersey
- ^ LR Ford y DR Fulkerson (1957) "Un algoritmo simple para encontrar los flujos de red máximos y una aplicación al problema de Hitchcock", Canadian Journal of Mathematics 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, 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 LP-Duality". Algoritmos de aproximación . Saltador. págs. 93–100. ISBN 3-540-65367-8.