Flujo máximo en redes

Flujo máximo en redes

Introducción

• El problema de flujo máximo consiste en resolver la capacidad máxima de flujo que puede incorporarse a través de la fuente y salir por el nodo de destino. Para resolver este algoritmo seguiremos estas propiedades:

Como calcular el flujo máximo

• El orden del algoritmo que sigue este procedimiento va a ser la siguiente:

• Sea G = (V, A, Cg) el grafo de capacidades máximas. Comenzar el grafo de flujos existentes, F, con nodos y aristas iguales a los de G, pero con pesos iniciales 0. Es decir, Cf (v, w) = 0; para todo [v,w] perteneciente a A. Este grafo guardará el resultado del algoritmo.

•  Averiguar un trayecto en G, desde o hasta t, yendo por aristas cuyo peso necesariamente sea superior a 0. Este trayecto es llamado camino creciente. Pensemos que el camino es (o, v1, v2, ..., vk, t). Cogemos m = min (Cg(o, v1), Cg(v1, v2), ..., Cg(vk, t)). En otras palabras, por este camino deben circular hasta m unidades de flujo, como límite.

• Para cada arista [v,w] de la vía anterior, sumar m al valor de la arista correspondiente en F y suprimir en G. Dicho de otra forma, Cf (v, w) = Cf (v, w) + m; Cg(v, w) = Cg(v, w) - m; para todo [v,w] del camino del paso 2.

• Regresar al paso 2 mientras siga encontrándose algún camino creciente entre o y t en G.

Flujo máximo deshaciendo caminos

Para determinar la solución del problema podemos hacer un mero cambio en el algoritmo. La interpretación de este cambio es que si elegimos un camino, que luego resulta ser una mala decisión, se pueda anular el flujo enviado por ese camino. Especialmente, la transformación afecta a la manera de actualizar Cg dentro del paso 3:

Para cada arista [v,w] del camino anterior, añadir m al coste de la arista correspondiente en F, quitarlo en G y ponerlo en G en sentido contrario. Es decir, Cf (v, w) = Cf (v, w) + m; Cg(v, w) = Cg(v, w) - m; Cg(w, v) = Cg(w, v) + m para todo [v,w] del camino del paso 2.

Muchas gracias por su atención

...