Prova di Lemma per il flusso nel grafico residuo

Question

A CLRS 3'RD Edition c'è un Lemma 26.2 che afferma che:

.

Let $ G= (V, E) $ BE Una rete di flusso, lascia $ f $ essere un flusso in $ G, $ e let $ p $ essere un percorso di aumentazione in $ G_ {f} $ . Definisci una funzione $ f_ {p} \ Colon V \ Times V \ RightArdrow \ mathbb {r} $ di $$ f_ {p} (u, v)=sinistra {\ begin {array} {ll} c_ {f} (P) & \ testo {se} (u, v) \ testo {su} p \\ 0 & \ testo {altrimenti} \ end {array} \ destra. $$ Quindi, $ f_ {p} $ è un flusso in $ G_ {f} $ con valore $ \ sinistra | f_ {p} \ destra |= c_ {f} (P)> 0 $

Come vasti dimostrare questo?

Come capisco dobbiamo controllare la conservazione del flusso e il vincolo della capacità. Sappiamo che $ c_f (p) $ è il minimo delle capacità residue sul percorso $ p $ che è più piccolo delle capacità, quindi il vincolo della capacità è soddisfatto. Ma che ne dici del vincolo di conservazione del flusso e dimostrare che il valore di flusso è in realtà $ c_f (P)> 0 $ ?

Answer 1

Osservare che se $ V $ non è un vertice di $ p $ , quindi $ f_p (u, v)= 0 $ . Quando $ V $ è in $ p $ e non una fonte né un lavandino, allora ce ne sono solo due Verticanti $ V_1 $ e $ v_2 $ In tal modo i bordi $ (v_1, V), (v, v_2) $ in $ p $ . Pertanto, nel flusso eccessivo a $ V $ $$ \ sum_u f_p (u, v) $$ ha solo due termini non zero $ f_p (v_1, v)= c_f (p) $ e $ f_p (v_2, v)= - f_p (v, v_2)= - c_f (p) $ .

Quindi, il flusso eccessivo è zero.

per vedere che $ c_f (P)> 0 $ Recupera che è definito come il minimo delle capacità residue dei bordi di $ P $ . Ci sono limitati molti bordi in $ P $ e per definizione del percorso di aumentazione le capacità residue dei suoi bordi sono positive. Quindi, stai prendendo il minimo di numeri positivi finalmente. Che si traduce in un numero positivo.