It’s less confusing to think of the cut as a two-color paint job at the apex.
- I think this is an example of how confusing it is if you think “cut = cutting an edge” and how easy it is to understand if you think “cut = painting with two colors”.
- The answer is 3
- As I understand it with the two-color paint scheme, it’s “painted in two colors, red and blue, and the cost of the red and blue sides added together.”
- If you try to explain it by cutting the edges, you’d only be cutting one of the two central edges.
- A lot of people seem to get confused here.
- I just thought of another example, but I think there are people who would answer “How many types of cuts are there in the first graph?” with 3 types, if they think that cutting is cutting an edge.
- If you think “cuts are two-color painted at the apex,” you can answer “four types” without making a mistake.
- (PS: I was a little short on words; assume the S and T colors are fixed)
- The reason there are four types instead of three is that the example in (2) is also a cut.
- If you want to have three options, add the red edge of (3) to eliminate this possibility. 3 or more options with minimum cuts.
- If you don’t understand that case (2) is included in the cut, you don’t understand the need to eliminate it with (3).
- People who confuse cut with flow are confused when they look at (2) and try to imagine what kind of flow it is, but not all cuts correspond to flow. The minimum cut only corresponds to the maximum flow.
- Thinking about flow when you’re thinking about cuts is confusing.
- If you think “cuts are two-color painted at the apex,” you can answer “four types” without making a mistake.
from Twitter from Cutting the smallest cut is not “cutting an edge”.
This page is auto-translated from /nishio/カット=頂点の二色塗り分け using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.