Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en...
Transcript of Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en...
![Page 1: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/1.jpg)
Problemas de Maximo Flujocomp-420
Thursday, September 26, 13
![Page 2: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/2.jpg)
Máximo Flujo
• Ejemplo de flujo clásico, capacidades en un grafo dirigido def. funcion de capacidad
• Si existe una arista (u,v) entonces no existe (v,u).
• Todos los vértices están en el camino de s a t.
Thursday, September 26, 13
![Page 3: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/3.jpg)
Máximo Flujo
• Como convertir grafos
Ejes antiparalelos
Thursday, September 26, 13
![Page 4: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/4.jpg)
Flujo MaximoMáximo Flujo
• Ejemplo de flujo clásico, flujo / capacidad
|f|=19
Thursday, September 26, 13
![Page 5: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/5.jpg)
• Para un flujo f• Restricción de Capacidad:
• Conservación de Flujo
•
Máximo Flujo
Thursday, September 26, 13
![Page 6: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/6.jpg)
• El valor |f| de un flujo f es:
• En muchos problemas nos interesa encontrar el máximo flujo
Máximo Flujo
Thursday, September 26, 13
![Page 7: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/7.jpg)
Abtracción de problemas diferentes
• Casos con multiples fuentes o sumideros
Thursday, September 26, 13
![Page 8: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/8.jpg)
The Ford-Fulkerson method
-Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar flujo en algunas aristas [ f(u,v)] y disminuirlo en otras.
Thursday, September 26, 13
![Page 9: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/9.jpg)
The Ford-Fulkerson method• La red residual Gf: con las aristas de capacidad residual (las
positivas),
Thursday, September 26, 13
![Page 10: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/10.jpg)
The Ford-Fulkerson method• La red residual, con su flujo f’ nos indica como aumentar el flujo de
la red original mediante una “función de aumento”
Cancelación
Ver la demostraciónThursday, September 26, 13
![Page 11: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/11.jpg)
The Ford-Fulkerson method• Caminos de aumento p, son caminos simples• La capacidad residual de un camino
Thursday, September 26, 13
![Page 12: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/12.jpg)
The Ford-Fulkerson method• de
Thursday, September 26, 13
![Page 13: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/13.jpg)
The Ford-Fulkerson method
Demostración inmediata por lo lemas anteriores
Thursday, September 26, 13
![Page 14: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/14.jpg)
The Ford-Fulkerson method
Thursday, September 26, 13
![Page 15: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/15.jpg)
The Ford-Fulkerson method• Un corte (S,T) en el grafo con flujo f
• El flujo neto y la capacidad del corte son:
• Nos interesa el mínimo corte, aquel con capacidad mínima de todos.
=19
=26
Thursday, September 26, 13
![Page 16: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/16.jpg)
The Ford-Fulkerson method
Nos esta llevando a que el flujo máximo esta acotado por la capacidad del corte mínimo.
Thursday, September 26, 13
![Page 17: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/17.jpg)
The Ford-Fulkerson method
Thursday, September 26, 13
![Page 18: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/18.jpg)
El algoritmo
• El algoritmo de Ford Fulkerson básico, reemplazamos f por f ↑ fp
(cada arista residual es una arista en el grafo original o bien un regreso en una arista original)
Thursday, September 26, 13
![Page 19: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/19.jpg)
Thursday, September 26, 13
![Page 20: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/20.jpg)
Thursday, September 26, 13
![Page 21: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/21.jpg)
Detalles de implementación
• Necesitamos buscar el camino de aumento con, por ejemplo, busqueda en anchura.
• Si f* denota el fujo maximo y estamos trabajando con capacidades enteras, el ciclo principal se ejecuta a lo mas f* veces
• El tiempo de buscar el camino de aumento O(V+2E) = O(E), entonces todo el algoritmo tiene O(E|f*|)
• Cuando las capacidades son enteras y |f*| es pequeño, el algoritmo funciona muy bien.
Thursday, September 26, 13
![Page 22: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/22.jpg)
Casos complicados• ¿Problemas? suponiendo capacidades enteras, la complejidad del
algoritmo es O(E |f*|)
capacidad residual de 1
siguiente red residual con camino de capacidad residual 1
siguiente red residual con camino de capacidad residual 1
Thursday, September 26, 13
![Page 23: Problemas de Maximo Flujo - cimat.mxalram/analisis_algo/clase12.pdf · -Este método se basa en redes residuales, caminos de aumento y cortes.-La linea 3 puede implica incrementar](https://reader031.fdocumento.com/reader031/viewer/2022021714/5bb986eb09d3f2fd488c371c/html5/thumbnails/23.jpg)
Extensiones
• Por supuesto que necesitamos extensiones de este algoritmo
• The Edmonds-Karp algorithm, cuando busca el camino en le grafo residual de s a t, busca el camino de distancia mas corto.
• Su complejidad es O(VE2)
Thursday, September 26, 13