Analysis of various parameters in labelled trees and tree-like structures / von Georg Seitz
VerfasserSeitz, Georg
Begutachter / BegutachterinPanholzer, Alois ; Fischer, Ilse
UmfangV, 137 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2011
Zsfassung in dt. Sprache
Bibl. ReferenzOeBB
Schlagwörter (DE)markierte Bäume / baumartige Strukturen / k-dimensionale Bäume / Inversionen / Vorfahren / Nachkommen / Gradverteilung / lokale Minima
Schlagwörter (EN)labelled trees / tree-like structures / k-trees / inversions / ancestors / descendants / degree distribution / local minima
Schlagwörter (GND)Baum <Mathematik> / Graphmarkierung / Inversion <Mathematik> / Lokales Minimum / Knoten <Mathematik> / Parameter <Mathematik>
URNurn:nbn:at:at-ubtuw:1-53297 Persistent Identifier (URN)
 Das Werk ist frei verfügbar
Analysis of various parameters in labelled trees and tree-like structures [0.98 mb]
Zusammenfassung (Englisch)

We analyse various parameters in labelled trees (i.e. in trees in which the nodes are labelled with distinct integers) and, more generally, in labelled tree-like graph structures. In trees, we consider two parameters which have already been extensively studied in finite sequences (especially in permutations), namely the number of inversions and the number of local minima. We analyse the behaviour of these quantities in random trees of various labelled tree families. Moreover, we consider a class of graphs known as k-trees. These are graphs with a tree-like structure, which can be constructed by a certain randomised graph evolution process, and which can be seen as a simple model for the growth of complex networks. In these graphs, we study parameters which have already been analysed in ordinary trees, namely the number of ancestors and descendants of nodes and the degree distribution. By the use of generating functions we obtain to a large extent very precise results on the exact distribution of these quantities if the size of the considered random objects is fixed. Apart from that, we can characterize the limiting behaviour of each of these quantities as the size of the considered objects tends to infinity.