edoc-Server der Humboldt-Universität zu Berlin

Habilitationsschrift

Autor(en): Mihyun Kang
Titel: Random planar structures and random graph processes
Gutachter: Günter M. Ziegler; Hans Jürgen Prömel; Michal Karonski
Erscheinungsdatum: 27.07.2007
Volltext: pdf (urn:nbn:de:kobv:11-10079034)
Fachgebiet(e): Informatik
Schlagwörter (ger): planare Graphen, zufällige Graphen, rekursive Methode, Singularitätenanalyse, probabilistische Methoden
Schlagwörter (eng): planar graphs, random graphs, recursive method, singularity analysis, probabilistic methods
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Kang, Mihyun: Random planar structures and random graph processes; Habilitationsschrift, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 27.07.2007, urn:nbn:de:kobv:11-10079034
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.

Abstract (ger):
Diese Habilitationsschrift richtete auf zwei diskrete Strukturen aus: planare Strukturen und zufällige Graphen-Prozesse. Zunächst werden zufällige planare Strukturen untersucht, mit folgende Gesichtspunkte: - Wieviele planare Strukturen gibt es? - Wie kann effizient eine zufällige planare Struktur gleichverteilt erzeugt werden? - Welche asymptotischen Eigenschaften hat eine zufällige planare Struktur mit hoher Wahrscheinlichkeit? Um diese Fragen zu beantworten, werden die planaren Strukturen in Teile mit höherer Konnektivität zerlegt. Für die asymptotische Enumeration wird zuerst die Zerlegung als das Gleichungssystem der generierenden Funktionen interpretiert. Auf dem Gleichungssystem wird dann Singularitätenanalyse angewendet. Für die exakte Enumeration und zufällige Erzeugung wird die rekursive Methode verwendet. Für die typischen Eigenschaften wird die probabilistische Methode auf asymptotischer Anzahl angewendet. Des Weiteren werden zufällige Graphen-Prozesse untersucht. Zufällige Graphen wurden zuerst von Erdos und Renyi eingeführt und untersucht weitgehend seitdem. Ein zufälliger Graphen-Prozess ist eine Markov-Kette, deren Zustandsraum eine Menge der Graphen mit einer gegebenen Knotenmenge ist. Der Prozess fängt mit isolierten Konten an, und in jedem Ablaufschritt entsteht ein neuer Graph aus dem aktuellen Graphen durch das Hinzufügen einer neuen Kante entsprechend einer vorgeschriebenen Regel. Typische Fragen sind: - Wie ändert sich die Wahrscheinlichkeit, dass ein von einem zufälligen Graphen-Prozess erzeugter Graph zusammenhängend ist? - Wann erfolgt der Phasenübergang? - Wie groß ist die größte Komponente? In dieser Habilitationsschrift werden diese Fragen über zufällige Graphen-Prozesse mit Gradbeschränkungen beantwortet. Dafür werden probabilistische Methoden, insbesondere Differentialgleichungsmethode, Verzweigungsprozesse, Singularitätsanalyse und Fourier-Transformationen, angewendet.
Abstract (eng):
This thesis focuses on two kinds of discrete structures: planar structures, such as planar graphs and subclasses of them, and random graphs, particularly graphs generated by random processes. We study first planar structures from the following aspects. - How many of them are there (exactly or asymptotically)? - How can we efficiently sample a random instance uniformly at random? - What properties does a random planar structure have, with high probability? To answer these questions we decompose the planar structures along the connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating functions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the recursive method. For typical properties of random planar structures we use the probabilistic method, together with the asymptotic numbers. Next we study random graph processes. Random graphs were first introduced by Erdos and Renyi and studied extensively since. A random graph process is a Markov chain whose stages are graphs on a given vertex set. It starts with an empty graph, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. Recently random graph processes with degree restrictions received much attention. In the thesis, we study random graph processes where the minimum degree grows quite quickly with the following questions in mind: - How does the connectedness of a graph generated by a random graph process change as the number of edges increases? - When does the phase transition occur? - How big is the largest component? To investigate the random graph processes we use the probabilistic method, Wormald''s differential equation method, multi-type branching processes, and the singularity analysis.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 2 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 2 Zugriffe PDF: 4 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe PDF: 2 Zugriffe Startseite: 4 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 1 Zugriffe Startseite: 1 Zugriffe PDF: 2 Zugriffe Startseite: 3 Zugriffe PDF: 10 Zugriffe Startseite: 3 Zugriffe PDF: 8 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 5 Zugriffe Startseite: 1 Zugriffe PDF: 9 Zugriffe Startseite: 3 Zugriffe PDF: 8 Zugriffe Startseite: 5 Zugriffe PDF: 4 Zugriffe Startseite: 1 Zugriffe PDF: 16 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 6 Zugriffe PDF: 22 Zugriffe PDF: 18 Zugriffe Startseite: 1 Zugriffe PDF: 27 Zugriffe PDF: 10 Zugriffe Startseite: 2 Zugriffe PDF: 20 Zugriffe PDF: 6 Zugriffe PDF: 20 Zugriffe Startseite: 2 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 16 Zugriffe Startseite: 1 Zugriffe PDF: 19 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe PDF: 17 Zugriffe PDF: 21 Zugriffe Startseite: 1 Zugriffe PDF: 23 Zugriffe Startseite: 3 Zugriffe PDF: 33 Zugriffe PDF: 32 Zugriffe Startseite: 4 Zugriffe PDF: 32 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe Startseite: 4 Zugriffe PDF: 26 Zugriffe Startseite: 1 Zugriffe PDF: 38 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Jan
12
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Jan
12
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Startseite 2 1 2 2 1   4 2 1 3 3 2 1 1 3 5 1 2 6   1   2     2 2 1 1     1 3   4 1 4 1
PDF 10 2 6 4 6 2 7 1 2 10 8 10 5 9 8 4 16 14 22 18 27 10 20 6 20 35 16 19 14 17 21 23 33 32 32 14 26 38

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 65 (1.67 pro Monat)
  • PDF – 567 (14.54 pro Monat)
 
 
Generiert am 23.11.2014, 05:40:20