1. Red residual:
Imagine que tiene una red con una (s) fuente (s), un sumidero (t) y bordes con capacidades que representan el flujo máximo permitido a través de cada borde. Una * red residual * es una representación de la capacidad restante en la red * después de * una cierta cantidad de flujo ya se ha impulsado a través de ella.
Así es como funciona:
* Bordes delanteros: Para cada borde (u, v) en la red original con capacidad C (u, v) y flujo de corriente f (u, v), la red residual incluye un borde * (u, v) correspondiente con capacidad C F (U, V) =C (U, V) - F (U, V). Esto representa la capacidad restante disponible en el borde.
* Bordes hacia atrás: La parte crucial es que la red residual *también *incluye *bordes hacia atrás *. Para cada borde (u, v) en la red original con flujo de corriente f (u, v), la red residual contiene un borde hacia atrás (V, u) con capacidad C F (V, U) =F (U, V). Esto representa la posibilidad de * empujar el flujo hacia atrás * a lo largo del borde, cancelando efectivamente parte del flujo ya enviado. La capacidad del borde hacia atrás es igual al flujo actualmente en el borde hacia adelante, porque solo puede retroceder la cantidad de flujo que ya está allí.
En esencia, la red residual muestra la capacidad disponible para los cambios en el flujo. Se adapta dinámicamente a medida que el flujo se empuja a través de la red. Encontrar una ruta de aumento (explicada a continuación) en la red residual significa que todavía hay potencial para aumentar el flujo total de la fuente al fregadero.
2. Ruta de aumento:
Una * ruta de aumento * es una ruta simple (sin vértices repetidos) en la red residual que conduce desde los fuente al fregadero (t). Crucialmente, representa una forma de aumentar el flujo total a través de la red.
La cantidad por la cual el flujo se puede aumentar a lo largo de la ruta de aumento está determinada por la *capacidad de cuello de botella *. Esta es la capacidad residual mínima entre todos los bordes en la ruta de aumento.
Por ejemplo:
Si una ruta de aumento tiene bordes con capacidades residuales de 5, 3 y 7, la capacidad del cuello de botella es 3. Luego podemos aumentar el flujo a lo largo de este camino en 3 unidades. Este proceso actualiza el flujo en la red original y posteriormente modifica la red residual.
Relación entre redes residuales y rutas de aumento:
El núcleo de muchos algoritmos de flujo máximo (como Ford-Fulkerson) es iterativamente:
1. Encuentre una ruta de aumento En la red residual actual.
2. Aumente el flujo a lo largo de ese camino por la capacidad del cuello de botella.
3. Actualice la red residual para reflejar el cambio en el flujo.
Este proceso continúa hasta que no se pueden encontrar más rutas de aumento en la red residual, momento en el cual se ha logrado el flujo máximo. El teorema de corte mínimo máximo de flujo garantiza esto.