Diskret matematik - 11


11. kursusgang , tirsdag den 24. marts 8.15-12.00


Forelæsning i Auditorium 2, 8.15 - 8.40:

Mere om NP-komplette problemer, farvning, planaritet og travelling salesman problem.
Slides

Opgaveregning 8.40 - 10.40:

Opgave i afsnit 9.6:  26, 29, 30
Opgave i afsnit 9.8:  8, 18, 28, 31

Opgave A:  Lad G være en graf.
Lad G*  være den graf der fås fra G ved at tilføje et nyt punkt og tilføje kanter fra det nye punkt til alle punkter i G.
Vis at  G har en farvning med k farver hvis og kun hvis G*  har en farvning med  k+1  farver.

Opgave B:
  Hvilke af følgende påstande er sande (for et fast tal k):

Opgave i afsnit 9.7:  2, 3, 4, 13, 15


Forelæsning i Auditorium 2, 10.40 - 12.00:

Afsnit 10.1: Introduktion til træer.
Afsnit 10.2: Anvendelse af træer, bl.a. Huffman koder.