Vocabulario:
viable | , es decir, el flujo es como mucho igual a la capacidad |
conservante | , es decir, tanto como entra sale de un nodo |
(claro, excepto para fuente y afluente). |
Teorema (Ford-Fulkerson):
Máximo flujo es igual a mínimo corte.
Algoritmo de FORD-FULKERSON, complejidad siendo el máximo flujo (asumiendo enteros como capacidades).
Algoritmo de EDMONDS-KARP, complejidad .
Algoritmo de DINIC, complejidad .
Algoritmo de KARZANOV-GOLDBERG-TARJAN, complejidad .
Se puede variar las resticciones: capacidades máximas por nodos, más de una fuente o afluente, introducción de capacidades mínimas,