Flujo Máximo

El uso de modelos de redes en la toma de decisiones incluye los llamados problemas de flujo máximo. En algunos problemas
el planteamiento de la red es muy evidente, no obstante, en otros casos se requiere de imaginación para representar la red
apropiadamente. Una vez construida la red, el algoritmo adecuado debe ser aplicado para la toma de decisión.
Considere una red con un nodo de entrada (o fuente) y un nodo de salida (o antifuente).
El problema del flujo máximo pregunta:
¿Cuál es la cantidad máxima de vehículos, líquido, peatones o llamadas telefónicas que pueden entrar y salir del sistema en
un periodo determinado de tiempo?
En este tipo de problemas se intenta conducir un flujo por las ramas o arcos de la red en forma óptima, aunque dicho flujo
esta limitado por restricciones diversas tales como: condiciones de la carpeta asfáltica, diámetros de tuberías, etc. Al límite
máximo del flujo de una rama se le denominara capacidad de flujo.

1) Volver a la red no dirigida

Trayectoria de aumento: OBET
Capacidad residual: {7, 5, 6}=5
Trayectoria de aumento: OADT
Capacidad residual: {5, 3, 9}=3

Trayectoria de aumento: OBADT
Capacidad residual: {2,4,6}=2

Trayectoria de aumento: OCEBDT
Capacidad residual: {4, 4, 5, 2, 4}=2

Trayectoria de aumento: OCEDT
Capacidad residual: {2, 2, 1, 2}=1

Trayectoria de aumento: OABET
Capacidad residual: {2, 1, 2, 1}=1

La cortadura es para saber si se realizo bien el ejercicio, esta consiste en cortar arcos dirigidos y
sumar los valores:

Puesto que todos los valores son mayores de 14, el ejercicio es correcto.