In question 2, I wanted to ask about the maximum number of different values for minimum s-t cuts.
(In other words, if you can find an example with more than n-1 different mincut values, then you'll know that a flow tree cannot exist for such a graph.)
Actually, even without the missing word, the question makes sense. It's just that the number could conceivably be much higher because each subset of vertices might define a cut of different capacity.
Answering this second variant will result in at least some credit.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment