Problema del Flujo Máximo (III)

En principio, la red residual difiere de la red original sólo en que cada arco dirigido (i→ j) que no tiene arco dirigido en la dirección opuesta (j → i) ahora se le agrega con capacidad cero. Después, las capacidades de los arcos en la red residual (llamadas capacidades residuales) se ajustan de la siguiente manera. Cada vez que se agrega una cantidad de flujo Δ a un arco i → j en la red original, la capacidad residual del arco i→ j se disminuye en Δ, pero la capacidad residual de arco j →i se aumenta en Δ. Así, la capacidad residual representa la capacidad del arco que no se usa en la red original o la cantidad de flujo en la dirección opuesta en esta red que se puede cancelar (o una combinación de ambas, si la re original tiene arcos en las dos direcciones). Así, después de asignar los diferentes flujos a la red original, la red residual muestra que tanto más se puede hacer ya se aumentando más lo flujos o cancelado los que se asignaron antes.