Teoría de grafos

Teoría de Grafos
Metodo de Ford-Fulkerson

Barquisimeto, Enero 2010
El método de Ford-Fulkerson
El método de Ford-Fulkerson depende de dos conceptos importantes: red residual y camino deaumento. Este método procede iterativamente. Comienza con f (u, v) = 0 para todo u, v V con lo que el flujo inicial vale 0. En cada iteración se incrementa el valor del flujo buscando un camino de aumento,que puede interpretarse como un camino de s a t por el cual se puede enviar más flujo y por tanto aumentar el flujo a través de este camino. Este proceso se repite hasta que no existan más caminos deaumento.
Para una red de transporte, estamos interesados en obtener la forma de utilizar óptimamente las "tuberías" de las que se dispone, dicho de otra forma queremos obtener la mayor cantidad deflujo que se pueda transportar por la red sin violar las capacidades predefinidas. El método de Ford-Fulkerson resuelve el problema del flujo máximo.
Le llamamos método y no un "algoritmo" dado quepermite varias implementaciones con diferentes tiempos de ejecución. El método Ford-Fulkerson es iterativo, puesto que se empieza con un flujo nulo (soportado por las tuberías de la red) y luego éstese va aumentando hasta que logre el mayor flujo posible sin violar las restricciones de capacidad.
Para lograr ir aumentando la cantidad de flujo transportado, en cada paso utilizaremos el conceptode ruta aumentante o semivía, la cual puede pensarse como un camino desde la fuente hasta el destino por el que se puede empujar o mandar todavía flujo. El método de Ford-Fulkerson consiste en utilizartantas rutas aumentantes como existan.
Dicho en otras palabras, la idea es encontrar conductos subutilizados entre la fuente y el destino, que pueden aumentarse hasta que una restricción decapacidad detenga el aumento.

|
La figura anterior es un Ejemplo de red de flujo en la figura izquierda. El primer valor de cada arista representa el flujo, y el segundo valor representa su...