algorithm - maximo - ¿Por qué se requieren bordes posteriores en el algoritmo Ford-Fulkerson?

flujo maximo

Question

Para encontrar el flujo máximo en un gráfico, ¿por qué no basta con saturar solo todas las rutas de aumento con la capacidad mínima de borde en esa ruta sin considerar los bordes posteriores? Quiero decir, ¿cuál es el punto que lo llama un borde trasero si asumimos que fluye de él?

Answer 1

Los bordes posteriores son necesarios cuando se realiza el algoritmo Ford-Fulkerson en caso de que la ruta que elija no sea parte del flujo general.

Como ejemplo donde se necesitan bordes posteriores, considere esta red de flujo:

 s
/ /
a b
/ / /
c d
/ /
t

Suponga que todos los bordes apuntan hacia abajo y que todos los bordes tienen capacidad 1 y que desea encontrar un flujo de s a t. Supongamos que en la primera iteración de Ford-Fulkerson tomas el camino s -> b -> c -> t. En este punto, has empujado una unidad de flujo de s a t. Si no agrega ningún borde posterior, queda con esto:

 s
/
a b
/ /
c d
/
t

No hay más rutas st, pero eso no significa que tenga un flujo máximo. Puede empujar dos unidades de flujo de s a t enviando una a lo largo de la ruta s -> a -> c -> t y la otra a lo largo de la ruta s -> b -> d -> t. Sin ningún borde posterior en la red de flujo residual, nunca descubriría este otro camino.

¡Espero que esto ayude!