Lidt mere om kardinalitet og kompleksitet.
Slides
Opgaveregning 8.40-10.40
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 C:
Hilberts hotel har uendeligt mange værelser. Alligevel er alt optaget
da der pludseligt ankommer en bus med (tælleligt) uendeligt mange
turister, der hver gerne vil have et værelse. Med udsigt til uendelig
stor fortjeneste ønsker hotellet ikke at afvise turisterne. Hvad kan
hotellet gøre?
Opgaver i afsnit 2.4: 31, 33, 40, 48, 45, 46, 47
Opgaver i afsnit 1.2: 60
Opgaver i afsnit 5.1: 1
Forelæsning, 10.40 - 12.00:
Afsnit 5.2: skuffeprincippet
Afsnit 5.3: permutation og kombination
Afsnit 5.4: binomialformel