Graph Theory37 sections · 1633 units
Open in Course

Quiz: Augmenting Paths in Matching

Knowledge check

Check Your Understanding

An augmenting path in bipartite matching alternates between unmatched and matched edges. What happens when you flip all edges along this path?

  1. A.The matching size decreases by 11
  2. B.The matching size stays the same
  3. C.The matching size increases by 11
  4. D.The matching becomes a perfect matching
Start the roadmap to answer the quizzes and solve the challenges