Diskret matematik - 19


Fredag den 1. april 

Forelæsning, 8.15 - 8.40:

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):
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