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):
- Hvis der findes en polynomiel tids algoritme, der afgør om
en graf har en farvning med k farver
så findes der en polynomiel tids algoritme, der afgør om
en graf har en farvning med k+1 farver.
- Hvis der findes en polynomiel tids algoritme, der afgør om
en graf har en farvning med k+1 farver
så findes der en polynomiel tids algoritme, der afgør om
en graf har en farvning med k farver.
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.