Lidt mere om
Afsnit 10.4 og P versus NP.
NP1 NP2 NP3
Afsnit 10.2: Binære søgetræer. Optimal kompleksitet af
sorteringsalgoritme. Huffman koder.
Huffman
Desuden starter vi på:
Afsnit 10.5: Minimum vægt udspændende træer. Prims algoritme.
Opgaveregning 14.15 - 16.15:
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 k-farvning hvis og kun hvis G
*
har en (k+1)-farvning.
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 k-farvning,
så findes der en polynomiel tids algoritme, der afgør om
en graf har en (k+1)-farvning.
- Hvis der findes en polynomiel tids algoritme, der afgør om
en graf har en (k+1)-farvning,
så findes der en polynomiel tids algoritme, der afgør om
en graf har en k-farvning.
Opgaver i afsnit 10.4: 1, 11, 12, 13, 14, 16, 30, 31.
Opgaver i afsnit 10.2: 5, 7.
