prikaz prve stranice dokumenta Prebrojavanje razapinjućih stabala grafa
No public access
undergraduate thesis
Prebrojavanje razapinjućih stabala grafa
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. urn:nbn:hr:168:969031
Marković, Bruno
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Marković, B. (2024). Prebrojavanje razapinjućih stabala grafa (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:969031

Marković, Bruno. "Prebrojavanje razapinjućih stabala grafa." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. https://urn.nsk.hr/urn:nbn:hr:168:969031

Marković, Bruno. "Prebrojavanje razapinjućih stabala grafa." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2024. https://urn.nsk.hr/urn:nbn:hr:168:969031

Marković, B. (2024). 'Prebrojavanje razapinjućih stabala grafa', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 19 October 2024, https://urn.nsk.hr/urn:nbn:hr:168:969031

Marković B. Prebrojavanje razapinjućih stabala grafa [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2024 [cited 2024 October 19] Available at: https://urn.nsk.hr/urn:nbn:hr:168:969031

B. Marković, "Prebrojavanje razapinjućih stabala grafa", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2024. Available at: https://urn.nsk.hr/urn:nbn:hr:168:969031

Metadata
TitlePrebrojavanje razapinjućih stabala grafa
Title (english)Counting the spanning trees of a graph
AuthorBruno Marković
MentorMario Osvin Pavčević (mentor)
Committee memberMario Osvin Pavčević (predsjednik povjerenstva)
Committee memberIva Manojlović (član povjerenstva)
Committee memberMatija Livaić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2024-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:969031
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2024-10-12 21:28:08