MS-A0402 - Foundations of Discrete Mathematics, Lecture, 27.2.2023-21.4.2023
Kurssiasetusten perusteella kurssi on päättynyt 21.04.2023 Etsi kursseja: MS-A0402
Lecture 10
Suorituksen vaatimukset
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.
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
- From some lectures notes By Prof Stephen Tate and UNC. https://home.uncg.edu/cmp/faculty/srtate/330.f16/primsproof.pdf
Viimeksi muutettu: torstaina 30. maaliskuuta 2023, 16.16