Graph Theory37 sections · 1633 units
Open in Course

Quiz: Max-Flow Min-Cut Relationship

Knowledge check

Check Your Understanding

You compute max flow on a network and get value 1212. You find an ss-tt cut with 33 edges of capacities 55, 44, and 33. What can you conclude?

  1. A.The cut is not minimal because 5+4+3=125 + 4 + 3 = 12 is coincidental
  2. B.This confirms the max-flow min-cut theorem: the cut capacity equals the max flow
  3. C.The max flow should be 33 because that is the bottleneck edge
  4. D.You must check all other cuts before concluding anything
Start the roadmap to answer the quizzes and solve the challenges