Generating All Trees

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.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