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

1. 1. Kuinka monta lehteä voi (i) enintään, (ii) vähintään olla n-solmuisessa puussa? (Pelkkä vastaus riittää, ei tarvitse todistaa.)
   2. Piirrä kaikki keskenään ei-isomorfiset nelilehtiset, enintään 7-solmuiset puut.
2. Olkoon G = (V,E) (suuntaamaton) verkko, jonka jokaisen solmun asteluku on parillinen. Osoita, että G:n kaaret voidaan suunnata niin, että syntyvässä suhteikossa ovat kunkin solmun tulo- ja lähtöaste (= tulevien ja lähtevien kaarien määrä) keskenään yhtä suuret.
3. 1. Olkoon G = (V,E) vähintään 3-solmuinen yhtenäinen tasoverkko, jonka kaikki syklit ovat vähintään neljän pituisia (so. verkko ei sisällä -muotoista indusoitua aliverkkoa eli on kolmioton). Osoita, että G:n kaarien määrää rajoittaa tällöin epäyhtälö . (Kuten luennolla esitettiin, ilman kolmiottomuusoletusta saadaan heikompi epäyhtälö .)
   2. Osoita edellisen tuloksen nojalla, että verkko ei ole planaarinen.
4. Tarkastellaan 15-bittistä Hamming-koodia (11 viestibittiä, 4 pariteettibittiä, 1 virheen korjaus).
   1. Esitä koodin tarkistusmatriisi, jonka sarakkeet on lueteltu luonnollisessa järjestyksessä.
   2. Montako koodisanaa koodissa on?
   3. Määritä koodin teho (engl. rate).
   4. Osoita, että missään 15-bittisessä, 1 virheen korjaavassa koodissa ei voi olla enempää koodisanoja kuin koodissa , ja se on siten tässä koodiluokassa maksimaalisen tehokas.
   5. Anna jokin kelvollinen koodisana ja vahvista, että todella on .
   6. Määritä yhden bittivirheen sisältävää jonoa 011101110011011 vastaava kelvollinen koodisana.

Pisteytys: kukin tehtävä á 9 pistettä, yhteensä 36 pistettä.