Skip to main content
Login | Suomeksi | På svenska | In English

Hamiltonin sykleistä Cayley-verkoissa

Show full item record

Title: Hamiltonin sykleistä Cayley-verkoissa
Author(s): Pohjonen, Kaisa
Contributor: University of Helsinki, Faculty of Science, Department of Mathematics and Statistics
Discipline: Mathematics
Language: Finnish
Acceptance year: 2012
Abstract:
Tässä tutkielmassa tarkastellaan, voidaanko määrätyn ryhmän alkiot esittää määrättyjen virittäjäalkioiden avulla ketjuna, joka sisältää kaikki ryhmän alkiot täsmälleen kerran, alkaa ja päättyy samaan alkioon ja jossa alkiosta toiseen siirrytään virittäjää pitkin. Kysymyksellä on yhteyksiä klassisiin peleihin (ratsun kierto shakkilaudalla) sekä esimerkiksi perinteiseen englantilaiseen tapaan soittaa kirkonkelloja (change ringing). Ongelman matemaattisessa muotoilussa käytetään Cayley-verkkoja. Ryhmä G ja sen virittäjistö S määräävät Cayley-verkon Cay(S:G), jonka solmut ovat ryhmän alkiot ja jossa solmujen x ja xs välillä on särmä, kun s ∈ S. Tällöin haluttu alkioketju muodostaa verkkoon Hamiltonin syklin. Työssä käsitellään sekä suunnattuja että suuntaamattomia Cayley-verkkoja. Työn käsittelytapa on verkoista huolimatta ryhmäteoreettinen. Tutkielmassa käydään läpi tarvittavia ryhmä- ja verkkoteoreettisia esitietoja sekä todistetaan Hamiltonin syklien olemassaolo eräiden tulo- ja Abelin ryhmien Cayley-verkoille. Työ huipentuu Dave Witten vuonna 1986 todistamaan tulokseen, että p-ryhmien Cayley-verkoissa on aina Hamiltonin sykli, riippumatta valitusta virittäjistöstä.


Files in this item

Files Size Format View
pro_gradu_pohjonen.pdf 557.0Kb PDF

This item appears in the following Collection(s)

Show full item record