MTH6105 Algorithmic Graph Theory

Week 2: Maximal Subtrees and Connectivity

  Covered this week:
Lecture 1:
The Maximal_Subtree algorithm and applications. Notes PDF file icon (not quite what we covered in the lecture—I decided to put all the definitions in one place, Maximal_Subtree now appears in L2 notes).
Lecture 2:
Some lemmas giving ... proof of correctness of Maximal_Subtree algorithm. Notes PDF file iconupdated 24.01.12 (again diverging from the lecture---they cover the maximum vs maximal distinction and specify Maximal_Subtree, with an example)
Lecture 3:
Complexity analysis of Maximal_Subtree algorithm. Notes PDF file icon (complexity + correctness in this set)

Week 2 Coursework: watch the boxes below!
Coursework 2
Solutions
Download pdf
Submit: 25.01
Download pdf

Extra: try out this MWST applet!

Week 1 Week 3 Back to MTH6105 main page School of Maths Sciences