Next: Tästä dokumentista ...
Up: harj6
Previous: harj6
- Piirrä täydellinen kaksijakoinen verkko ja esitä sen
naapurimatriisi. Minkälaisia ovat yleisesti verkkojen ,
ja naapurimatriisit?
- 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.)
- 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?
- Osoita, että asunnossa jossa on vain yksi ulko-ovi on jossakin
huoneessa pariton määrä ovia.
- 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.
- Olkoon (suuntaamaton) verkko, jonka jokaisen solmun asteluku
on parillinen. Osoita, että :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.
- 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 , missä
, .
Osoita, että näin saatavat
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 ja .
(Vihje: Tarkastele verkkoa .)
Next: Tästä dokumentista ...
Up: harj6
Previous: harj6
Pekka Orponen
2000-10-26