Prebrojavanje razapinjućih stabala grafa

završni rad

• Naslov (engleski): Counting the spanning trees of a graph
• Autor: Bruno Marković
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Iva Manojlović (član povjerenstva)
• Član povjerenstva: Matija Livaić (č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: 2024-07-09, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

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