Diverse families of random rooted trees; a compilation of characteristics

Abstract

Die Diplomarbeit befasst sich mit vier großen Gruppen von Zufallsbäumen, den Pólya trees, simply generated trees, increasing trees, und der relativ neuen Struktur der Scale-free trees.<br />Verschiedenste Charakteristiken, Gemeinsamkeiten und Unterschiede dieser Gruppen werden besprochen, wie zum Beispiel die Grenzverteilung der Knotengrade. Die Ergebnisse werden meist ausgehend von der erzeugenden Funktion der fraglichen Struktur unter Zuhilfenahme von Methoden aus der Stochastik und der Singularitätsanalyse gefunden.<br />

This diploma thesis deals with four groups of random trees, namely Pólya trees, simply generated trees, increasing trees and scale-free trees. Different characteristics, similarities and differences of these varieties are discussed, e.g. the limiting distribution of node-degrees. Most results are obtained using generating functions and methods of singularity analysis and stochastics.