Prebrojavanje razapinjućih stabala grafa

undergraduate thesis

• Title (english): Counting spanning trees of a graph
• Author: Dorian Kablar
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Lenka Mihoković (član povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Tema ovog rada je prebrojavanje razapinjućih stabala grafa. Predstavljeni su osnovni pojmovi teorije grafova, zatim je predstavljen pojam razapinjućeg grafa, razne primjene, te računanje broja razapinjućih stabala pomoću rekurzivnih relacija. Predstavljeni su iskaz i dokaz matričnog teorema o stablima, te primjene. Na kraju je prikazan rad web-aplikacije Graphelite za računanje s grafovima.

Abstract (english)

The topic for this thesis is counting spanning trees. We presented the basic concepts of graph theory, then we introduced the notion of spanning trees and described some applications. We stated and proved the Matrix-Tree Theorem and demonstrated applications. In the end, we showed the implementation of the Graphelite web-application for computations on graphs.

• Keywords: teorija grafova; stabla; razapinjuća stabla; matrični teorem o stablima
• Keywords (english): graph theory; trees; spanning trees; matrix-tree theorem
• Language: croatian
• URN:NBN: urn:nbn:hr:168:483124
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 20:44:38