FLUJOS MÁXIMOS
Estructuras y Algoritmos de Procesamiento de Datos II
EJEMPLOS
Formulario
C=Capacidad
I,j=inicios de los nodos
K=Flujo mínimo del camino seleccionado
Cij,ji= Ci-K,CJ+K
Pasos
-
Identificar los nodos de origen y destino.
-
Identificar la capacidad más alta que sale del nodo origen
-
Identificar el nodo intermediario con [af,i]
-
Repetir como si el nodo intermediario fuera nodo de origen
Hallar el flujo máximo que puede circular en el siguiente grafo.
Elegimos el mayor fujo como primer camino, y realizamos el paso 3.
Hallamos K.
K=min{∞,70,15}
K=15
C02,02= C(70-15,0+15)
C02,02= C(55,15)
C23,32= C(15-15,0+15)
C23,32= C(0,15)
Actualizamos el grafo.
Hallamos K.
K=min{∞,55,10,50}
K=10
C02,02= C(55-10,15+10)
C02,02= C(45,25)
C21,12= C(10-10,25+10)
C21,12= C(0,35)
C13,31= C(50-10,0+10)
C13,31= C(40,10)
Actualizamos el grafo.
Hallamos K.
K=min{∞,30,40,}
K=30
C01,10= C(30-30,0+30)
C01,10= C(0,30)
C13,31= C(40-30,30+10)
C13,31= C(10,40)
Actualizamos el grafo.
Como ya no podemos hallar otro camino finalizamos las iteraciones.
Hallamos la sumatoria de K el cual es el FLUJO MAXIMO que puede circular en este grafo.
FM=∑K=15+10+30
FM=55
El flujo máximo que puede circular en el grafo es 55.