Ramseyn lause
Ladataan...
454.6 KB
suljettu
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tutkielma käsittelee äärellistä Ramseyn lausetta graafiteoreettisesta näkökulmasta. Lauseen mukaan riittävän suuresta kahdella värillä väritetyllä täydellisellä graafilla on aina tietyn kokoinen yksivärinen aligraafi. Ramseyn luku kertoo, kuinka suuri graafin täytyy vähintään olla, jotta tällainen rakenne on väistämätön. Tutkielmassa osoitetaan Ramseyn lukujen keskeisiä ominaisuuksia, todistetaan Ramseyn lause ja selvitetään muutamien Ramseyn lukujen arvot. Lisäksi käsitellään Ramseyn lauseen yleistystä, jossa graafit väritetään useammalla kuin kahdella värillä.