Valor máximo de flujo obtenido con caminos de aumento en un digrafo tipo cuadrícula

Question

Dado el flujo de red $R = (G, s, t, c)$, donde el digrafo $G = (V, E)$ se ve así

y la malla $G - \{s, t\}$ tiene $n \times n$ vértices, orientados de norte a sur, de oeste a este con todas las aristas de capacidad $1$, necesito demostrar que comenzando con un flujo nulo y continuando con crecimientos sucesivos en caminos aumentantes solo con arcos hacia adelante es posible alcanzar solo un valor de flujo de $1$.

No estoy seguro sobre los arcos verticales que conectan las "filas" de la malla en el digrafo G, porque estos no parecen ser arcos hacia adelante o arcos hacia atrás.

La pregunta final es... ¿Cómo debería empezar a abordar esto? Creo que entiendo la pregunta pero no tengo idea de por dónde empezar.

Answer 1

No se puede estar al 100% seguro con respecto al vocabulario en teoría de grafos, así que por favor verifique con su profesor (a partir de su redacción supongo que esta es una tarea de clase), pero me parece que "caminos de aumento solo con arcos hacia adelante" significa "caminos de aumento cuya dirección se alinea con la dirección de las flechas en $R$".

De hecho, si no pudieras usar los arcos verticales, entonces cualquier algoritmo razonable de flujo de aumento encontrará el flujo máximo, es decir, $n$. La razón es que entonces tienes solo $n$ caminos disjuntos que juntos constituyen el flujo máximo.

Suponiendo que esta comprensión es correcta, aquí hay algunas indicaciones:

Pista:

1. En este grafo hay solo un flujo máximo que consiste en $n$ caminos que usan solo arcos horizontales. Primero, intenta obtener algún flujo con un valor más pequeño.
2. Lo anterior ya es una pequeña pista para la solución: tienes que usar los arcos verticales para tener éxito en tu tarea.

Más pistas:

3. Puedes bloquear los caminos de flujo máximo usando sus arcos: como no puedes usar arcos hacia atrás, el camino óptimo no puede reclamar ese arco nuevamente.

4. Intenta encontrar un camino de valor $1$ que bloquee todos los demás caminos.

Solución:

Sea $A$ un camino de aumento de esta forma y valor $1":

entonces no hay otro camino de aumento que use solo arcos hacia adelante. La razón es que $G' = (V, E(G) - E(A))$ es un grafo en el que $s$ y $t$ están en dos componentes débilmente conectadas diferentes, en particular no hay camino de $s$ a $t$.

Espero que esto ayude $\ddot\smile$