optional · interactive figures
15
Explore: matching
König's cover grown from a matching, the Hungarian method's potentials shifting, and Gale–Shapley's proposals, each replayed from the reference solution.
optional: nothing in the lab depends on it back to the slides
These figures support the slides; they don't replace them, and the unit is complete
without them. Each one is computed from the unit's own data or reference solution, so
what you see agrees with the numbers on the slides.
Inside a figure, the arrow keys and drags belong to the figure; click outside it (or
press Esc) to use them for the slides again.
15 · explore
König's cover, built from a matching
Try: step from the free left vertex along alternating paths; the last step turns what was reached into a cover. Static version: König's cover, on a small graph .
What it shows. The slide's bipartite graph with the maximum matching the reference
hopcroft_karp finds, $\{\ell_0 r_0, \ell_2 r_1\}$. The search starts at the free left
vertex and follows alternating paths: an unmatched edge to the right, the matched edge back.
The cover is the left vertices not reached plus the right vertices reached, and it has
the matching's size, so each proves the other optimal.
A logged copy of the reference konig_cover, checked against it.
15 · explore
The Hungarian method, potential by potential
Try: step and watch zeros appear as the potentials shift; the assigned cells are always zeros. Static version: the Hungarian method, on a 3×3 matrix .
What it shows. The slide's cost matrix. Each cell shows its reduced cost
$c_{ij} - u_i - v_j$ (large) and its cost (small). Rows are added one at a time; the search
tree's rows and columns are highlighted, and each shift adds $\delta$ to the tree rows' $u$ and
subtracts it from the tree columns' $v$, which keeps every reduced cost $\ge 0$ and creates a new
zero. When a zero reaches a free column, the assignment grows along the tight path.
At the end the assigned cells are all zero and every other cell is $\ge 0$: the potentials are
a dual certificate, and $\sum u + \sum v = 5$ = the cost. The run is a logged copy of the
reference hungarian, checked against its assignment and potentials.
15 · explore
Gale–Shapley, proposal by proposal
Try: follow C down its list while X and Y trade up. Static version: Gale–Shapley, round by round .
What it shows. The slide's preferences. Each step is one proposal: accepted by a free
receiver, accepted with the previous partner dropped, or rejected. Proposers only move down
their lists (brackets mark choices used up) and receivers only trade up, which is why it ends,
and why the result has no blocking pair.
A logged copy of the reference gale_shapley; its matching is checked against the
reference and by is_stable.