 | Ｓがカット、ｆが流れならば
Σ｛ｆ（ｘ，ｙ）−ｆ（ｙ，ｘ）｝＝Σ｛ｆ（ｓ、ｙ）−ｆ（ｙ、ｓ）｝
（左辺：ｘはＳの点でｙはＶ（Ｄ）−Ｓの点）
（右辺：ｓは始点、ｙはＶ（Ｄ）の点）
Ｄは有向グラフ
この式が成り立つのはなぜでしょうか？
具体的な図を描いて理解したいのですがよく分かりません。
左辺を式変形して
左辺＝左辺＋Σ｛ｆ（ｘ、ｖ）−ｆ（ｖ、ｘ）｝（ｙはＶ（Ｄ）の点）
＝Σ｛ｆ（ｘ、ｙ）−ｆ（ｙ、ｘ）｝（ｘはＳの点、ｙじゃＶ（Ｄ）の点）
なぜこのような式変形になるのでしょうか？
そもそもΣ｛ｆ（ｘ、ｖ）−ｆ（ｖ、ｘ）｝（ｙはＶ（Ｄ）の点）＝０になるんですかね？
Σ｛ｆ（ｘ、ｙ）−ｆ（ｙ、ｘ）｝（ｘはＳの点、ｙじゃＶ（Ｄ）の点）が０にならないのはｘがｓの場合とありますがなぜでしょう？
教えてください
|