Bipartite matching
- Algorithms course
- Expert
- Lesson 29/41
- 4 min
Maximum matching in a bipartite graph.
Bipartite matching
A bipartite graph has its nodes split into U and V, with edges only from U to V. A matching is a set of edges where each node appears at most once.
A maximum matching is the largest such set. Many real problems fit this model: jobs and applicants, courses and students.
Bipartite maximum matching reduces to a flow network: add edges from source to U, U to V, and V to sink.
Augmenting path method
Bipartite maximum matching is found with the augmenting path method. An augmenting path starts at an unmatched U node, ends at an unmatched V node, and alternates between unmatched and matched edges.
Each augmenting path increases the matching by one. When no augmenting path remains, the matching is maximum.
This method is the bipartite special case of Ford-Fulkerson.
Practice bipartite_matching function
Write bipartite_matching(graph, left). graph maps U nodes to V lists; left is the U nodes. Return the maximum matching count. Print 3 with print(bipartite_matching({'a': [1, 2], 'b': [1], 'c': [2, 3]}, ['a', 'b', 'c'])).
Starter code
def bipartite_matching(graph, left):
# Bipartite maximum matchingSample solution
def bipartite_matching(graph, left):
# Bipartite maximum matching
match = {}
def augment(u, visited):
for v in graph[u]:
if v not in visited:
visited.add(v)
if v not in match or augment(match[v], visited):
match[v] = u
return True
return False
result = 0
for u in left:
if augment(u, set()):
result += 1
return result
print(bipartite_matching({'a': [1, 2], 'b': [1], 'c': [2, 3]}, ['a', 'b', 'c']))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 matching definition
match = ____
# match[v] = umatch = {}
# match[v] = uExplanation: match is initialized as a dict.
2 Bipartite matching concepts
| Term | Meaning |
|---|---|
U set |
Left side |
V set |
Right side |
matching |
One-to-one edges |
maximum |
Largest matching |
3 Maximum matching equals?
if augment(u, set()):
result += 1- The shortest path
- Number of augmenting paths found Correct answer
- Size of U set
- Total edge count
Explanation: Each augmenting path adds one matching.