Prof. Dr. Achim Klenke
Institut für Mathematik
Fachbereich Physik, Mathematik und Informatik
Johannes Gutenberg-Universität
Staudingerweg 9
55099 Mainz
Tel. 06131 39-22829
Fax 06131 39-20916
E-Mail: 'math' dann 'at' und 'aklenke' gefolgt von einem Punkt und 'de'


Hauptseminar: Zufällige Spannbäume

Sommer 2011

Zeit: 

Fr 12-14

Ort:

Raum 05-522

Beginn:

06.05.2011

Besprechung: 

17.02.2011, 14ct, 05-136




Literatur


Inhalt. Ein Graph besteht aus Knoten und (ungerichteten) Kanten. Es solcher Graph heißt Wald, falls es keine Kreise gibt, und Baum, falls er zudem verbunden ist. Zu jedem verbundenen Graphen G lässt sich mindestens ein Baum finden, der die gleiche Knotenmenge besitzt und nur Kanten aus G verwendet. Solch ein Baum heißt Spannbaum von G. Ist G endlich, so kann man unter allen Spannbäumen nach der Gleichverteilung zufällig einen auswählen. Ist G unendlich, so gibt es eine kanonische Limesprozedur, die einen Spannwald liefert.

In diesem Hauptseminar werden die Eigenschaften von Spannbäumen endlicher Graphen mit verschiedenen Methoden untersucht. Es werden effiziente Algorithmen zur Erzeugung zufälliger Spannbäume diskutiert. Schließlich wird gezeigt, dass auf dem d-dimensionalen ganzzahligen Gitter der zufällige Spannwald genau dann ein Spannbaum ist, wenn d höchstens 4 ist.

 

Voraussetzung. Grundlagen der Stochastik (Stochastik 0) und Aufbaumodul Stochastik 1.

 

Ablauf.

14 Tage vor Vortrag: Einreichen des Vortragsmanuskripts

 10 Tage vor Vortrag: Vorbesprechung, Dienstag, 13 Uhr.