Gráfico residual en flujo máximo

14

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?

csds
fuente

Respuestas:

28

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):Gfe/cefeece

Ejecutando ejemplo

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 ePst ); es decir, todos los bordes en P tienen capacidad disponible.e(ePfe<ceP
  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 ) .ΔΔPΔ=mineP(cefe)
  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:GP1P2P3

Posible ejecución del enfoque codicioso para un flujo máximo

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 )?P3P1P2

Camino de bloqueo

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:wv

Flujo hacia atrás

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 :RGGe=(u,v)G

  • Un borde delantero con capacidad c e - f e , si c e - f e > 0 .e=(u,v)cefecefe>0

  • Un borde hacia atrás con capacidad f e , si f e > 0 .e=(v,u)fefe>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):RP3

Gráfico residual

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 :wvstR

Ruta de aumento en el gráfico residual

En general:

Cuando se selecciona una ruta de aumento en el gráfico residual R :PR

  • Cada borde en que corresponde a un borde delantero en GPG 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.PG

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.GfGst

Mario Cervera
fuente
¿Hay algún ejemplo en el que se agreguen rutas en el orden de longitud más corta como se describe en el algoritmo Edmonds-Karp? En su contraejemplo, la primera ruta es de longitud 3, mientras que se puede encontrar una ruta más corta (es decir, 2) y se agregaría primero si estamos haciendo Edmonds-Karp.
Roy
Simplemente puede hacer que todas rutas s - t en el gráfico original tengan longitud 3 . Para hacerlo, divide el vértice v en dos vértices v 1 y v 2 . A continuación, dividir w en w 1 y w 2 . Agregue también dos aristas ( v 1 , v 2 ) y ( w 1 , w 2 v 1 a w 2st3vv1v2ww1w2(v1,v2) con capacidad 2 . El borde que originalmente pasó de v a w ahora pasará de(w1,w2)2vwv1w2 . Podemos obtener el mismo tipo de flujo de bloqueo si elegimos inicialmente la ruta que contiene el borde . (v1,w2)
Mario Cervera
Tu ejemplo tiene sentido. Siempre podemos extender el gráfico en otros bordes en el corte para que el borde en cuestión esté en uno de los caminos más cortos.
Roy
3

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 AUNsisiUNUNsi

Banach Tarski
fuente