Mere om repræsentation af grafer, og datastrukturens betydning for algoritmers kompleksitet.
Dijkstras algoritme.
Slides
Opgaveregning 8.40-10.40:
Opgave i afsnit 9.6: 1, 3, 15, 18, 24
Opgave i afsnit 9.4: 6, 15
Opgave i afsnit 9.3: 2, 6, 35, 36
Opgave i afsnit 9.2: 23, 25
Opgave i afsnit 9.6: 21, 22, 23
Forelæsning i Auditorium 1, 10.40 - 12.00:
Afsnit 9.6:
The Travelling Salesman Problem (Et NP-komplet problem.)
Afsnit 9.7:
Kort gennemgang af planare grafer.
Afsnit 9.8:
Lidt om farvning af grafer. (Et NP-komplet problem.)