Mere om P og NP, og om træer.
Slides
Opgaveregning 8.40-10.40
Opgaver i afsnit 9.8: 7, 8
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.
Opgaver i afsnit 10.1: 1, 3, 45, 46
Opgaver i afsnit 10.4: 1, 3
Forelæsning i Auditorium 3, 10.40 - 11.20:
Afsnit 10.4: Lidt om træer og backtracking.
Afsnit 10.5:
Minimum vægt udspændende træ.