残差グラフの流れのための補題の証明

Question

CLRS 3'RD版は、それを述べているリンマ26.2があります：

$ g=（v、e）$ はフローネットワークになります、 $ f $ $ g、$ のフローになり、 $ p $ の $ g_ {f} $ 。関数を定義する $ f_ {p} \ colon v v \ times v v rightarrow \ mathbb {r} $ $$ f_ {p}（u、v）=left \ {\ begin {array} {ll} c_ {f}（p）＆\ text {if}（U、 v）\ text {in on} p \\ 0＆\ text {それ以外の場合} \ end {array} \ right。$$ その後、 $ f_ {p} $ は $ g_ {f} $ のフローです。 class="math-container"> $ \ wreat | F_ {p} \ right |= c_ {f}（p）> 0 $

これを証明することについてどう思いますか？

私たちは流れの保全と容量の制約をチェックする必要があります。 $ c_f（p）$ は、経路上の残差能力の最小値は、 $ P $ です。容量よりも小さいため、容量制約が満たされます。しかし、フロー保護制約についてはどうやって $ c_f（p）> 0 $ ？

Answer 1

$ v $ が $ p $ の頂点ではない場合、 $ f_p（u、v）= 0 $ 。 $ v $ が $ p $ の場合は、ソースもシンクではありませんが、2つしかありませんvertices $ v_1 $ と $ v_2 $ edges $（v_1、v）、（v、v_2）$ は $ p $ です。したがって、 $ v $ $$ \ sum_u f_p（u、v）$$ の過剰な流れで2つのゼロ以外の用語 $ f_p（v_1、v）= c_f（p）$ と $ f_p（v_2、 v）= - f_p（v、v_2）= - c_f（p）$ 。

だから、過剰な流れはゼロです。

$ c_f（p）> 0 $ を確認すると、 $ P $ 。 $ p $ には、かなり多くのエッジがあり、拡張パスの定義によって、そのエッジの残差容量は正です。だから、あなたは最低限の正の数の正数を取っています。それは正数になります。