カット

定義 4.2（「連結度とネットワークフロー」§4）

$s\in S$ 、 $t\notin S$ である頂点集合 $S\subseteq V$ を $s$ – $t$ カットといい、

c(S)=\sum_{(u,v)\in E,\ u\in S,\ v\notin S}c(u,v)

をその容量という。容量が最小のカットを最小カットという。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

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

証明で明示的に参照している定理は、まだありません。