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

Labelling Algorithm (Interactive)

The labelling algorithm is a systematic BFS procedure that finds augmenting paths. It grows an alternating tree from every exposed node in X until it either reaches an exposed node in Y (→ augment) or exhausts all reachable nodes (→ M is maximum).

Label convention: - Every exposed \(x \in X\) gets label \(\langle * \rangle\) (root of tree). - When we reach an unlabelled \(y \in Y\) via a non-\(M\) edge from \(x\): label \(y\) with \(\langle x \rangle\). - If \(y\) is matched to \(x'\): label \(x'\) with \(\langle y \rangle\) and enqueue \(x'\). - If \(y\) is exposed: augmenting path found — reconstruct via labels.

🔍 Labelling Algorithm — Step-by-Step

Init

Use Next → to step through the algorithm.

```yzkde //| echo: false viewof matchingStepSlider = Inputs.range([0, 4], {value: 0, step: 1, label: "Step:"})

<!-- Left: graph SVG -->
<div class="la-panel" id="la-panel-graph">
  <div class="la-panel-title">Bipartite graph G</div>
  <svg id="la-svg" width="100%" viewBox="0 0 400 300"
       style="display:block; overflow:visible;"></svg>
</div>
<!-- Right: algorithm state -->
<div class="la-panel" id="la-panel-state">
  <div class="la-panel-title">Algorithm state</div>
  <div id="la-state-panel">
    <div id="la-queue-row">Queue Q: <strong>—</strong></div>
    <table id="la-label-table">
      <thead><tr><th>Node</th><th>Label</th><th>Status</th></tr></thead>
      <tbody id="la-label-tbody"></tbody>
    </table>
  </div>
</div>

<button id="la-btn-prev" disabled>← Prev</button>
<button id="la-btn-next">Next →</button>
<button id="la-btn-reset" disabled>↺ Reset</button>

{
  if (window.goToMatchingStep) {
    window.goToMatchingStep(matchingStepSlider);
  }
}


## 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 |


::: {.cell}

```{.pyodide .cell-code}
FINAL_MATCHING = [('x1','y1'), ('x2','y2'), ('x3','y3'), ('x4','y4')]

fig, axes = plt.subplots(1, 2, figsize=(10, 4.5))

# Left: before augmentation
draw_bipartite(axes[0], ALL_EDGES,
               matching=INITIAL_MATCHING,
               exposed=['x4', 'y3'],
               title='Before: M = {x1-y1, x2-y2, x3-y4}\n|M| = 3')

# Right: after augmentation
draw_bipartite(axes[1], ALL_EDGES,
               matching=FINAL_MATCHING,
               title="After: M' = {x1-y1, x2-y2, x3-y3, x4-y4}\n|M'| = 4  (perfect matching!)")

leg = [
    mpatches.Patch(color='#cccccc', label='Non-matching edge'),
    mpatches.Patch(color='#2980b9', label='Matching edge'),
]
for ax in axes:
    ax.legend(handles=leg, loc='lower center', fontsize=7.5,
              bbox_to_anchor=(0.5, -0.05), ncol=2, frameon=True)

plt.suptitle('Symmetric difference M ⊕ P augments the matching by 1',
             fontsize=11, fontweight='bold', y=1.02)
plt.tight_layout()
plt.show()

:::

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.