Reiner, P. (2018). Kombinatorische Abzählprobleme bei markierten k-Bäumen [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.50270
k-trees; generation functions; node-degrees; desendants; ascendants; enumeration formulas; local cluster coefficient; limiting distribution
en
Abstract:
Die k-Bäume sind in der Graphentheorie eine Verallgemeinerung der Bäume. Durch ihren rekursiven Aufbau sind die k-Bäume interessant als Modelle für komplexe Netzwerke, welche in verschiedenen Formen vielerorts in der Wissenschaft auftreten. In der Arbeit wird für verschiedene Arten von k-Bäumen das kombinatorische Abzählungsproblem gelöst. Mit rekursiven Konstruktionen, welche nach verschiedenen probabilistischen Regeln ablaufen, werden Wahrscheinlichkeitsverteilungen auf den k-Bäumen erzeugt. Diese Verteilungen können zum Teil kombinatorisch interpretiert werden und in Zusammenhang mit bestimmten Typen von k-Bäumen gebracht werden. Ausgestattet mit einem Wachstum dieses Typs werden für die k-Bäume die Verteilungen für den Knotengrad, die Nachfahren und die Vorfahren bestimmt. Diese Größen werden für einen beliebigen Knoten auch auf ihre Grenzverteilung untersucht.
de
In graph theory k-trees are a generalisation of ordinary trees. As recursive defined structures they can be seen as complex network models. Complex networks play an important role in different parts of science. In this thesis we will count various types of k-trees. These graphs can be generated with probabilistic growth rules. Distinct forms of k-trees can be identified with some growth rules. Formulas will be derived for the degree, the descendants and the ancestors. In particular we will study for each model the exact distribution of a node and calculate the limiting distribution of a random node.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers