<div class="csl-bib-body">
<div class="csl-entry">Kraus, V. (2011). <i>Asymptotic study of families of unlabelled trees and other unlabelled graph structures</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-45174</div>
</div>
Die vorliegende Dissertation beschäftigt sich mit der asymptotischen Analyse von zufälligen Graphenstrukturen, besonders Zufallsbäumen. Wir betrachten dazu die Menge von Objekten einer festen Größe (=Anzahl der Knoten) n und wählen daraus ein bezüglich der Gleichverteilung zufälliges Objekt aus. Wir untersuchen Eigenschaften solcher zufälliger Vertreter, wobei die Größe n gegen Unendlich strebt.<br />Wir zeigen für die Klasse der Polya-Bäume, dass die Größe eines Ward-Baumes asymptotisch von Ordnung \sqrt{n} ist, wobei ein Ward-Baum ein Unterbaum ist, der am Vater eines Blattes verwurzelt ist. Weiters zeigen wir, dass der Gradprofilprozess von Polya Bäumen schwach gegen die lokale Zeit einer Brown'schen Exkursion konvergiert.<br />Für verschiedene Modelle Boole'scher Bäume erhalten wir Resultate über die auf der Menge der Boole'schen Funktionen induzierte Wahrscheinlichkeitsverteilung. Genauer zeigen wir, dass die Wahrscheinlichkeit einer Funktion in direktem Zusammenhang mit ihrer Komplexität steht und das die verschiedenen Modelle verschiedene Wahrscheinlichkeitsverteilungen induzieren.<br />Im letzten Kapitel zeigen wir einen zentralen Grenzwertsatz für die Gradverteilung in unmarkierten subkritschen planaren Graphenklassen, sowohl für allgemeine Graphen als auch für ihre 2-zusammenhängenden Subklassen.<br />Alle Ergebnisse werden mithilfe von erzeugenden Funktionen und ihrer Singularitätenstruktur gewonnen, ein sehr mächtiges Werkzeug aus der analytischen Kombinatorik.<br />
de
dc.description.abstract
This thesis deals with the asymptotic analysis of random graph structures, especially random trees. We consider the set of objects of fixed size (=number of vertices) n and choose an object from it uniformly at random. We study properties of such a random representative, when the size n tends to infinity. We show for the class of Polya trees that the size of a Ward-tree is asymptotically of order \sqrt{n}, where a Ward-tree is a subtree rooted at a parent node of a leaf. We further show that the degree profile process of Polya trees converges weakly to the local time of a Brownian excursion. For several models of Boolean trees we obtain results on the probability distribution they induce on the set of Boolean functions. To be more precise, we show that the probability of a function is in relation to its complexity and that different models induce different probability distributions.<br />In the last chapter we show a central limit theorem for the degree distribution in unlabelled planar subcritical graphs, as well for general graphs as for their 2-connected subclasses.<br />All results are obtained via generating functions and their singularity analysis, a very powerful tool from analytic combinatorics.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
unmarkierte Zufallsgraphen
de
dc.subject
Singularitätenanalyse
de
dc.subject
erzeugende Funktionen
de
dc.subject
Zyklenzeigersummen
de
dc.subject
Gradverteilung
de
dc.subject
Gradprofil
de
dc.subject
unlabelled random graphs
en
dc.subject
singularity analysis
en
dc.subject
generating functions
en
dc.subject
cycle index sums
en
dc.subject
degree distribution
en
dc.subject
degree profile
en
dc.title
Asymptotic study of families of unlabelled trees and other unlabelled graph structures
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Veronika Kraus
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Gittenberger, Bernhard
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC07810508
-
dc.description.numberOfPages
171
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-45174
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
doctoral thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie