.png)
弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．
Spir | Smart scheduling calendar
この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．
詳しくは231121_最大流・最小カット定理 を参照。
始点 $S$ と終点 $T$ を持つ、辺に重みのついた有向グラフ $G$ についての概念。 この資料では辺重みが非負整数の連結グラフを仮定。
前回の資料の図なので $S,T$ が小文字
辺の重みをその辺の「容量」として、始点 $S$ から終点 $T$ に水を流す操作をフローと呼ぶ。
$S$ から $T$ に流れる水の量を最大化したものが最大流（最大フロー）。
青文字が流量11のフロー
各頂点を $S$ グループ と $T$ グループ の2グループに分ける操作をカットと呼ぶ。
この時に $S$ グループの頂点 から $T$ グループの頂点 への辺重みの総和がカットのコスト。 コストを最小化したグループ分けが最小カット。
赤がS，青がT，重み11のカット
任意のグラフについて**（最大流の流量） $\leq$ （最小カットのコスト）**が成り立つ．
カットを任意に一つとり、高々そのカットのコスト分しか水を流せないことを示せば良い。