Title: Analysis of various parameters in labelled trees and tree-like structures
Language: English
Authors: Seitz, Georg
Qualification level: Doctoral
Keywords: markierte Bäume; baumartige Strukturen; k-dimensionale Bäume; Inversionen; Vorfahren; Nachkommen; Gradverteilung; lokale Minima
labelled trees; tree-like structures; k-trees; inversions; ancestors; descendants; degree distribution; local minima
Advisor: Panholzer, Alois
Assisting Advisor: Fischer, Ilse 
Issue Date: 2011
Number of Pages: 137
Qualification level: Doctoral
Abstract: 
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-53297
http://hdl.handle.net/20.500.12708/10695
Library ID: AC07812247
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

8
checked on Feb 18, 2021

Download(s)

42
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.