Buenas, no entiendo mucho la condición del while de este algoritmo. Se supone que se saldrá del while cuando no exista un camino s-t en el grafo residual. Lo que no entiendo es, en qué momento sucede de que no haya un camino s-t en el grafo residual? Lo único que se me ocurrió es que eso suceda cuando todas las aristas salientes de s estén saturadas y por lo tanto solo haya aritas backward hacia s. Pero si fuera por eso, no podría existir un flujo máximo en el que no todas las aristas salientes de s tienen un flujo igual a la capacidad de la arista o sea que no todas estén saturadas?
Hola.
Sí, el ciclo termina cuando en el grafo residual no hay ningún camino s-t. Eso ocurre cuando en algún corte s-t, (A,B), en cada arista saliente de A el flujo es igual a su capacidad y en cada arista entrante en A el flujo es 0. O sea, cuando la diferencia entre el flujo saliente de A y el flujo entrante en A (que siempre es igual al valor del flujo) es igual a la capacidad del corte. Como consecuencia, en el grafo residual por cada arista saliente de A solo hay una arista backward, que es entrante en A, y por cada arista entrante en A solo hay una arista forward, que también es entrante en A. Por lo tanto no hay aristas salientes de A, por lo que no se puede alcanzar ningún vértice de B desde A. Entonces, como s pertenece a A y t pertenece a B, no hay camino s-t.
El corte no tiene por qué ser el que separa a s del resto, esto es ({s}, V \ {s}), ni tampoco el simétrico de este, el que separa a t del resto, (V \ {t}, {t}).
Lo que se cumple es que (A,B) tiene que ser un corte de capacidad mínima, porque la capacidad de cualquier corte s-t es mayor o igual al valor de cualquier flujo, en particular del flujo máximo.
Veamos un ejemplo casi mínimo. En la red de flujo G los vértices son s, u, w y t, y las aristas son (s,u) de capacidad 3, (u,w) de capacidad 1 y (w,t) de capacidad 3. Con flujo inicial 0 en cada arista la red G sería asÍ;
s --- 0 / 3 ---> u --- 0 / 1---> w --- 0 / 3 ---> t
El corte s-t de capacidad mínima es ({s,u}, {w.t}), que tiene capacidad 1. El corte ({s,} {u,w,t}) tiene capacidad 3, lo mismo que el corte ({s,u,w}, {t}).
El grafo residual Gf es:
s --- 3 ---> u --- 1---> w --- 3 ---> t
Pasando una unidad de flujo por el camino (s,u,w, t) la red G queda
s --- 1 / 3 ---> u --- 1 / 1---> w --- 1 / 3 ---> t
El grafo residual pasa a ser
s --- 2 ---> u <--- 1--- w --- 2 ---> t
<---1--- <---1 ---
En el corte s-t (A,B) donde A = {s,u}y B = {w,t} no hay ninguna arista saliente de A. Este es el corte que habíamos visto que tiene capacidad mínima.
En cambio, como decís al final, sí hay una arista saliente de s con flujo menor a su capacidad (y también una arista entrante con flujo menor a su capacidad).
¿Responde esto a la duda?
Sí, el ciclo termina cuando en el grafo residual no hay ningún camino s-t. Eso ocurre cuando en algún corte s-t, (A,B), en cada arista saliente de A el flujo es igual a su capacidad y en cada arista entrante en A el flujo es 0. O sea, cuando la diferencia entre el flujo saliente de A y el flujo entrante en A (que siempre es igual al valor del flujo) es igual a la capacidad del corte. Como consecuencia, en el grafo residual por cada arista saliente de A solo hay una arista backward, que es entrante en A, y por cada arista entrante en A solo hay una arista forward, que también es entrante en A. Por lo tanto no hay aristas salientes de A, por lo que no se puede alcanzar ningún vértice de B desde A. Entonces, como s pertenece a A y t pertenece a B, no hay camino s-t.
El corte no tiene por qué ser el que separa a s del resto, esto es ({s}, V \ {s}), ni tampoco el simétrico de este, el que separa a t del resto, (V \ {t}, {t}).
Lo que se cumple es que (A,B) tiene que ser un corte de capacidad mínima, porque la capacidad de cualquier corte s-t es mayor o igual al valor de cualquier flujo, en particular del flujo máximo.
Veamos un ejemplo casi mínimo. En la red de flujo G los vértices son s, u, w y t, y las aristas son (s,u) de capacidad 3, (u,w) de capacidad 1 y (w,t) de capacidad 3. Con flujo inicial 0 en cada arista la red G sería asÍ;
s --- 0 / 3 ---> u --- 0 / 1---> w --- 0 / 3 ---> t
El corte s-t de capacidad mínima es ({s,u}, {w.t}), que tiene capacidad 1. El corte ({s,} {u,w,t}) tiene capacidad 3, lo mismo que el corte ({s,u,w}, {t}).
El grafo residual Gf es:
s --- 3 ---> u --- 1---> w --- 3 ---> t
Pasando una unidad de flujo por el camino (s,u,w, t) la red G queda
s --- 1 / 3 ---> u --- 1 / 1---> w --- 1 / 3 ---> t
El grafo residual pasa a ser
s --- 2 ---> u <--- 1--- w --- 2 ---> t
<---1--- <---1 ---
En el corte s-t (A,B) donde A = {s,u}y B = {w,t} no hay ninguna arista saliente de A. Este es el corte que habíamos visto que tiene capacidad mínima.
En cambio, como decís al final, sí hay una arista saliente de s con flujo menor a su capacidad (y también una arista entrante con flujo menor a su capacidad).
¿Responde esto a la duda?