MTH6105 Algorithmic Graph Theory

Week 8: Maximum Matchings 1

  Covered this week:
Lecture 1:
Matchings in graphs. Bipartite graphs. Notes PDF file icon
Lecture 2:
Covers in graphs. Relationship between covers and matchings. Notes PDF file icon
Lecture 3:
Recognising bipartite graphs. Extending a matching using an M-augmenting path. Notes PDF file icon

Week 8 Coursework: watch the boxes below!
Coursework 7
Solutions
Download pdf
Submit: 07.03
Download pdf

Extra: beyond our coverage: non-bipartite matching . And of course theoremoftheday has something to chip in: Bregman's Theorem

Week 7 Week 9 Back to MTH6105 main page School of Maths Sciences