FLUJO MAXIMO Kevin Torres

FLUJO MAXIMO – EJERCICIO PROPUESTO

Solución Grafo 1:
K= min [∞, 6, 3, 2,5]
K= 2
C14,41 = (6-2, 0+2) = (4,2)
C43,34 = (3-2, 3+2) = (1,5)
C35,53 =(2-2, 2+2) = (0,4)
C57,75 = (5-2, 0+2) = (3,2)
Remplazamos en el siguiente grafo.










Solución Grafo 2:
K= min [∞, 6, 3, 4, 5, 2]
K= 2
C12,21 = (6-2,0+2) = (4,2)
C25,52 = (3-2, 3+2) = (1,5)
C53,35 = (4-2, 0+2) = (2,2)
C34,43 = (5-2, 1+2) = (3,3)
C47,74 = (2-2, 0+2) = (0,2)
Remplazamos en elsiguiente grafo.










Solución Grafo 3:
K= min [∞, 4, 2, 3, 1, 5]
K= 1
C12,21 = (4-1, 2+1) = (3,3)
C23,32 = (2-1, 2+1) = (1,3)
C34,43 = (3-1, 3+1) = (2,4)C46,64 = (1-1, 1+1) = (0,2)
C67,76 = (5-1, 0+1) = (4,1)
Remplazamos en el siguiente grafo.












Solución Grafo 4:
K= min [∞, 4, 4, 3, 1, 3]
K=1
C14,41 = (4-1, 2+1) = (3,3)
C43,34 = (4-1, 2+1) = (3,3)
C32,23 = (3-1, 1+1) = (2,2)
C25,52 = (1-1, 5+1) = (0,6)
C57,75 = (3-1, 2+1) = (2,3)Remplazamos en el siguiente grafo.









Solución Grafo 5:
K= min [∞, 3, 3, 2, 4]
K= 2
C14,41 = (3-2, 3+2) = (1,5)
C43,34 = (3-2, 3+2) = (1,5)
C36,63 =(2-2, 2+2) = (0,4)
C67,76 = (4-2, 1+2) = (2,3)


Solución Grafo 6:
K= min [∞, 3, 2, 2,2]
K= 2
C12,21 = (3-2, 3+2) = (1,5)
C23,32 = (2-2, 2+2) = (0,4)
C35,53= (2-2, 2+2) = (0,4)
C57,75 = (2-2, 3+2) = (0,5)

Reemplazando las nuevas capacidades, nos queda de la siguiente forma,   las capacidades del nodo deorigen quedan como 0, por lo cual seguimos a sumar a todas las K y ahí conseguimos el flujo máximo.
Flujo Máximo = 2+2+1+1+2+2
Flujo Máximo = 10