20 Flujos

1. Flujos y redes
2. Flujos y cortes
3. Flujos y coloración

Vocabulario:

viable	$f(e)\leq w(e)$, es decir, el flujo es como mucho igual a la capacidad
conservante	$\sum_v f_{in}(e)=\sum_v f_{out}(e)$, 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 $O(F*m)$ siendo $F$ el máximo flujo (asumiendo enteros como capacidades).

Algoritmo de EDMONDS-KARP, complejidad $O(nm^2)$.

Algoritmo de DINIC, complejidad $O(n^2m)$.

Algoritmo de KARZANOV-GOLDBERG-TARJAN, complejidad $O(n^3)$.

Se puede variar las resticciones: capacidades máximas por nodos, más de una fuente o afluente, introducción de capacidades mínimas,