JultikaUniversity of Oulu repository

Tässä pro gradu -tutkielmassa perehdytään lähdekirjallisuuden avulla graafiteorian perusteisiin ja sen syntyhistoriaan sekä Hamiltonin sykliin. Tutkielman ensisijaisena tarkoituksena on esittää ja todistaa ehtoja graafin hamiltonilaisuudelle eli esittää tulokset sille, millaisista graafeista hamiltonin syklin voi löytää. Tutkielman päälähteenä on käytetty R. Diestelin teosta Graph Theory (4.p). Ensimmäisessä luvussa käsitellään graafiteorian historiaa ja erityisesti Leonhard Eulerin vaikutusta graafiteorian syntyyn. Lisäksi käsitellään lyhyesti hamiltonin sykliin liittyvää historiaa. Toisessa luvussa määritellään graafiteoriaan liittyviä, tutkielmassa myöhemmin tarvittavia peruskäsitteitä. Luvussa määritellään piste, viiva, graafi, naapuri, aste, polku, sykli, kulku ja aligraafi sekä näihin liittyviä muita käsitteitä. Kolmannessa luvussa käsitellään graafien yhtenäisyyttä ja todistetaan graafiteorian eräs kulmakivistä, Mengerin lause. Lausetta tarvitaan myöhemmin tutkielmassa käsiteltäessä riittäviä ehtoja hamiltonilaisuudelle. Neljännessä luvussa määritellään Euleriaaninen graafi ja todistetaan Eulerin vuonna 1793 esittämä lause, joka antaa välttämättömän ja riittävän ehdon graafin euleriaanisuudelle. Viimeisessä luvussa keskitytään graafin hamiltonilaisuuteen ja siihen, millaisista graafeista hamiltonin syklin voi löytää. Aluksi määritellään hamiltonin polku ja sykli sekä graafin hamiltonilaisuus. Sen jälkeen siirrytään käsittelemään graafin hamiltonilaisuuden ehtoja. Ensin esitetään graafin hamiltonilaisuudelle kolme triviaalia ehtoa ja sitten todistetaan yksi välttämätön, graafin komponenttien määrään liittyvä ehto. Kaikki tämän ehdon täyttävät graafit eivät kuitenkaan ole hamiltonilaisia. Tästä annetaan esimerkkinä Petersenin graafi. Lopuksi esitetään ja todistetaan neljä riittävää ehtoa, jotka toteutuessaan takaavat graafin hamiltonilaisuuden. Ensimmäisenä on klassinen Diracin lause, jossa ehdot liittyvät graafin minimiasteeseen. Toisena käsitellään lause, jonka ehto liittyy graafin suurimman riippumattoman pistejoukon koon suhteesta graafin yhtenäisyysluvun suuruuteen. Kolmantena on Asratianin ja Khachatrianin lause, jossa käsitellään graafin paikallisen minimiasteen merkitystä hamiltonilaisuuteen. Neljäntenä tapauksena käsitellään Chvátalin lause, jonka ehto liittyy graafin astejonoon.