Generiranje svih stabala

undergraduate thesis

• Title (english): Generating All Trees
• Author: Željko Findak
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Mario Bukal (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-08-31, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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