Viisivärityslause
Linna, Henriina (2022)
Linna, Henriina
2022
Tekniikan ja luonnontieteiden kandidaattiohjelma - Bachelor's Programme in Engineering and Natural Sciences
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural 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-12-07
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202212058906
https://urn.fi/URN:NBN:fi:tuni-202212058906
Tiivistelmä
Tässä kanditutkielmassa on tarkoituksena todistaa viisivärityslause, joka on graafiteoriaan liittyvä lause, jossa jokainen tasograafi tai tasossa oleva kartta on väritettävissä korkeintaan viidellä värillä siten, että missään kohtaa ei ole kahta saman väristä aluetta vierekkäin.
Työssä tarkastellaan graafeja sekä niiden värityksiä. Graafi on solmuista eli pisteistä ja särmistä eli viivoista muodostettu matemaattinen malli. Solmut kuvaavat joitain kohteita ja särmät niiden välisiä yhteyksiä. Väritys tarkoittaa graafin solmujen värittämistä eri väreillä siten, etteivät vierekkäiset solmut ole saman värisiä. Tämä tarkoittaa sitä, ettei saman värisillä solmuilla ole yhteistä särmää. Solmuväritystä voidaan käyttää muun muassa työtehtävien jakamiseen, kun samalla työpisteellä ei voida työskennellä yhtäaikaisesti. Myös suurien koulujen tenttijärjestelyt on helppo toteuttaa, kun ne suunnitellaan solmuvärityksen avulla.
Alussa tuodaan esille graafiteorian peruskäsitteitä ja niiden yksinkertaisia todistuksia. Peruskäsitteitä ovat esimerkiksi graafi, solmu, särmä ja aste. Todistettuja lauseita ovat muun muassa Eulerin kaava, särmien lukumäärä sekä osittain todistettu Kuratowskin lause. Esimerkkejä näistä tapauksista löytyy tutkielman alkuosasta.
Kolmannessa luvussa esitellään nelivärityslausetta lyhyesti sekä sen historiaa ja ongelmakohtia. Nelivärityslause todistaa sen, että mikä tahansa tasossa oleva graafi voidaan värittää neljällä värillä siten, ettei naapurisolmut ole saman väriset. Nelivärityslauseen todistamisen ongelmaksi on noussut pitkät todistukset sekä tietokoneavusteisuus.
Viimeisessä luvussa todistetaan luvun kaksi tiedoilla viisivärityslause kahdella tavalla. Ensimmäisessä todistuksessa näytettiin mahdollisimman vähällä solmumäärällä, kuinka kuusi solmua voidaan värittää viidellä värillä, kun yhdestä solmusta lähtevät viisi solmua, jotka kaikki ovat aluksi eri värisiä. Todistuksessa käytettiin apuna polkuja sekä osagraafeja. Todistus osoittaa, että yksi viidestä solmusta voidaan värittää jollain muulla värillä, jolloin keskimmäinen kuudes solmu voidaan värittää yli jäävällä värillä. Tämä todistus löytyy usein oppikirjateksteistä.
Toisessa todistuksessa käytettiin apuna myös kuuden solmun graafiesitystä, jossa solmut on aluksi väritetty kuudella värillä. Todistuksessa ensin solmuja ja särmiä poistamalla sekä solmuja yhdistämällä ja sitten taas särmiä ja solmuja lisäämällä saadaan graafista viisivärinen. Tässä todistuksessa oli tarkoitus löytää keskimmäisen solmun naapurisolmut, jotka eivät ole keskenään naapureita ja siksi ne voidaankin värittää samalla värillä, jolloin vapautuu viides väri keskimmäisen solmun värittämiseen.
Työssä tarkastellaan graafeja sekä niiden värityksiä. Graafi on solmuista eli pisteistä ja särmistä eli viivoista muodostettu matemaattinen malli. Solmut kuvaavat joitain kohteita ja särmät niiden välisiä yhteyksiä. Väritys tarkoittaa graafin solmujen värittämistä eri väreillä siten, etteivät vierekkäiset solmut ole saman värisiä. Tämä tarkoittaa sitä, ettei saman värisillä solmuilla ole yhteistä särmää. Solmuväritystä voidaan käyttää muun muassa työtehtävien jakamiseen, kun samalla työpisteellä ei voida työskennellä yhtäaikaisesti. Myös suurien koulujen tenttijärjestelyt on helppo toteuttaa, kun ne suunnitellaan solmuvärityksen avulla.
Alussa tuodaan esille graafiteorian peruskäsitteitä ja niiden yksinkertaisia todistuksia. Peruskäsitteitä ovat esimerkiksi graafi, solmu, särmä ja aste. Todistettuja lauseita ovat muun muassa Eulerin kaava, särmien lukumäärä sekä osittain todistettu Kuratowskin lause. Esimerkkejä näistä tapauksista löytyy tutkielman alkuosasta.
Kolmannessa luvussa esitellään nelivärityslausetta lyhyesti sekä sen historiaa ja ongelmakohtia. Nelivärityslause todistaa sen, että mikä tahansa tasossa oleva graafi voidaan värittää neljällä värillä siten, ettei naapurisolmut ole saman väriset. Nelivärityslauseen todistamisen ongelmaksi on noussut pitkät todistukset sekä tietokoneavusteisuus.
Viimeisessä luvussa todistetaan luvun kaksi tiedoilla viisivärityslause kahdella tavalla. Ensimmäisessä todistuksessa näytettiin mahdollisimman vähällä solmumäärällä, kuinka kuusi solmua voidaan värittää viidellä värillä, kun yhdestä solmusta lähtevät viisi solmua, jotka kaikki ovat aluksi eri värisiä. Todistuksessa käytettiin apuna polkuja sekä osagraafeja. Todistus osoittaa, että yksi viidestä solmusta voidaan värittää jollain muulla värillä, jolloin keskimmäinen kuudes solmu voidaan värittää yli jäävällä värillä. Tämä todistus löytyy usein oppikirjateksteistä.
Toisessa todistuksessa käytettiin apuna myös kuuden solmun graafiesitystä, jossa solmut on aluksi väritetty kuudella värillä. Todistuksessa ensin solmuja ja särmiä poistamalla sekä solmuja yhdistämällä ja sitten taas särmiä ja solmuja lisäämällä saadaan graafista viisivärinen. Tässä todistuksessa oli tarkoitus löytää keskimmäisen solmun naapurisolmut, jotka eivät ole keskenään naapureita ja siksi ne voidaankin värittää samalla värillä, jolloin vapautuu viides väri keskimmäisen solmun värittämiseen.
Kokoelmat
- Kandidaatintutkielmat [8709]