Bipartite Matching

Two applicants can both accept the same job, but assigning that job twice is not a matching. A bipartite graph separates the two kinds of objects into left and right sets. An edge means compatibility, and a matching selects edges that never share a vertex. The objective here is to make as many pairs as possible. Sometimes this requires moving an earlier assignment, rather than leaving every previous decision fixed.

Reproduce the exchange, then remove an option

Open the Bipartite Matching explorer. These steps use its actual controls. The upper result bar distinguishes the matching currently committed in the replay from the already computed maximum size.

1. Choose Greedy trap in Preset. Left count and Right count are both 2, and Edges contains the three pairs from the worked example. Current is 0; Maximum is 2.
2. Move Replay step to 1. The candidate path is L0 → R0, but Current remains 0. Press Next step to commit that pair at step 2.
3. Press Next step again. At step 3, follow the amber additions and dashed red removal along L1 → R0 → L0 → R1. The path panel shows three edges, two additions and one removal; Current is still 1.
4. Advance to step 4 to commit the exchange. Then press Show maximum to reach step 5. The two pairs are L0–R1 and L1–R0, both free counts are zero, and Perfect is Yes.
5. Choose R0 in Inspect vertex, or click its node. Its partner is L1. Drag the graph background or use its arrow keys to pan; Home or Reset view restores only the view.
6. Replace Edges with two lines, 0 0 and 1 0. The edited experiment restarts at step 0 and clears inspection. Maximum is now 1, because both left vertices compete for the only usable right vertex. Show maximum to inspect the chosen pair.
7. Choose Rectangular. At its maximum, both left vertices are paired, but one of the three right vertices is free. Perfect is No.
8. Enter 7 in Left count. An error replaces the previous results and drawing. Press Reset experiment to recover the default graph, initial replay, inspection and view.