Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 7, 7.-9.11.

1. Muodosta jokin binääriaakkoston 16-bittinen De Bruijnin jono, so. sellainen 16-merkkinen jono $w \in \{0,1\}^{16}$, joka syklisesti luettuna sisältää kaikki 4-merkkiset jonot $x \in \{0,1\}^{4}$ osajonoinaan.

2. 1. Piirrä kaikki keskenään ei-isomorfiset 6-solmuiset puut.
   2. Osoita, että $n$-solmuisten puiden isomorfiatyyppejä on ainakin $e^{n-1}/n^3$ kappaletta. (Ohje: Sovella Sylvesterin-Cayleyn lausetta ja epäyhtälöä $e(\frac{n}{e})^n \leq n! \leq ne(\frac{n}{e})^n$.)

3. Osoita, että verkko $G = (V,E)$ on puu, jos ja vain jos se on syklitön, mutta minkä tahansa $G$:stä puuttuvan kaaren lisääminen synnyttää siihen syklin.

4. Todista oikeaksi seuraavat väitteet:
   1. Jokaisessa vähintään kaksisolmuisessa puussa on ainakin kaksi lehteä.
   2. Olkoon $G = (V,E)$ mielivaltainen verkko ja $u \in V$ jokin $G$:n lehti (= solmu, jonka asteluku on 1). Tällöin $G$ on puu, jos ja vain jos verkko $G-u$ (= solmujoukon $V\setminus\{u\}$ virittämä $G$:n aliverkko) on puu.

5. Muodosta seuraavien puiden Prüfer-koodit:
   
   Minkä 7-solmuisen puun Prüfer-koodi on (3,1,4,1,5)?

6. Hyperkuutioverkon $H_n$ solmuina ovat kaikki $n$-bittiset binäärijonot $u \in \{0,1\}^n$, ja solmujen $u$ ja $v$ välillä on kaari, jos ja vain jos niitä vastaavat binäärijonot eroavat toisistaan tasan yhdessä kohden.
   1. Piirrä verkot $H_3$ ja $H_4$. Montako solmua on verkossa $H_n$?
   2. Millä $n$:n arvoilla verkko $H_n$ sisältää Eulerin kierroksen?
   3. Määritä verkon $H_n$ halkaisija, so. suurin mahdollinen kahden solmun välinen etäisyys $d(H_n) = \max \{d(u,v) \;\vert\; u, v \in H_n\}.$ (Solmujen $u, v \in H_n$ välinen etäisyys $d(u,v)$ tarkoittaa lyhimmän niitä yhdistävän polun pituutta.)

7. Todista induktiolla $n$:n suhteen, että jokainen edellisen tehtävän mukainen hyperkuutioverkko $H_n$, $n \geq 2$, sisältää Hamiltonin kehän. (Ohje: Oleta induktiivisesti, että verkko $H_n$ sisältää Hamiltonin polun solmusta $u = 00\dots 0$ solmuun $v = 10\dots 0$. Totea, että kahdesta tällaisesta polusta voidaan yhdistää verkon $H_{n+1}$ samanmuotoinen Hamiltonin polku.) Piirrä em. konstruktion mukaiset verkkojen $H_3$ ja $H_4$ Hamiltonin kehät.

   (Huomautus: Hyperkuution $H_n$ Hamiltonin kehät vastaavat kokonaislukujen 0, ..., $2^n-1$ ns. syklisiä Gray-koodeja, joissa kahden peräkkäisen luvun binääriesitykset poikkeavat aina vain yhdessä bitissä.)