Prova de lema para fluxo em gráfico residual

Question

em Clrs 3'rd Edition há um lema 26.2, que afirma que:

.

Deixe $ g= (v, e) $ ser uma rede de fluxo, deixe $ F $ Seja um fluxo em $ g, $ e deixe $ p $ ser um caminho de aumento na $ g_ {f} $ . Defina uma função $ f_ {p} \ colon v \ vezes v \ righttarrow \ mathbb {r} $ por $$ f_ {p} (u, v)=left \ {\ iniciar {disca} {ll} c_ {f} (p) & \ text {} (u} v) \ text {está em} p \\ 0 & \ text {de outra forma} \ end {matray} \ direita. $$ Então, $ f_ {p} $ é um fluxo em $ g_ {f} $ com valor $ \ left | f_ {p} \ direito |= c_ {f} (p)> 0 $

Como você iria provar isso?

Como eu entendo, precisamos verificar se há conservação de fluxo e restrição de capacidade. Sabemos que $ c_f (p) $ é o mínimo das capacidades residuais no caminho $ P $ que é menor que as capacidades, daí a restrição de capacidade é satisfeita. Mas como sobre a restrição de conservação de fluxo e provando que o valor do fluxo é, na verdade, $ c_f (p)> 0 $ ?

Answer 1

Observe que, se $ v $ não é um vértice de $ P $ , então $ f_p (u, v)= 0 $ . Quando $ v $ está em $ P $ e não uma fonte nem pia, então há apenas dois vértices $ v_1 $ e $ v_2 $ tal que as bordas $ (v_1, v), (v, v_2) $ estão em $ p $ . Portanto, no fluxo excessivo em $ v $ $$ \ sum_u f_p (u, v) $$ só tem dois termos não zero $ f_p (v_1, v)= c_f (p) $ e $ f_p (v_2, v)= - f_p (v, v_2)= - c_f (p) $ .

Então, o fluxo excessivo é zero.

Para ver que $ c_f (p)> 0 $ Apenas lembre que é definido como o mínimo das capacidades residuais das bordas da $ P $ . Há finitamente muitas bordas na $ P $ e por definição de caminho de aumento as capacidades residuais de suas bordas são positivas. Então, você está tomando o mínimo de muitos números positivos finitamente. Que resulta em um número positivo.