最小カットのカットは「辺を切る」ではない
グラフの「カット」を文字通り「辺を切ること」と捉えていると、最小カット問題の文脈では混乱の元である。
グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。
定義に忠実に「頂点を白黒の二色に塗り分ける」と捉える方が良い。
最小カット問題とは辺$ (u, v) \in E のうち、$ u \in S, v \in T であるような辺のコストの和が最小になるようなカット $ (S, T) を見つける問題。言い換えれば「白黒辺のコストが最小になるように頂点を白黒に塗り分ける」問題。 https://gyazo.com/b9559c8d3676a4a89942a16838a27ce1
「無限大辺は切ってはいけない」と解釈していると中央部分が全部ひとつながりになりそうに思って混乱する。そうではなく頂点を塗り分ける。
ここまでの説明では白黒と書いたが、図では赤白になってる。赤白辺のコストを足し合わせたものを最小化する。
1つ目の例ではプロジェクト1を選んでいるのに必要なマシン2を買ってないので無限大辺のコストが足されている。
2つ目の例ではプロジェクト1だけが選択されている。プロジェクト2は必要なマシンが買われているのに選択されてないので損をしている。
3つ目の例ではプロジェクト2も選択されている。
https://gyazo.com/a18e0dc6651304be872867f61f41f49d
無限大コストの有向辺は「切ってはいけない」ではなく「赤白に塗ってはいけない、白赤ならあり」になる。
両方向に辺を張ることで「白赤も赤白もダメ」になる。これだと「切ったらダメ」って解釈ができるが、一般的には双方向に辺があるとは限らない。
メモ
2番目の例がフローとして考えると意味不明だが、それはフローとして考えるのがおかしい
そもそも最小カットとは、カットのうち、最小であるものを見つける問題
この「カット」がすべてフローと対応づくわけではない、最小カットが最大フローと対応づくだけ