We disucssed Trees, Minimal Spanning Trees and Graph colourings.

  • We did not discuss everything in the seciton 3.4 in the lectures notes on graph colouring. I suggest you read the extra material on your own and ask questions if you find something you do not understand. The was an error in ex 3.21 that is now fixed. 

There was not enough time to disucss the proof of Prim's greedy algorithm.

Here are two different proofs. Although both rely on the same essential idea.

  1. Form the reocmmnded book https://aimath.org/textbooks/approved-textbooks/bender-williamson-dm/  Direct link: Page 38 of https://cseweb.ucsd.edu//~gill/BWLectSite/Resources/C2U4GT.pdf

  2. From some lectures notes By Prof Stephen Tate and UNC. https://home.uncg.edu/cmp/faculty/srtate/330.f16/primsproof.pdf

Last modified: Thursday, 30 March 2023, 4:16 PM