Willkommen zur Webseite der Vorlesung
Graphen- und Zufallsgraphentheorie
im Sommersemester 2015 bei Prof. Dr. Konstantinos Panagiotou
Termine Literatur Übungen und Material Prüfung
Inhalt
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, die Verbindungen zwischen den Knoten beschreiben. Mit Hilfe dieser einfachen mathematischen Objekte lassen sich viele fundamentale Probleme formulieren, z.B.
- Wie legt man möglichst optimal die Ankunfts- und Abflugzeiten aller Flugverbindungen in Deutschland fest?
- Wie findet man den schnellsten Weg von München nach Paris?
- Wie plant man eine Rundreise durch USA, so dass die zurückgelegte Strecke so kurz wie möglich ist?
Ziel der Vorlesung ist es, einen vertiefenden Einblick in vielen Aspekten der Theorie der Graphen zu geben. Dabei werden Graphen
- als diskrete kombinatorische Objekte betrachtet, und ihre strukturellen Eigenschaften werden analysiert.
- als Eingabe für verschiedene Optimierungsprobleme verwendet, und algorithmische Lösungen diskutiert.
- als zufällige Objekte betrachtet, und Aussagen über die typisch entstehenden Strukturen gemacht.
Termine
Vorlesungsbeginn: Di 14.04.2015, Besprechung des ersten Übungsblattes: 24.4.2015
| Do 14-16 Uhr |
|
|
| |
|
|
| |
|
Die Vorlesung und die Übungen beginnen um Punkt 14:00.
Sprechstunden: bitte per Email vereinbaren!
Literatur
Empfehlenswerte Bücher sind z.B.
- Reinhard Diestel - Graphentheorie
- Svante Janson, Tomasz Luczak, Andrzej Rucinski - Random Graphs
- Remco van der Hofstad - Random Graphs and Complex Networks
Eine gute Einführung in die Theorie der Zufallsgraphen findet sich
hier. Die Vorlesung basiert auf diese Notizen.
Diese Liste wird im Laufe der Vorlesung um geeignete Referenzen erweitert werden.
Übungen und Material
Eine inoffizielle Mitschrift wird von Herrn Moritz Karl erstellt und ist hier verfügbar (zulezt aktualisiert: 19.06.). Herzlichen Dank dafür!
Übungsblätter
| | | |
|---|---|---|
Zusätzliches Material
- Kantenkontraktion (28.04.)
Prüfung
Die Ergebnisse der Nachklausur (für alle, die ein Pseudonym angegeben haben) finden Sie hier.