最小カットのカットは「辺を切る」ではない

グラフの「カット」を文字通り「辺を切ること」と捉えていると、最小カット問題の文脈では混乱の元である。

グラフのカットの定義: カット (グラフ理論) - Wikipedia

グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。 定義に忠実に「頂点を白黒の二色に塗り分ける」と捉える方が良い。

最小カット問題とは辺$(u,v)\in E$ のうち、$u\in S,v\in T$ であるような辺のコストの和が最小になるようなカット $(S,T)$ を見つける問題。言い換えれば「白黒辺のコストが最小になるように頂点を白黒に塗り分ける」問題。

かならず守って欲しい制約をコストが十分大きな辺(以下、無限大辺と呼ぶ)で表現することが多い。たとえばProject Selection Problem 「無限大辺は切ってはいけない」と解釈していると中央部分が全部ひとつながりになりそうに思って混乱する。そうではなく頂点を塗り分ける。 ここまでの説明では白黒と書いたが、図では赤白になってる。赤白辺のコストを足し合わせたものを最小化する。 1つ目の例ではプロジェクト1を選んでいるのに必要なマシン2を買ってないので無限大辺のコストが足されている。 2つ目の例ではプロジェクト1だけが選択されている。プロジェクト2は必要なマシンが買われているのに選択されてないので損をしている。 3つ目の例ではプロジェクト2も選択されている。

無限大コストの有向辺は「切ってはいけない」ではなく「赤白に塗ってはいけない、白赤ならあり」になる。 両方向に辺を張ることで「白赤も赤白もダメ」になる。これだと「切ったらダメ」って解釈ができるが、一般的には双方向に辺があるとは限らない。

メモ

• 2番目の例がフローとして考えると意味不明だが、それはフローとして考えるのがおかしい
  • そもそも最小カットとは、カットのうち、最小であるものを見つける問題
  • この「カット」がすべてフローと対応づくわけではない、最小カットが最大フローと対応づくだけ

カット=頂点の二色塗り分け