Graphentheorie
Aktuelles
- 13.10.2015: Webseiten online
- 23.10.2015: 1. Vorlesung
- 18.03.2016: 1. Klausur
- 13.04.2016: Klausureinsicht um 10:00 in Gebäude 51, Raum 02-007 (geändert)
- 27.09.2016: 2. Klausur
- 19.10.2016: Klausureinsicht um 17:00 in Raum 02-035, Gebäude 51
Inhalt
In dieser Vorlesung werden Grundlagen der Graphentheorie für Bachelor-Studenten der Informatik behandelt.
- Grundlagen
- Matching
- Zusammenhang
- Planare Graphen
- Färbbarkeit
- Flüsse in Graphen
- Zufallsgraphen
Organisation
Vorlesung
- Sven Köhler
- Freitags, 14:00 - 16:00 c.t., Hörsaal 101-00-036
Übungen
Übungen finden wie unten im Zeitplan vermerkt statt. Übungsabgabe über das Websystem. Näheres dazu gibt es in der Vorlesung.
- Freitag 15-16 Uhr (1h) oder 14-16 Uhr (2h) Seminarraum 101-01-018, Felix Schiller
- Montag 13-14 Uhr (1h) oder 12-14 Uhr (2h), Seminarraum 101-01-016, Felix Schiller
Zeitplan
| Datum | Vorlesungsstunden | Übungsstunden | Kapitel | Aufzeichnung |
| 23.10.2015 | 2 | Einführung | ||
| 30.10.2015 | 2 | Einführung | ||
| 06.11.2015 | 1 | 1 | Speicherung | |
| 13.11.2015 | 2 | Matching | ||
| 20.11.2015 | 1 | 1 | Wege, Kreise, Erreichbarkeit, Topologische Sortierung | |
| 27.11.2015 | 2 | Zusammenhang, Satz von Euler | ||
| 04.12.2015 | 1 | 1 | Hamiltonsche Graphen, Graphfärbung | |
| 11.12.2015 | 2 | Graphfärbung, chrodale und perfekte Graphen | ||
| 18.12.2015 | 0 | 2 | ||
| 08.01.2016 | 2 | Bäume, Tiefensuche | ||
| 15.01.2016 | 1 | 1 | Tiefensuche | |
| 22.01.2016 | 2 | Maximaler Fluss, Minimaler Schnitt | ||
| 29.01.2016 | 1 | 1 | Kruskal | |
| 05.02.2016 | 2 | Prim Boruvka, Zufallsgraphen | ||
| 12.02.2016 | 1 | 1 | Zufallsgraphen |
Forum
Zu der Vorlesung ist ein Forum eingerichtet, in dem inhaltliche und organisatorische Fragen diskutiert werden können. Eine Registrierung dafür ist nicht notwendig.
Material
Bei dieser Veranstaltung wird hauptsächlich die Tafel und nur ausnahmsweise Vorlesungsfolien verwendet. Aufzeichnungen der Vorlesung sind aus den Vorjahren 2013 (Deutsch) und 2014 (Englisch) verfügbar.
Algorithmen 3.4 und 3.5 aus der Vorlesung vom 27.11.2015 gibt es hier zum Download. Diese stammen aus dem Buch von Krumke und Noltemeier, wurden aber leicht abgeändert.
Übungsblätter
Übungsblätter müssen über das Übungsportal abgegeben werden. Deadline ist der jeweilige Dienstag vor der Besprechung.
- Übungsblatt erschienen am 30.10.2015
- Übungsblatt erschienen am 13.11.2015
- Übungsblatt erschienen am 27.11.2015
- Übungsblatt erschienen am 11.12.2015
- Übungsblatt erschienen am 8.1.2016
- Übungsblatt erschienen am 22.1.2016
- Übungsblatt erschienen am 5.2.2016
Tools
Um Graphen zu zeichnen kann das Tool yEd Graph Editor verwendet werden. Falls Sie Ihre Abgaben mit LaTeX schreiben empfehlen wir das tikz Paket.
Prüfung
Die schriftliche Prüfung findet am 18.03.2016 um 9 Uhr s.t. im Hörsaal 101-00-026, statt . Die Prüfungsanmeldung erfolgt online über das HIS. Weitere Zulassungsvoraussetzungen gibt es nicht. Beachten Sie die Fristen! Außer Schreibzeug sind keine Hilfsmittel mitzubringen. Es wird aber eine Auswahl der eigenen Übungslösungen am Platz bereitgestellt. Hierbei werden nur sinnvolle Abgabe berücksichtigt ohne Programmausdrucke und ohne Korrekturen der Tutoren. Wenn keine Teilnahme am Peer-Review-Verfahren stattfand wird die entsprechende Übungslösung ebenso nicht berücksichtigt. Im Falle von Plagiaten bei der Übungsabgabe behalten wir uns vor überhaupt kein Material bereit zu stellen. Vor der Klausur erhalten Sie die Möglichkeit die Auswahl einzusehen.
Die zugeordneten Studiengänge und Prüfungsmodule sind im Vorlesungsverzeichnis aufgeführt.
Literatur
- Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online nur innerhalb des Uni-Netzes)
- Graph Theory, Reinhard Diestel, Electronic Edition 2010 pdf
Weitere Literaturhinweise werden hier im Verlauf der Veranstaltung veröffentlicht.