Tema
Flujo máximo y corte mínimo
- Algoritmos
- Nivel avanzado
- Con simulador interactivo
El flujo máximo que una red puede llevar de la fuente al sumidero coincide con la capacidad del corte mínimo que los separa.
Nombre en inglés
Maximum flow and minimum cut
Intuición
La red es un sistema de tuberías y el corte mínimo es el conjunto de tuberías que, al cerrarse, deja incomunicados el origen y el destino. Ford y Fulkerson buscan caminos con capacidad libre en el grafo residual, donde cada arista usada crea una arista hacia atrás que permite deshacer decisiones anteriores. Muchos problemas de asignación y de emparejamiento se resuelven traduciéndolos a una red de este tipo.
Fórmula
valor del flujo maximo = capacidad del corte minimo ; Edmonds y Karp con recorrido en anchura cuesta O(V E^2)
Ejemplo resuelto
Sea una red con fuente S, sumidero T y dos caminos: De S a A con capacidad 3 y de A a T con capacidad 2, más de S a B con capacidad 1 y de B a T con capacidad 4. El primer camino admite 2 unidades, limitado por la arista de A a T, y el segundo admite 1 unidad, limitado por la arista de S a B. El flujo máximo vale 3, y el corte formado por esas dos aristas tiene capacidad 2 más 1, que coincide.
Errores frecuentes
- Olvidar las aristas residuales hacia atrás: Sin ellas el algoritmo se detiene en un flujo bloqueante que no es máximo.
- Elegir los caminos de aumento sin criterio: Con capacidades grandes, la elección arbitraria puede tardar en proporción al valor del flujo, mientras que buscar el camino con menos aristas acota el número de iteraciones.
- Confundir el corte mínimo con el conjunto de aristas saturadas: Toda arista del corte está saturada, pero no toda arista saturada pertenece al corte mínimo.
Ejercicio
Una red tiene dos caminos de la fuente al sumidero que no comparten aristas, con capacidades mínimas 4 y 6. ¿Cuál es el flujo máximo?
Ver la solución
Al no compartir aristas, los dos caminos se usan a la vez y sus capacidades se suman sin estorbarse.
Respuesta: 10
Temas relacionados
Cursos a los que prepara
Simulador
Este tema tiene un simulador interactivo en la guía.