Bipartite matching

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.

Exercise 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'])).

Show example 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']))

Test yourself

matching definition

match = ____
# match[v] = u

Show answer

match = {}
# match[v] = u

Bipartite matching concepts

U set

Left side
V set

Right side
matching

One-to-one edges
maximum

Largest matching
Maximum matching equals?
```
if augment(u, set()):
    result += 1
```
- The shortest path
- Number of augmenting paths found
- Size of U set
- Total edge count
Show answer

Number of augmenting paths found — Each augmenting path adds one matching.

Next lesson: Summary - Network flow

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies