Prova di Lemma per il flusso nel grafico residuo
-
29-09-2020 - |
Domanda
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 $ ?
Soluzione
Osservare che se $ V $ non è un vertice di $ p $ , quindi
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.