Topic summary · Decision maths (D1)
Matchings summary
Bipartite matching pairs two sets such as people and tasks. Alternating paths improve incomplete matchings.
Files: D1-Matchings.pdf · D1-Matchings answers.pdf · free public downloads · diagrams in the PDFs
Key learning points
- Draw the bipartite graph with the two parts clearly separated.
- Distinguish maximal from maximum matchings.
- Augmenting paths flip edges to increase matching size by one.
- State the final matching explicitly.
Worked example 1 — Augmenting path
What does an augmenting path achieve?
Working
Flip matched and unmatched edges along the path.
Worked example 2 — Draw the bipartite graph with the two parts clearly
Use this method from the Matchings sheet: Draw the bipartite graph with the two parts clearly separated.
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 3 — Distinguish maximal from maximum matchings
Use this method from the Matchings sheet: Distinguish maximal from maximum matchings.
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 4 — Augmenting paths flip edges to increase matching size
Use this method from the Matchings sheet: Augmenting paths flip edges to increase matching size by one.
Working
Each key learning point matches a question type on the printable worksheet.
Worked example 5 — State the final matching explicitly
Use this method from the Matchings sheet: State the final matching explicitly.
Working
Each key learning point matches a question type on the printable worksheet.
Scaffolded Learning Sheet and answers (PDFs)
This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.