University of Oulu

Hamiltonin sykleistä graafiteoriassa

Saved in:
Author: Nordberg, Ohto
Organizations: University of Oulu, Faculty of Science, Department of Mathematical Sciences, Mathematics
Format: ebook
Online Access: PDF Full Text (PDF, 1 MB)
Persistent link: http://urn.fi/URN:NBN:fi:oulu-201303061083
Language: Finnish
Published: Oulu : O. Nordberg, 2013
Publish Date: 2013-03-06
Physical Description: 31 p.
Thesis type: Master's thesis
Tutor: Niemenmaa, Markku
Reviewer: Myllylä, Kari
Niemenmaa, Markku
Description: 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.
Subjects:
Copyright information: This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.