Matching
Interactive visualizations for Chapter 12 of the Ricerca Operativa notes
The Bipartite Graph
We work with a bipartite graph G = (X ∪ Y, E) throughout this chapter.
- Left partition X: x1, x2, x3, x4
- Right partition Y: y1, y2, y3, y4
- Edges: x1-y1, x1-y2, x2-y1, x2-y2, x2-y3, x3-y3, x3-y4, x4-y3, x4-y4
- Initial matching M: {x1-y1, x2-y2, x3-y4} (size 3)
- Exposed nodes: x4 (left), y3 (right)
Matching Definitions
A matching M in a graph G is a set of edges with no shared endpoints.
- A node is matched if it is an endpoint of some edge in M; otherwise it is exposed (or free).
- A matching is maximum if no other matching has more edges.
- A matching is perfect if every node is matched.
The initial matching M = {x1-y1, x2-y2, x3-y4} has size 3. Nodes x4 and y3 are exposed (dashed red border).
Finding an Augmenting Path
An augmenting path is a path that:
- starts and ends at exposed nodes,
- alternates between non-matching and matching edges.
Augmenting M along P gives a matching of size |M| + 1 (by taking the symmetric difference M ⊕ P).
We find the path x4 → y4 → x3 → y3 by alternating search from the exposed node x4.
Step 1 — Start at x4, follow non-matching arc x4→y4
x4 is exposed. The edge x4-y4 is not in M, so we follow it first.
Step 2 — y4 is matched to x3, follow matching arc y4→x3
y4 is matched (to x3 via edge x3-y4 ∈ M). We must follow this matching edge backward to x3.
Step 3 — x3 can reach exposed y3 via non-matching arc x3→y3
x3 is now in the path. The edge x3-y3 is not in M, and y3 is exposed. Augmenting path found!
Augmenting path P: x4 - y4 - x3 - y3
Augmenting: Symmetric Difference
Given augmenting path P, the new matching is:
M’ = M ⊕ P = (M P) ∪ (P M)
That is: remove matching edges on P, add non-matching edges on P.
| Edges | |
|---|---|
| M (before) | {x1-y1, x2-y2, x3-y4} — size 3 |
| Path P | x4-y4 (add), x3-y4 (remove), x3-y3 (add) |
| M’ (after) | {x1-y1, x2-y2, x3-y3, x4-y4} — size 4 |
The Maximum Matching is Perfect
The final matching M’ = {x1-y1, x2-y2, x3-y3, x4-y4} is perfect: every node in X and Y is matched. Since |M’| = 4 = |X| = |Y|, no larger matching is possible.
Reduction to Max Flow
Maximum bipartite matching can be solved as a max-flow problem:
- Add a source s with an arc of capacity 1 to each node in X.
- Add a sink t with an arc of capacity 1 from each node in Y.
- Each original edge (x,y) becomes a directed arc x→y of capacity 1.
The max flow from s to t equals the maximum matching size.
For our graph the max flow is 4, corresponding to the perfect matching.
König’s Theorem
König’s theorem (for bipartite graphs):
In any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover.
A vertex cover is a set of nodes C such that every edge has at least one endpoint in C.
For our graph:
- Maximum matching size = 4 (perfect matching M’)
- Minimum vertex cover = 4 nodes
Since the matching is perfect, taking all nodes on either side (e.g. C = {x1,x2,x3,x4}) gives a vertex cover of size 4. Every edge x-y has its left endpoint in C, so all edges are covered. No smaller cover exists (we need at least 4 nodes to cover 4 disjoint matching edges).
Every edge has its left endpoint in C = {x1,x2,x3,x4}, confirming that C is a valid vertex cover. Since |C| = 4 = |M’|, König’s theorem is verified: minimum vertex cover = maximum matching = 4.