Graafin virittävien puiden lukumäärän laskeminen matriiseja käyttäen
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset148
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tämän Pro gradu -tutkielman tarkoituksena on tutustuttaa lukija graafien peruskäsitteisiin, graafien virittäviin puihin ja graafien virittävien puiden lukumäärän laskemiseen. Graafi koostuu äärellisestä joukosta solmuja ja niitä yhdistävistä särmistä. Puu on syklitön ja yhtenäinen graafi ja graafin virittävä puu on puu, joka sisältää kaikki alkuperäisen graafin solmut. Graafilla voi olla lukuisia virittäviä puita. \\
Kirchhoffin matriisipuulauseen avulla voidaan selvittää graafien virittävien puiden lukumäärä pelkistetystä Laplacen matriisista. Tutkielmassa hyödynnetään lineaarialgebrasta tunnettuja tuloksia graafin virittävien puiden lukumäärän laskemiseen, kun kyseessä on täydellinen graafi, täydellinen kaksijakoinen graafi tai täydellinen $k$-jakoinen graafi. \\
Lukijalta vaaditaan lineaarialgebran perusteiden tuntemusta. Tutkielma pohjautuu vahvasti kirjallisuuteen. Tutkielman päälähteinä ovat Pertti Koiviston ja Riitta Niemistön luentomoniste $[1]$, David P. Williamsonin luentomateriaali $[2]$ ja Steven Kleen ja Matthew T. Stampsin julkaisu $[3]$.