Broj razapinjućih stabala grafa

završni rad

• Naslov (engleski): Total number of Spanning Trees in a Graph
• Autor: Lovro Gaćina
• Mentor: Mario Krnić (mentor)
• Član povjerenstva: Mario Krnić (predsjednik povjerenstva)
• Član povjerenstva: Josipa Pina Milišić (član povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-09-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Tema ovog rada su različiti načini prebrojavanja razapinjućih stabala. Prvo se predstavljaju osnovni pojmovi teorije grafova s posebnim fokusom na stabla i njihova svojstva. Zatim se predstavlja pojam razapinjućih stabala grafa. Iskazuju se i dokazuju dva načina za računanje broja razapinjućih stabala: osnovna rekurzija i matrični teorem o stablima. Pomoću te dvije metode izračunava se taj broj za određene familije grafa: kotač, potpuni bipartitni graf i potpuni graf. Na kraju, prikazuje se rad jednostavne aplikacije za kreiranje grafova i računanje broja njihovih razapinjućih stabala.

Sažetak (engleski)

The thesis of this paper are the ways of calculating the number of spanning trees of a given graph. Firstly, the basic concepts of graph theory are introduced, with additional focus placed on trees and their properties. Then, the concept of spanning trees is introduced. Two methods of calculating the number of a graph's spanning trees are shown and proven: the general recursion and the Matrix-tree Theorem. These methods are used to calculate that number for certain families of graph: wheel, complete bipartite graph and complete graph. Finally, a simple application for creating graphs and calculating the number of their spanning trees is demonstrated.

• Ključne riječi: Teorija grafova; grafovi; stabla; razapinjuća stabla
• Ključne riječi (engleski): Graph theory; graphs; trees; spanning trees
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:281495
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 08:52:35