Willkommen zur Webseite der Vorlesung
Graphen- und Zufallsgraphentheorie
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?
- 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 |
|
|
| |
|
|
| |
|
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
Ü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.)