Matching Ladder¶
This ladder should make bipartite matching feel like a natural modeling tool and help you separate it cleanly from flow, weighted assignment, and general matching.
Who This Is For¶
Use this ladder if:
- pairing problems still feel story-specific instead of graph-structured
- you know augmenting paths, but not yet the modeling cues
- you are unsure when the graph is bipartite and when blossom-level machinery appears
Warm-Up¶
- bipartite matching basics
- augmenting path intuition
Target skill:
- identify the two sides of the bipartite graph clearly
Core¶
- School Dance
- maximum bipartite matching
- matching as a reduction target
Target skill:
- turn assignment and compatibility statements into clean matching graphs
Stretch¶
- Edmonds Blossom / General Matching
- QBFLOWER
- compare matching reductions with flow reductions
- understand where edge-cover relationships appear
Target skill:
- distinguish bipartite matching, flow, and general matching on structure rather than terminology
Retrieval Layer¶
- bipartite maximum matching -> hopcroft-karp.cpp
- flagship in-lane rep -> School Dance
- weighted sibling lane -> Task Assignment
- non-bipartite sibling lane -> General Matching
- when the cleaner model is actually capacity flow -> dinic.cpp
- quick reminder sheet -> Matching hot sheet
Repo Anchors And Compare Points¶
- boundary note, not the core bipartite rep -> QBFLOWER
- dedicated non-bipartite sibling -> Edmonds Blossom / General Matching
- compare against flow modeling -> Police Chase
- compare the teaching pages -> Matching and Maximum Flow
- reopen the broader graph routing layer -> Matching ladder hub and Graphs ladder
The strongest in-repo loop here is:
- learn the bipartite-first modeling cues from the Matching topic
- solve or revisit School Dance as the clean in-lane
Hopcroft-Karprep - compare against General Matching once the graph stops being bipartite
- solve or revisit QBFLOWER only to see the transformation boundary where blossom-level structure appears
Exit Criteria¶
You are ready to move on when:
- you check bipartiteness before reaching for stronger machinery
- augmenting paths feel intuitive rather than memorized
- you can explain why a pairing problem is really matching and not just generic flow