General Matching¶

Maximum-cardinality matching in a general undirected graph via Edmonds blossom shrinking, with odd-cycle contraction preserving augmenting-path search.

Topic slug: graphs/general-matching
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 3

Microtopics¶

general-graph-matching
augmenting-paths
alternating-forest
blossom-shrinking
base-array
odd-cycle-contraction

Learning Sources¶

Source	Type
OI Wiki general graph maximum matching	`Reference`
KACTL PDF	`Reference`
Edmonds blossom lecture notes	`Reference`

Practice Sources¶

Source	Type
Library Checker Matching on General Graph	`Practice`
Luogu P6113	`Practice`
VN SPOJ QBFLOWER	`Practice`

Repo Companion Material¶

Material	Type
General Matching hot sheet	`quick reference`
General Matching starter route	`starter route`
General Matching note	`anchor note`
Matching tutorial	`compare point`
QBFLOWER note	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Matching on General Graph	`Library Checker`	`Hard`	Blossom	Template Problem; Non-Bipartite Matching	Augmenting Paths; Alternating Forest; Matching Basics	Edmonds Blossom; Odd Cycle; Maximum Matching	The cleanest direct benchmark where the graph is explicitly general and the whole task is just blossom-based maximum matching.

Practice¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
P6113 [Template] General Graph Maximum Matching	`Luogu`	`Hard`	Blossom	Template Drill; Non-Bipartite Matching	Augmenting Paths; Odd Cycle Contraction	Template; Maximum Matching	A straightforward second template benchmark once the Library Checker route feels stable.

Bridge¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
QBFLOWER - Tặng hoa	`VN SPOJ`	`Medium`	Edge Cover	Modeling; Transformation	Maximum Matching; Edge Cover Formula	Minimum Edge Cover; Graph Transformation	A strong bridge problem where blossom is still the engine, but only after reducing the story to minimum edge cover on a general graph.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`GENERALMATCHING`	Matching on General Graph	`primary`	`hard`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py