Diskreetti matematiikka / kevät 2012

Harjoitus 5

1. Piirrä kaikki keskenään ei-isomorfiset 6-solmuiset puut. Montako 7-solmuista

keskenään ei-isomorfista puuta on olemassa?

2. Osoita, että asunnossa, jossa on vain yksi ulko-ovi, on jossakin huoneessa

pariton määrä ovia.

3. Mallinna seuraava tehtävä verkkoteoreettisesti ja ratkaise se. On annettu 8, 5 ja 3 litran vetoiset vesiruukut, joista 8-litrainen on täynnä vettä ja kaksi muuta tyhjiä. Onko mahdollista jakaa vesi tasan kahteen 4 litran annokseen, kun ainoa sallittu mittausoperaatio on kaataa vettä ruukusta A ruukkuun B niin, että joko A tyhjenee tai B täyttyy (läikkymättä)? (Vihje: Valitse verkon solmuiksi ruukkukolmikon “vesitilavektorit”)

4. Sir William Hamilton totesi v. 1856, että jokainen avaruuden säännöllisen monitahokkaan kärkien ja sivujen muodostama verkko sisältää Hamiltonin kierroksen. Vahvista tulos oikeaksi kuutiota ja säännöllistä dodekaedria (12-tahokasta) vastaavissa verkoissa.

5. Muodosta jokin binääriaakkoston 16-bittinen De Bruijnin jono, so. sellainen 16-

merkkinen jono w Î {0, 1}¹⁶, joka syklisesti luettuna sisältää kaikki 4-merkkiset

jonot w Î {0, 1}⁴ osajonoinaan.