カットは頂点の二色塗り分けだと考えると混乱しにくい

このグラフの最小カットはいくらでしょう、という話が「カット=辺を切る」だと思ってると混乱しやすくて「カット=二色での塗り分け」だと思ってるとわかりやすい例なのではないか

答えは3

二色塗り分けで理解してると「赤青二色で塗って、赤青辺のコストを足したもの」

辺の切断で説明しようとすると中央の2本の辺の片方だけを切ることになる

ここで混乱する人が多そう

もう一つ例を思いついたんだけど「1番のグラフのカットは何種類あるでしょう」に対して3種類と答えちゃう人が「カットは辺を切ること」だと思ってる人にはいそう。

「カットは頂点の二色塗り分け」と考えていれば間違えずに4種類と答えられる。

(追記: 少し言葉足らずだった。SとTの色は固定されているものとします)

3種類ではなく4種類なのは(2)の例もカットだからである。

3択にしたい時はこの可能性を消すために(3)の赤の辺を追加する。 最小カットで3以上の選択肢

(2)のケースがカットに含まれることを理解してないと(3)で消す必要性がわからない。

カットとフローを混同してる人は(2)をみてどんなフローか想像しようとして混乱するが、カットがすべてフローに対応するわけではない。最小カットが最大フローに対応するだけ。

カットのことを考えてる時にフローのことを考えるのは混乱の元。

from Twitter

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