next up previous
Next: 21 Emparejamientos Up: Algoritmia Avanzada: Teoría de Previous: 19 Coloración

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,



© 2006, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática