University of Oulu

Verkkojen reunaväritykset

Saved in:
Author: Salo, Tuomas1
Organizations: 1University of Oulu, Faculty of Science, Mathematics
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 0.7 MB)
Pages: 26
Persistent link: http://urn.fi/URN:NBN:fi:oulu-202212213864
Language: Finnish
Published: Oulu : T. Salo, 2022
Publish Date: 2022-12-21
Thesis type: Bachelor's thesis
Tutor: Käenmäki, Antti
Myllylä, Kari
Description:

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ä.

see all

Subjects:
Copyright information: © Tuomas Salo, 2022. Except otherwise noted, the reuse of this document is authorised under a Creative Commons Attribution 4.0 International (CC-BY 4.0) licence (https://creativecommons.org/licenses/by/4.0/). This means that reuse is allowed provided appropriate credit is given and any changes are indicated. For any use or reproduction of elements that are not owned by the author(s), permission may need to be directly from the respective right holders.
  https://creativecommons.org/licenses/by/4.0/