Generiranje svih stabala

završni rad

• Naslov (engleski): Generating All Trees
• Autor: Željko Findak
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Mario Bukal (č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: 2015-08-31, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Generiranje svih stabala je problem generiranja kombinatornih objekata. Postoje razne vrste stabala, dok su ovdje obrađena označena, korijenska, binarna i slobodna. Odgovor na pitanje koliko ima označenih stabala s n čvorova daje Cayleyev teorem, broj binarnih stabala je element niza Catalanovih brojeva, dok za broj slobodnih stabala postoji gornja i donja ograda. Prikazani su razni načini zapisa pojedinih vrsta stabala (matrica incidencije, lista bridova, Prüferov kod, planarni kod, zapis razina). Prikazani su i implementirani algoritmi za generiranje stabala; algoritam za označena stabla temeljen na Prüferovom kodu, za korijenska stabla prema Beyer-Hedetniemi, za slobodna stabla Wright-Richmond-Odlyzko-McKay.

Sažetak (engleski)

Generating all trees is categorized as combinatorial objects generation problem. There are many types of trees, although here were covered labeled, rooted, binary and free trees. Another important problem is counting of such objects. Answer to that is given in Cayley's theorem for number of labeled trees with n vertices, number of binary trees is element of Catalan’s series and for number of free trees there is an upper and lower bound. Here many ways of representing a tree are shown, such as adjacency matrix, list of edges, Prüfer’s code, planar code and level sequence. Furthermore, algorithms for generating all trees are presented and implemented; for labeled trees based on Prüfer’s code, Beyer-Hedetniemi algorithm for generating rooted trees, Wright-Richmond-Odlyzko-McKay algorithm for generating free trees.

• Ključne riječi: generiranje stabala; stabla; teorija grafova; označeno stablo; korijensko stablo; binarno stablo; slobodno stablo; Prüferov kod
• Ključne riječi (engleski): generating trees; trees; graph theory; labeled tree; rooted tree; binary tree; free tree; Prüfer’s code
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:269720
• 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: 2018-02-06 08:44:38