カット=頂点の二色塗り分け
カットは頂点の二色塗り分けだと考えると混乱しにくい
このグラフの最小カットはいくらでしょう、という話が「カット=辺を切る」だと思ってると混乱しやすくて「カット=二色での塗り分け」だと思ってるとわかりやすい例なのではないか https://gyazo.com/be67d70231072dff13c8ee7267bf6c4d
答えは3
二色塗り分けで理解してると「赤青二色で塗って、赤青辺のコストを足したもの」
辺の切断で説明しようとすると中央の2本の辺の片方だけを切ることになる
ここで混乱する人が多そう
https://gyazo.com/648dac96e5753856bd3b201b169aae08
もう一つ例を思いついたんだけど「1番のグラフのカットは何種類あるでしょう」に対して3種類と答えちゃう人が「カットは辺を切ること」だと思ってる人にはいそう。
「カットは頂点の二色塗り分け」と考えていれば間違えずに4種類と答えられる。
(追記: 少し言葉足らずだった。SとTの色は固定されているものとします)
https://gyazo.com/ed8d12765dc74176e93e7e2f9519f829
3種類ではなく4種類なのは(2)の例もカットだからである。
(2)のケースがカットに含まれることを理解してないと(3)で消す必要性がわからない。
カットとフローを混同してる人は(2)をみてどんなフローか想像しようとして混乱するが、カットがすべてフローに対応するわけではない。最小カットが最大フローに対応するだけ。
カットのことを考えてる時にフローのことを考えるのは混乱の元。