Verkkojen reunaväritykset

Salo, Tuomas (2022-12-21)
 
Avaa tiedosto
Lataukset: 


Salo, Tuomas
T. Salo
21.12.2022
© 2022 Tuomas Salo. Ellei toisin mainita, uudelleenkäyttö on sallittu Creative Commons Attribution 4.0 International (CC-BY 4.0) -lisenssillä (https://creativecommons.org/licenses/by/4.0/). Uudelleenkäyttö on sallittua edellyttäen, että lähde mainitaan asianmukaisesti ja mahdolliset muutokset merkitään. Sellaisten osien käyttö tai jäljentäminen, jotka eivät ole tekijän tai tekijöiden omaisuutta, saattaa edellyttää lupaa suoraan asianomaisilta oikeudenhaltijoilta.
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-202212213864
Tiivistelmä
Tämän tutkielman aiheena ovat verkkoteorian alle kuuluvat verkkojen reunaväritykset, joissa käsiteltävän silmukattoman verkon jokaiselle reunalle määrätään jokin väri. Ensimmäisessä luvussa pohjustetaan tätä varsinaista aihetta tutustumalla reunaväritysten käsittelyn kannalta olennaisimpiin verkkoteorian peruskäsitteisiin, kuten silmukkaan, vierekkäisiin reunoihin ja asteeseen, sekä erilaisiin verkkoihin. Toisessa luvussa käsitellään ensin reunavärityksiin liittyviä peruskäsitteitä ja määritellään sitten näiden pohjalta verkon reunakromaattinen luku. Reunakromaattisen luvun määrittämistä käsitellään sekä yksinkertaisen esimerkin että lauseiden kautta. Keskeisimmässä roolissa on kaksijakoisen verkon reunakromaattisen luvun osoittaminen. Reunaväritysten sovelluskohteena tarkastellaan lukujärjestysongelmaa, jossa tehtävänä on määrittää lukujärjestys kouluun mahdollisimman pienellä tuntimäärällä.

Tutkielman lukijan on hyvä omata tietämystä yliopistotason matemaattisista merkinnöistä ja käsitteistä, mutta esitietoja verkkoteoriasta ei vaadita. Esimerkit ovat itse tehtyjä, ja todistuksia on tarvittaessa muokattu hieman sekä kirjoitettu yksityiskohtaisemmin kuin lähteessä.
Kokoelmat
https://creativecommons.org/licenses/by/4.0/
Ellei muuten mainita, aineiston lisenssi on https://creativecommons.org/licenses/by/4.0/