MTH6105 Algorithmic Graph Theory

Week 3: Minium-Weight Spanning Trees

  Covered this week:
Lecture 1:
Minimum-Weight Spanning Tree (MWST) algorithm and its correctness and complexity. Notes PDF file iconupdated 24.01.12 to include the correctness proof of MWST.
Lecture 2:
Prim's algorithm, with an example. Notes PDF file icon (updated 25.01.12 to correct a couple of errors in the algorithm pseudocode; updated 01.02.12 to correct the labelling on the first graph on page 2.)
Lecture 3:
Forests. Kruskal's algorithm with example and discussion of correctness and complexity. NOTES: we hardly got on to this topic, so it is carried over to Week 4 and the notes will appear then. In the meantime you can look ahead using the links on the right...

Week 3 Coursework: watch the boxes below!
Coursework 3
Solutions
Download pdf
Submit: 01.02.12
Download pdf
Amended 15.04.12

Extra: something here soon!

Week 2 Week 4 Back to MTH6105 main page School of Maths Sciences