Prueba de lemma para flujo en gráfico residual

Question

En CLRS 3'RD Edición hay un LEMMA 26.2 que establece que:

Let $ g= (v, e) $ Be una red de flujo, deje que $ f $ ser un flujo en $ g, $ y deje que $ P $ sea una ruta de aumento en $ g_ {f} $ . Definir una función $ f_ {p} \ colon v \ veces v \ rudotrow \ mathbb {r} $ por $$ f_ {p} (u, v)=izquierda \ {\ begin {array} {ll} c_ {f} (p) & \ texto {if} (u, v) \ texto {está en} p \\ 0 & \ texto {de lo contrario} \ Fin {Array} \ Derecha. $$ Luego, $ f_ {p} $ es un flujo en $ g_ {f} $ con valor $ \ \ izquierda | f_ {p} \ derecha |= c_ {f} (p)> 0 $

¿Cómo irías a probar esto?

Como entiendo, debemos verificar la conservación de flujo y la restricción de capacidad. Sabemos que $ c_f (p) $ es el mínimo de las capacidades residuales en la ruta $ P $ que es más pequeño que las capacidades, por lo tanto, la restricción de capacidad está satisfecha. Pero, ¿qué tal la restricción de la conservación de flujo y demostrando que el valor de flujo es de hecho $ c_f (p)> 0 $ ?

Answer 1

Observa que si $ v $ no es un vértice de $ p $ , luego $ F_P (U, V)= 0 $ . Cuando $ v $ está en $ p $ y no una fuente ni un fregadero, entonces solo hay dos vértices $ v_1 $ y $ v_2 $ de tal que los bordes $ (v_1, V), (V, v_2) $ están en $ P $ . Por lo tanto, en el exceso de flujo en $ v $ $$ \ sum_u f_p (u, v) $$ Solo tiene dos términos que no tienen cero $ f_p (v_1, v)= c_f (p) $ y $ f_p (v_2, v)= - F_P (V, V_2)= - C_F (P) $ .

Entonces, el exceso de flujo es cero.

para ver que $ c_f (p)> 0 $ recuerde que se define como el mínimo de las capacidades residuales de los bordes de $ P $ . Hay finamente muchos bordes en $ P $ y por definición de ruta de aumento Las capacidades residuales de sus bordes son positivas. Por lo tanto, está tomando el mínimo de finamente muchos números positivos. Que resulta en un número positivo.