Graafin virittävien puiden lukumäärän laskeminen matriiseja käyttäen

Abstract

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]$.