Prebrojavanje razapinjućih stabala grafa

undergraduate thesis

• Title (english): Counting the spanning trees of a graph
• Author: Bruno Marković
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Iva Manojlović (član povjerenstva)
• Committee member: Matija Livaić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-09, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Broj razapinjućih stabala grafa općenito je zahtjevan zadatak koji se ne može riješiti jednostavnim tehnikama elementarnog prebrojavanja. Iako je u općenitom slučaju teško prebrojati sva razapinjuća stabla zbog veličine prostora rješenja, postoje grafovi za koje je poznat broj razapinjućih stabala. Cilj ovog rada je opisati i implementirati formulu i algoritme za neke od osnovnih metoda prebrojavanja razapinjućih stabala. Prvo je implementirana Kirchhoffova formula koja je najefikasniji način za dobiti broj razapinjućih stabala, no ona ne pronalazi stabla već samo daje njihov ukupni broj. Zbog toga smo posegnuli za drugim algoritmima i posvetili se nekim od već razrađenih metoda prebrojavanja stabala. Napravili smo algoritam koji koristi metodu testiraj i odaberi. Taj algoritam ima visoku vremensku složenost te samim time nije efikasan. Zbog toga smo implementirali i Mintyev algoritam čija složenost raste linearno s brojem razapinjućih stabala. Iako je Mintyev algoritam mnogo brži od prethodnog, treba imati na umu da skup rješenja brzo raste s brojem bridova i vrhova te zbog toga izvođenje može biti dugotrajno za velike grafove.

Abstract (english)

The task of counting the number of spanning trees in a graph is generally challenging and cannot be solved using simple elementary counting techniques. Although it is difficult to count all spanning trees in the general case due to the size of the solution space, there are graphs for which the number of spanning trees is well known. This work aims to describe and implement the formula and algorithms for some of the basic methods of counting spanning trees. First, Kirchhoff’s formula was implemented, which is the most efficient way to obtain the number of spanning trees, but it only gives their number without finding the actual trees. Therefore, we resorted to other algorithms and focused on some of the well-established methods for counting trees. We developed an algorithm that uses the test and select method, which has a high time complexity and is therefore inefficient. Consequently, we implemented Minty’s algorithm, whose complexity grows linearly with the number of spanning trees. Although Minty’s algorithm is much faster than the previous one, it should be noted that the solution space grows rapidly with the number of edges and vertices, and therefore, the execution time can be long for large graphs.

• Keywords: Graf; Stabla; Razapinjuće stablo; Kirchhoffova formula; Mintyev algoritam; Metoda sukcesivnog smanjivanja grafa; Metoda testiraj i odaberi
• Keywords (english): Graph; Trees; Spanning Tree; Kirchhoff’s Formula; Minty’s Algorithm; Successive reduction of graph method; Test and select method
• Language: croatian
• URN:NBN: urn:nbn:hr:168:969031
• 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: Open access
• Created on: 2024-10-12 21:28:08