Gráfico Residual (Max - Flow) - Intuición y corrección

Primero, pensemos en el flujo no en términos de su estructura global (la suma de caminos ponderados desde$X$a$Y$) sino en términos de su estructura local (una asignación de valores a cada borde tal que el flujo de entrada total es igual al flujo de salida total en cada vértice excepto$X$y$Y$).

Por supuesto, en ambas interpretaciones, todavía hay que considerar las capacidades en los bordes.

Dados dos flujos diferentes, defina su diferencia como la asignación de valores a los bordes que asigna a cada borde la diferencia entre el primer flujo en ese borde y el segundo flujo. ¿Por qué nos importa esta diferencia para empezar? Porque si queremos pasar del flujo de la Figura 2a al flujo de la Figura 1a, eso corresponde a agregar una "diferencia de flujo" a cada borde, entonces queremos saber cómo se ve la diferencia de flujo.

Una diferencia de flujo es muy parecida a un flujo: asigna valores a cada borde de modo que el flujo de entrada total sea igual al flujo de salida total en cada vértice excepto$X$y$Y$. Sin embargo, no respeta las capacidades del gráfico original. Por ejemplo, la diferencia de flujo entre la Figura 2a y la Figura 1a asigna un valor de$-1$hasta el borde$B \to C$.

Si actualmente estamos en el flujo de la Figura 2a, podemos anotar el rango de valores posibles que puede tener una diferencia de flujo entre el flujo actual y otro flujo válido. Por ejemplo, el flujo de corriente en el borde$C \to Y$es$1$; otro flujo válido puede tener cualquier valor en$[0,2]$en ese borde; por lo que la diferencia de flujo puede ser cualquier valor en el rango$[-1,1]$.

Si etiquetamos cada borde con el rango de valores posibles que puede tener una diferencia de flujo de la Figura 2a, obtenemos algo que se parece mucho al gráfico residual:

La única diferencia es que donde este gráfico tiene un solo borde con etiqueta$[-1,4]$, el gráfico residual tiene un borde delantero con etiqueta$4$y un borde posterior con etiqueta$1$. Así que vamos a explicar esa diferencia.

En una diferencia de flujo, podemos satisfacer la condición de flujo local en los vértices con algo que no parece un camino (o incluso una suma de caminos). Por ejemplo, asignando el valor$1$hasta el borde$A \to C$y el valor$-1$hasta el borde$B \to C$satisface la condición de flujo local en el vértice$C$.

Sin embargo, si tomamos cualquier camino no dirigido en esta red y le damos a cada borde a lo largo del camino el valor$1$si se lleva adelante y$-1$si se toma hacia atrás, entonces eso siempre satisfará la condición de flujo local. Por ejemplo, si tenemos bordes$u \to v$y$v \gets w$a lo largo del camino, entonces asignamos$1$al primer borde y$-1$al segundo borde, por lo que el flujo de entrada total en$v$es$1 + (-1)=0$, satisfaciendo la condición local en$v$.

Más generalmente, las diferencias de flujo válidas son precisamente las sumas ponderadas de tales caminos no dirigidos cuyos valores en cada borde están en el rango dado por la figura anterior. Entonces, si encontramos una ruta de este tipo, esa es una diferencia de flujo válida, y podemos agregar algunos múltiplos al flujo en la Figura 2a para mejorarlo. En particular, para pasar de la Figura 2a a la Figura 1a, sumamos la diferencia de flujo dada por el camino no dirigido$X \to A \to C \gets B \to D \to E \to Y$.

Pensar en caminos no dirigidos es extraño. Pero notamos que si un borde tiene etiqueta$[-a,b]$, eso significa que puede tener flujo como máximo$b$cuando se lleva adelante, y como máximo$a$cuando se toma hacia atrás. Este es exactamente el mismo comportamiento que obtendríamos si tuviéramos una ventaja con la etiqueta$[0,b]$y un borde en la dirección inversa y la etiqueta$[0,a]$- excepto entonces, no necesitaríamos tomar ningún borde hacia atrás.

(Por ejemplo, si tomamos una ventaja ficticia$C \to B$con valor$1$, que corresponde a tomar la ventaja$B \to C$con valor$-1$: pero ahora nos deja pensar en el camino dirigido$X \to A \to C \to B \to D \to E \to Y$en lugar del camino no dirigido que teníamos antes).

Así es como obtenemos el gráfico residual: es simplemente el gráfico de la figura anterior, pero cada borde que tiene un límite inferior negativo en la capacidad se reemplaza por dos bordes, uno en cada dirección, que tienen el mismo efecto.