Yleistettyjen ratsujen Hamiltonin kierrokset shakkilaudoilla
Viskari, Arttu (2022)
2022
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2022-11-22
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202210277970
https://urn.fi/URN:NBN:fi:tuni-202210277970
Tiivistelmä
Tässä tutkielmassa tarkastellaan Hamiltonin kierrosten olemassaoloa ja ominaisuuksia erikokoisilla shakkilaudoilla. Kierroksia tutkitaan sekä tavallisen ratsun että yleistettyjen ratsujen näkökulmasta. Hamiltonin kierros on polku, joka käy läpi jokaisen solmujoukon alkion tasan kerran palaten takaisin alkusolmuunsa.
Tutkielman luvussa 2 käydään läpi tutkielmassa tarvittavia keskeisiä verkkoteorian käsitteitä. Luvussa syvennytään yhtenäisyyden käsitteeseen, komponentteihin sekä Hamiltonin verkkoon.
Tämän jälkeen, luvussa 3, käsitellään tavallisen ratsun kierroksia äärellisillä shakkilaudoilla. Näiden kierrosten olemassaololle kootaan riittävät ja välttämättömät ehdot, jotka on esitetty Schwenkin lauseessa. Schwenkin lauseen todistamiseksi rakennetaan yhdeksän ratsun kierrosta, joista laajennetaan kierrokset jokaiselle Schwenkin lauseen mukaiselle laudalle.
Luvussa 4 laajennetaan tavallisen ratsun käsitettä (a,b)-ratsuksi ja esitetään välttämättömät ehdot (a,b)-ratsun kierroksille. Luvussa 4 tarkastellaan erityisesti (2,3)-ratsun kierrosten olemassaoloa äärellisillä shakkilaudoilla.
Luvussa 5 käsitellään (a,1)-ratsun kierroksia neliön muotoisilla shakkilaudoilla. Luku aloitetaan käymällä läpi, kuinka kierrokset voidaan laajentaa suuremmille laudoille. Tämän jälkeen muodostetaan kierrokset perustapauksille, joista kierrosten laajentaminen suuremmille laudoille on mahdollista. Lopuksi kootaan lause, joka todistaa (a,1)-ratsun kierrosten olemassaolon riittävän suurilla laudoilla.
Tutkielman lopuksi, luvussa 6, kootaan yhteenveto ratsun kierroksista erikokoisilla shakkilaudoilla
Tutkielman luvussa 2 käydään läpi tutkielmassa tarvittavia keskeisiä verkkoteorian käsitteitä. Luvussa syvennytään yhtenäisyyden käsitteeseen, komponentteihin sekä Hamiltonin verkkoon.
Tämän jälkeen, luvussa 3, käsitellään tavallisen ratsun kierroksia äärellisillä shakkilaudoilla. Näiden kierrosten olemassaololle kootaan riittävät ja välttämättömät ehdot, jotka on esitetty Schwenkin lauseessa. Schwenkin lauseen todistamiseksi rakennetaan yhdeksän ratsun kierrosta, joista laajennetaan kierrokset jokaiselle Schwenkin lauseen mukaiselle laudalle.
Luvussa 4 laajennetaan tavallisen ratsun käsitettä (a,b)-ratsuksi ja esitetään välttämättömät ehdot (a,b)-ratsun kierroksille. Luvussa 4 tarkastellaan erityisesti (2,3)-ratsun kierrosten olemassaoloa äärellisillä shakkilaudoilla.
Luvussa 5 käsitellään (a,1)-ratsun kierroksia neliön muotoisilla shakkilaudoilla. Luku aloitetaan käymällä läpi, kuinka kierrokset voidaan laajentaa suuremmille laudoille. Tämän jälkeen muodostetaan kierrokset perustapauksille, joista kierrosten laajentaminen suuremmille laudoille on mahdollista. Lopuksi kootaan lause, joka todistaa (a,1)-ratsun kierrosten olemassaolon riittävän suurilla laudoilla.
Tutkielman lopuksi, luvussa 6, kootaan yhteenveto ratsun kierroksista erikokoisilla shakkilaudoilla