数学 › グラフ理論 › 連結度とネットワークフロー

流量はどのカットでも測れる

補題 4.3（「連結度とネットワークフロー」§4）・ ✓公理まで証明済み

フロー $f$ と $s$ – $t$ カット $S$ について

|f|=f^+(S)-f^-(S)\le c(S)

が成り立つ。等号 $|f|=c(S)$ が成り立つのは、 $S$ から出る辺がすべて $f(e)=c(e)$ 、 $S$ に入る辺がすべて $f(e)=0$ のとき、そのときに限る。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

これを使っている定理証明で参照している 3 件

増加道が無ければ流量と等しい容量のカットがある✓補題 4.6・連結度とネットワークフロー
整数性定理✓定理 4.9・連結度とネットワークフロー
0-1 フローは道に分解できる✓補題 5.2・連結度とネットワークフロー

関連するノック 1 問

グラフ理論第 17 問