Title: Vergleich von einfach erzeugten Bäumen und Pólya-Bäumen
Other Titles: Comparison of simply generated trees and Pólya trees
Language: Deutsch
Authors: Meyer, Nicolas 
Qualification level: Diploma
Advisor: Gittenberger, Bernhard 
Issue Date: 2020
Citation: 
Meyer, N. (2020). Vergleich von einfach erzeugten Bäumen und Pólya-Bäumen [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.64844
Number of Pages: 125
Qualification level: Diploma
Abstract: 
Unter einem Wurzelbaum versteht man einen einfach zusammenhängenden Graph mit einem ausgezeichneten Knoten. Wir betrachten dabei zwei Klassen von Wurzelbäumen: eine allgemeinere, die einfach erzeugten Bäume, und eine speziellere, die sogenannten Pólya-Bäume. Das Ziel dieser Arbeit ist, verschiedene Eigenschaften dieser zwei Klassen zu vergleichen. Es ist leicht zu zeigen, dass Pólya-Bäume nicht einfach erzeugt sind. Doch haben die beiden Klassen viele Ähnlichkeiten. Um diese einzusehen werden folgende zwei Methoden verwendet: Anwendung von erzeugende Funktionen und asymptotische Bestimmung der Koeffizienten; Analyse von Parametern, insbesondere Berechnung von Mittelwert, Varianz und Grenzverteilung.

A rooted tree is a simple connected graph with a distinguished vertex. We consider two families of rooted trees: a more general one, the simply generated trees, and a more specific one, the so called Pólya trees. The goal of this work is to compare different properties of these two classes. It is easy to show that Pólya trees are not simply generated. However, both classes have many similarities. In order to get these, the following two methods are used: application of generating functions and asymptotic determination of its coefficients; analysis of parameters, especially solving mean value, variance and limit law.
Keywords: asymptotische Abzählung; einfach erzeugte Bäume; Pólya-Bäume; Singularitätenanalyse; erzeugende Funktionen
asymptotic enumeration; simply generated trees; Pólya trees; singularity analysis; generating functions
URI: https://doi.org/10.34726/hss.2020.64844
http://hdl.handle.net/20.500.12708/16409
DOI: 10.34726/hss.2020.64844
Library ID: AC16098944
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

23
checked on Sep 10, 2021

Download(s)

10
checked on Sep 10, 2021

Google ScholarTM

Check


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