CLRS -MAXFLOW拡張フロー補題26.1- defの使用を理解しないでください。証明で

Question

Cormen et。 al。、 アルゴリズムの紹介 （第3版）、私は補題26.1の証拠にラインを取得しません。これは、増加したフロー$ f uparrow f '$は$ g $のフローであり、st $ | f uparrow f' |であると述べています。 = | f |+| f '| $（これはpp。717-718です）。

私の混乱：議論するとき フロー保存 彼らは最初の行で$ f uparrow f '$の定義を使用して、v setminus {s、t } $の各$ u について

$$ sum_ {v in v}（f uparrow f '）（u、v）= sum_ {v in v}（f（u、v）+f'（u、v） - f '（ v、u））、$$

拡張された経路がとして定義されている場合

$$（f uparrow f '）（u、v）= begin {cases} f（u、v）+f'（u、v）-f '（v、u）＆ text {if $（u）＆ text 、v） in e $}、 0＆ text {それ以外の場合}。 end {case} $$

なぜ彼らは合計の「そうでなければ」条項を無視できるのですか？そのようなすべての場合において、最初の条項がゼロと評価されるとは思わない。彼らは何らかの方法で$ f $と$ f '$のフロー保護を使用していますか？

Answer 1

ノート： 以下で使用される表記と定義は、本の第3版から借用されています。

この質問に答えるために、最初に、$（u、v） notin e $の場合、フロー定義により、

$$ f（u、v）= f '（u、v）=（f uparrow f'）（u、v）= 0 、。$$

さらに、$ f '（v、u） le c_f（u、v）= f（u、v）$であるため、$ f'（v、u）= 0 $であることが得られます。これは、単に$ forall（u、v） notin e $、

$$（f uparrow f '）（u、v）= f（u、v） + f'（u、v）-f '（v、u）= 0 、。$$

したがって、増強されたフローの定義は、V Times v $のすべての$（u、v）に対して次のように一般化できます。

$$（f uparrow f '）（u、v）= f（u、v） + f'（u、v）-f '（v、u）、。$$

残りの証拠は、もちろん、テキストで明示的に説明されていないこの観察から続きます。

PS本の第3版のフローの正式な定義は、第2版とは大きく異なることに注意してください。特に、第2版には、名前付きのフロープロパティがあります ゆがんだ対称性 それには$ f（u、v）= -f（v、u）、 forall u、v in v $が必要です。このプロパティは、$（v、u） notin e $ if $（u、v） in e $および$ f（v、u）= 0 $ if $（vという仮定のために、第3版で削除されました。 、u） notin e $。このため、2つのエディションのフロー保存の定義も異なります。実際、そのような混乱の多くは、おそらく証明を簡素化することを意図したこの定義の変化から来ていますが、より困惑していることが判明しました。私は個人的に、この特定の章の本の第2版に固執したいと思います。