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

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

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

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