Graafien värittämisestä

Abstract

Tämän tutkielman tarkoituksena on esitellä graafien värittämistä, joka on yksi graafiteorian tunnetuimmista aihealueista. Tutkielman alussa esitellään graafiteorian peruskäsitteitä sekä tutkielman kannalta olennaisia määritelmiä ja lauseita. Tärkeää on ymmärtää tasograafin, solmun asteen, komponentin ja aligraafin käsitteet. Tarkastelut on rajattu käsittelemään vain yksinkertaisia graafeja, jotta tutkielma ei olisi liian laaja. Eräs työn keskeisistä tuloksista on viisivärilause, jonka mukaan jokainen tasograafi voidaan värittää viidellä värillä. Tämän tuloksen todistuksen ymmärtämiseksi tutkielmassa esitetään Jordanin käyrälause sekä osoitetaan, että jokaisessa tasograafissa on solmu, jonka aste on korkeintaan viisi. Viisivärilauseen lisäksi esitetään myös heikompi kuusivärilause sekä nelivärilauseen historiaa. Viisivärilauseen jälkeen tarkastellaan graafin solmujen värittämistä kahdella värillä ja osoitetaan, että graafi voidaan värittää kahdella värillä, jos ja vain jos siinä ei ole paritonta silmukkaa. Lisäksi esitetään graafin solmujen ja alueiden värittämisen välinen suhde ja osoitetaan, että tasograafin alueet voidaan värittää kahdella värillä, jos ja vain jos graafi on Eulerin graafi. Tämän tuloksen osoittamiseksi määritellään ensin Eulerin graafi. Tutkielman lopussa toisena keskeisenä tuloksena todistetaan Brooksin lause, joka kertoo, että jos graafi ei ole täydellinen eikä pariton silmukka, niin graafin väriluku on aina pienempi tai yhtä suuri kuin graafin maksimiaste. Johdatteluna tähän lauseeseen esitetään ja todistetaan ensin muita lauseita koskien graafin väriluvun ylärajaa. Lisäksi tutustutaan ahneeseen algoritmiin, joka on yksinkertainen ja hyvin tunnettu tapa värittää graafi käyttämättä liikaa värejä. Ahnetta algoritmia havainnollistetaan esimerkin avulla.