MAT282 Johdatus diskreettiin matematiikkaan
2. välikoe ke 29.11.2000 klo 8-11

1. Anna esimerkit yhtenäisistä verkoista, joissa:
   1. ei ole Eulerin kierrosta eikä Hamiltonin kehää;
   2. on Eulerin kierros mutta ei Hamiltonin kehää;
   3. on Hamiltonin kehä mutta ei Eulerin kierrosta;
   4. on sekä Eulerin kierros että Hamiltonin kehä.

2. Merkitään verkon $G = (V,E)$ solmujen keskimääräistä astetta
   
   $$\bar{\delta}_G = \frac{1}{\vert V\vert}\sum_{u \in V} \deg(u).$$
   
   
   Osoita, että kaikilla tasoverkoilla $G$ on $\bar{\delta}_G < 6$, ja että puiden $T$ keskimääräinen aste lähestyy raja-arvoa $\lim \bar{\delta}_T = 2$, kun solmujen lukumäärä kasvaa.

3. 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. Määritä hyperkuutioverkon $H_n$ väriluku $\chi(H_n)$. (Perusteltu vastaus.)

4. Suunnittele jokin kuusibittinen, yhden virheen korjaava lineaarinen koodi, jossa on 8 koodisanaa. Esitä koodisi tarkistusmatriisi ja luettele sen mukaiset koodisanat. Esitä, miten jokin yhden bittivirheen sisältävä jono korjattaisiin suunnittelemaasi tarkistusmatriisia käyttäen.

Pisteytys: tehtävät 1 ja 2 á 8 pistettä, tehtävät 3 ja 4 á 7 pistettä, yhteensä 30 pistettä.