Preuve de lemme pour le flux dans un graphique résiduel

Question

Dans CLRS 3'RD Edition Il y a un lemme 26.2 qui indique que:

let $ g= (v, e) $ être un réseau de flux, laisse $ f $ être un flux dans $ g, $ et let $ p $ être un chemin d'augmentation de $ g_ {f} $ . Définir une fonction $ f_ {p} \ colon v \ fois v \ rightarrow \ mathbb {r} $ par $$ f_ {p} (u, v)=gaucher \ {\ commencez {array} {ll} c_ {f} (p) & \ text {si} (u, v) \ texte {est sur} p \\ 0 & \ text {sinon} \ fin {array} \ droite. $$ Ensuite, $ f_ {p} $ est un flux dans $ g_ {f} $ avec valeur $ \ Gauche | f_ {p} \ droite |= c_ {f} (p)> 0 $

Comment allez-vous faire prouver cela?

Si je comprends, nous devons vérifier la conservation des flux et la contrainte de capacité. Nous savons que $ c_f (p) $ est le minimum des capacités résiduelles sur le chemin $ p $ qui est plus petit que les capacités, d'où la contrainte de capacité est satisfaite. Mais que diriez-vous de la contrainte de conservation du flux et de prouver que la valeur de débit est en fait $ C_F (p)> 0 $ ?

Answer 1

Observez que si $ v $ n'est pas un sommet de $ p $ , alors $ f_p (u, v)= 0 $ . Quand $ v $ est dans $ p $ et non une source ni un évier, il n'y a que deux sommets $ v_1 $ et $ v_2 $ telle que les bords $ (v_1, v), (v, v_2) $ est dans $ p $ . Par conséquent, dans l'excédent de flux à $ V $ $$ \ sum_u f_p (u, v) $$ A seulement deux termes non nuls $ f_p (v_1, v)= c_f (p) $ et $ f_p (v_2, v)= - F_P (v, v_2)= - C_F (p) $ .

Donc, l'excès de flux est zéro.

Pour voir que $ C_F (P)> 0 $ Rappelez-vous simplement qu'il est défini comme le minimum des capacités résiduelles des bords de $ p $ . Il y a finement beaucoup de bords dans $ p $ et par définition du chemin augmenté, les capacités résiduelles de ses bords sont positives. Donc, vous prenez le minimum de plusieurs nombres positifs. Cela entraîne un nombre positif.