Gráfico residual en flujo máximo

Estoy leyendo sobre el problema de flujo máximo aquí . No pude entender la intuición detrás del Gráfico Residual. ¿Por qué estamos considerando los bordes traseros al calcular el flujo?

¿Alguien puede ayudarme a entender el concepto de Gráfico Residual?

¿Cómo cambia el algoritmo en los gráficos no dirigidos?

La intuición detrás del gráfico residual en el problema de flujo máximo está muy bien presentada en esta conferencia. La explicación es la siguiente.

Supongamos que estamos tratando de resolver el problema del flujo máximo para la siguiente red (donde cada etiqueta f e / c e denota tanto el flujo f e empujado a través de un borde e como la capacidad c e de este borde):$G$$f_e/c_e$$f_e$$e$$c_e$

Un posible enfoque codicioso es el siguiente:

1. Elija una ruta de aumento arbitraria que vaya desde el vértice fuente s hasta el vértice sumidero t de modo que ∀ $P$$s$$t$ ); es decir, todos los bordes en P tienen capacidad disponible.$\forall e \: (e \in P \rightarrow f_e \lt c_e$$P$
2. Empuje el flujo máximo posible través de este camino. El valor de Δ está determinado por el cuello de botella de P ; es decir, el borde con capacidad mínima disponible. Formalmente, Δ = min e ∈ P ( c e - f e ) .$\Delta$$\Delta$$P$$\Delta=\min_{e \in P} (c_e-f_e)$
3. Vaya al paso 1 hasta que no existan rutas de aumento.

Es decir, encuentre una ruta con capacidad disponible, envíe flujo a lo largo de esa ruta y repita.

En , una posible ejecución de la heurística anterior encuentra tres rutas de aumento P 1 , P 2 y P 3 , en este orden. Estas rutas empujan 2, 2 y 1 unidades de flujo, respectivamente, para un flujo total de 5:$G$$P_1$$P_2$$P_3$

Elegir caminos en este orden conduce a una solución óptima; sin embargo, ¿qué sucede si seleccionamos primero (es decir, antes de P 1 y P 2 )?$P_3$$P_1$$P_2$

Obtenemos lo que se llama un flujo de bloqueo : no existen más rutas de aumento. En este caso, el flujo total es 3, que no es óptimo. Este problema puede resolverse permitiendo operaciones de deshacer (es decir, permitiendo que el flujo se envíe en reversa, deshaciendo el trabajo de las iteraciones anteriores): simplemente empuje 2 unidades de flujo hacia atrás desde el vértice al vértice v de esta manera:$w$$v$

Codificar estas operaciones de deshacer permitidas es el objetivo principal del gráfico residual .

Un gráfico residual de una red G tiene el mismo conjunto de vértices que G e incluye, para cada borde e = ( u , v ) ∈ G :$R$$G$$G$$e=(u,v) \in G$

• Un borde delantero con capacidad c e - f e , si c e - f e > 0 .$e'=(u,v)$$c_e-f_e$$c_e-f_e \gt 0$

• Un borde hacia atrás con capacidad f e , si f e > 0 .$e''=(v,u)$$f_e$$f_e \gt 0$

Por ejemplo, considere el gráfico residual que se obtiene después de la primera iteración de la heurística codiciosa cuando la heurística selecciona primero P 3 (es decir, cuando obtiene el flujo de bloqueo):$R$$P_3$

Tenga en cuenta que la operación de deshacer que empuja 2 unidades de flujo de a v está codificada como una ruta de avance (aumento) de s a t en R :$w$$v$$s$$t$$R$

En general:

Cuando se selecciona una ruta de aumento en el gráfico residual R :$P'$$R$

• Cada borde en que corresponde a un borde delantero en $P'$$G$ aumenta el flujo al usar un borde con capacidad disponible.
• Cada borde en que corresponde a un borde que va hacia atrás en G deshace el flujo que se empujó hacia adelante en el pasado.$P'$$G$

Esta es la idea principal detrás del método Ford – Fulkerson .

El método Ford – Fulkerson procede exactamente de la misma manera que el enfoque codicioso descrito anteriormente, pero solo se detiene cuando no hay más rutas de aumento en el gráfico residual (no en la red original). El método es correcto (es decir, siempre calcula un flujo máximo) porque el gráfico residual establece la siguiente condición de optimización :

Dada una red , un flujo f es máximo en G si no hay una ruta s - t en el gráfico residual.$G$$f$$G$$s-t$

La intuición detrás de la red residual es que nos permite "cancelar" un flujo ya asignado, es decir, si ya hemos asignado 2 unidades de flujo de a B , luego pasar 1 unidad de flujo de B a $A$$B$$B$$A$$A$$B$