Intenté buscar en todas partes en línea sobre la intuición detrás del aumento de rutas en gráficos residuales y todo lo que realmente obtuve es cómo resolver sistemáticamente el problema de encontrar el flujo máximo sin comprender realmente por qué funciona.
Mi entendimiento es que el teorema del camino creciente (Ford-Fulkerson, 1956) dice que un flujo f es un flujo máximo si y solo si no hay caminos crecientes.
Pero, ¿por qué es esto cierto? ¿Cómo puedo ver esto intuitivamente?
También entiendo que los gráficos residuales tienen bordes que "envían el flujo hacia atrás" como una forma de "deshacer" un camino posiblemente malo. Pero en los ejemplos que vi, un camino se "deshace" y luego nunca se vuelve a usar, simplemente terminamos teniendo menos capacidad para fluir. Pero lo más probable es que no entienda completamente los bordes posteriores de los gráficos residuales.
Digamos que tenemos una ruta de aumento
Primero, podemos transportar directamente más flujo desde a a .
Anteriormente estábamos transportando algo de flujo desde a , pero ahora que hemos logrado que fluya de otra manera, no necesitamos transportar tanto flujo de a . Esto libera algo de flujo de para enviar a otro lado.
Luego, podemos enviar el flujo liberado desde a a .
La lógica en el punto 2 es generalmente la lógica detrás de los bordes hacia atrás.
Esto explica por qué aumentar las rutas nos ayuda a aumentar el valor del flujo. Por sí mismo, no prueba el teorema que dice que aumentar los caminos es esencialmente la única forma de aumentar el valor del flujo; si no existe una ruta de aumento, entonces el flujo no se puede aumentar.
La lógica aquí es que si no existe una ruta de aumento, entonces en el gráfico residual, no hay una ruta desde la fuente. al fregadero . Podemos dividir los vértices en dos conjuntos: , el conjunto de vértices accesibles desde en el gráfico residual, y , los vértices no accesibles desde . No hay bordes de ninguna a en el gráfico residual, o de lo contrario seríamos capaces de alcanzar de , también.
Esto significa que cada arco de a en la red debe estar a plena capacidad, y cada arco de a debe tener caudal cero. Esto significa que el flujo neto que sale ir a es lo más grande que podría ser, y en particular el flujo que va desde a no se puede aumentar.