Graph Theory37 sections · 1633 units
Open in Course

Quiz: Max-Flow Min-Cut Theorem

Knowledge check

Check Your Understanding

You compute max flow and get value 1515. You find the min-cut by running BFS on the residual graph from ss. Which edges form the min-cut?

  1. A.All edges from ss to its neighbors
  2. B.All edges where both endpoints are reachable from ss in the residual graph
  3. C.All original-graph edges from BFS-reachable nodes to non-reachable nodes
  4. D.All edges with zero residual capacity
Start the roadmap to answer the quizzes and solve the challenges