DISKREETTI MATEMATIIKKA Harjoitus 7, syksy 2005
1. Onko seuraavissa verkoissa Eulerin ketjua? Perustele vastauksesi ja etsi ketju, jos mahdollista.
a)
•
2222 2222
22 •
@@
@@
@@ •
• • •
•
• • •
b)
•
88 88 88 88 88
8 •
•
8888
88 • •
33333
•
•
c)
•
TT TT TT TT TT TT T
??
??
??
??
??
?? •
•
jj jj jj jj jj jj
j •
•
•
2. Anna esimerkki verkosta, jossa a) ei ole Eulerin eikä Hamiltonin ketjua, b) on Eulerin ketju mutta ei Hamiltonin ketjua, c) ei ole Eulerin ketjua mutta on Hamiltonin ketju, d) on sekä Eulerin että Hamiltonin ketju.
3. Olkoon G = (V, E, α) verkko ja MG sen yhteysmatriisi. Olkoon V = {v1, . . . , vn} ja matriisin MG rivit indeksöity samaan järjestykseen. Osoi- ta, että tällöin matriisin MkG, k ≥ 0, (i, j)-alkio on k-pituisten ketjujen vi → vj lukumäärä. Vihje: Käytä induktiota eksponentin k suhteen ja mieti, mikä on (i, j)-alkio matriisissa Mk+1G =MG·MkG.
Osoita edelleen, että Gon yhtenäinen jos ja vain jos matriisin Pn−1 k=0MkG= (MnG−I)/(MG−I)alkiot ovat nollasta eroavia. Tässä Ion yksikkömatriisi.
4. Nipa ja Pipsa haluavat kulkea (käsi kädessä) taloon autioon (pohjapiirros alla) ja kierrellä siellä niin, että he kävelevät jokaisesta ovesta täsmälleen kerran. Voivatko he löytää tällaisen reitin? Entä silloin, jos he haluavat aloittaa ja lopettaa kierroksensa tähdellä merkittyyn kohtaan?
∗
5. Dominolaatassa on kaksi vierekkäistä neliötä, joissa molemmissa on 06 pistettä. Osoita, että kaikki erilaiset dominolaatat voidaan asettaa ren- kaaksi niin, että vierekkäisissä laatanpäissä on sama numero. Onko tämä mahdollista, jos pisteitä on 16?
