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. / 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.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/14625 |
| Date | 27 July 2007 |
| Creators | Kang, Mihyun |
| Contributors | Ziegler, Günter M., Prömel, Hans Jürgen, Karonski, Michal |
| Publisher | Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Source Sets | Humboldt University of Berlin |
| Language | English |
| Detected Language | English |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/pdf |
Page generated in 0.0029 seconds