Ejemplo Algoritmo para el problema del flujo máximo (III)

Si se emplea este último método, existe un flujo a través de un arco si la capacidad residual final es mejor que la capacidad original. La magnitud de este flujo es igual a la diferencia entre estas capacidades. En la figura 10.6 se muestra el patrón de flujo óptimo que resulta al comparar la red que se obtuvo en la última iteración con la figura 10.5.

Este ejemplo ilustra en forma sencilla la razón para sustituir el arco i →j en la red residual y después aumentar en c* la capacidad residual de éste último cuando se asigna un flujo de c* al arco i →j. Sin este refinamiento, las primeras seis iteraciones no cambian, pero en ese momento pareceria que ya no quedan trayectorias aumentadas (ya que la capacidad de flujo real sin usar de E → B es cero). El refinamiento permite agregar la asignación de un flujo de 1 para O→C→E→B→D→T en la iteración 7. En efecto, esta asignación adicional cancela una unidad de flujo asignada en la iteración 1 (O→B→E→T) y la sustituye por las asignaciones de una unidad a las dos rutas O→B→D→T y O→C→E→T.