Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 6, 31.10.-2.11.

1. Piirrä täydellinen kaksijakoinen verkko $K_{2,4}$ ja esitä sen naapurimatriisi. Minkälaisia ovat yleisesti verkkojen $K_n$, $K_{m,n}$ ja $C_n$ naapurimatriisit?

2. Osoita, että seuraavan kuvan esittämät verkot ovat isomorfisia. (Molemmat piirrokset esittävät ns. Petersenin verkkoa, joka on luonnollinen esimerkki tai vastaesimerkki useissa verkkoteoreettisissa konstruktioissa.)
   

3. Piirrä kaikki keskenään ei-isomorfiset 4-solmuiset (suuntaamattomat, yksinkertaiset) verkot. Kauanko suunnilleen kestäisi kaikkien ei-isomorfisten 15-solmuisten verkkojen läpikäynti tietokoneohjelmalla, joka tarkastaa yhden verkon nanosekunnissa?

4. Osoita, että asunnossa jossa on vain yksi ulko-ovi on jossakin huoneessa pariton määrä ovia.

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

6. 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.

7. Dominopelin nappula on kahteen neliöön jaettu suorakaide, jonka molemmissa puoliskoissa on nollasta kuuteen ``silmää''. Jos pelistä jätetään pois nappulat, joiden puoliskojen silmämäärä on sama, ja sovitaan että nappulan suunnistuksella ei ole väliä, huomataan että dominonappulat vastaavat täsmälleen kahden alkion joukkoja $\{i,j\}$, missä $i,j = 0,\dots, 6$, $i \neq j$. Osoita, että näin saatavat ${{7}\choose{2}} = 21$ dominonappulaa voidaan asettaa dominopelin sääntöjen mukaiseksi renkaaksi, jossa kahden toisiaan koskettavan nappulan vastinpuoliskoissa on aina sama silmäluku. Esimerkiksi oheisessa kuvassa on toistensa naapureiksi laillisesti asetetut dominonappulat $\{1,5\}$ ja $\{1,3\}$.
   
   (Vihje: Tarkastele verkkoa $K_7$.)