Beweis von Lemma für den Fluss in Restgraphen

Question

In Clrs 3'RD Edition gibt es ein Lemma 26.2, das heißt,:

$ g= (v, e) $ Seien Sie ein Flow-Netzwerk, lassen Sie $ F $ Seien Sie ein Fluss in $ g, $ und lassen Sie $ P $ einen Augmenting-Pfad in $ g_ {f} $ . Definieren Sie eine Funktion $ F_ {P} \ colon v \ thes v \ rightarrow \ mathbb {r} $ von $$ F_ {P} (u, v)=link \ {\ starten {array} {ll} c_ {f} (p) & \ text {if} (u, v) \ text {ist auf} p \\ 0 & \ text {sonst} \ \ \ \ \ \ \ yect {arlay} \ richtig. $$ Dann ist $ f_ {p} $ ein Fluss in $ g_ {f} $ mit Wert $ \ links | f_ {p} \ Right |= c_ {f} (p)> 0 $

Wie würden Sie dies beweisen?

Wie ich verstehe, müssen wir nach Flow-Erhaltung und Kapazitätsbeschränkung prüfen. Wir wissen, dass $ c_f (p) $ das Minimum der Restkapazitäten auf dem Pfad $ P $ ist ist kleiner als die Kapazitäten, daher ist die Kapazitätsbeschränkung erfüllt. Aber wie wäre es mit der Flow-Erhaltungsbeschränkung und der Nachweis, dass der Durchflusswert tatsächlich $ C_F (P)> 0 $ ist?

Answer 1

Beachten Sie, dass, wenn $ V $ kein Scheitelpunkt von $ P $ ist, und dann $ f_p (u, v)= 0 $ . Wenn $ V $ in $ P $ ist, und keine Quelle oder kein Waschbecken, dann gibt es nur zwei Scheitelpunkte $ v_1 $ und $ v_2 $ so, dass die Kanten $ (v_1, v), (v, v_2) $ sind in $ p $ . Daher im übermäßigen Durchfluss bei $ V $ $$ \ SUM_U F_P (U, V) $$ Es hat nur zwei Nicht-Null-Begriffe $ F_P (V_1, V)= C_F (P) $ und $ f_p (v_2, v)= - F_P (V, V_2)= - C_F (P) $ .

Also ist der überschüssige Durchfluss Null.

um zu sehen, dass $ C_F (P)> 0 $ nur daran erinnert, dass er als Minimum der Restkapazitäten der Kanten von $ P $ . Es gibt endlich viele Kanten in $ P $ und per Definition von Augmenting-Pfad Die Restkapazitäten seiner Kanten sind positiv. Sie nehmen also das Minimum an endlich vieler positiver Zahlen ein. Das führt zu einer positiven Zahl.