Graphentheorie
Aktuelles
- 07.10.2013: Webseiten online
- 23.10.2013: 1. Vorlesung
- 05.11.2013: Wegen Serverproblemen stellen wir alles Material auch über BitTorrent Sync zur Verfügung. Secret: BTDRLQFTNNFVMXTO53SOGYE5AEBZ5TBI3
- 06.11.2013: Übungsgruppenräume korrigiert
- 16.12.2013: Websystem läuft auf neuer Domain und neuem Zertifikat
- 30.01.2014: Beginn der Lehrevaluation!
- 26.02.2014: Es gibt eine Probeklausur zum selbst Üben
- 08.04.2014: Die Klausureinsicht findet um 10 Uhr im Raum 51-02-07 statt!
- 29.08.2014: Die Nachklausur findet um 9 Uhr im Raum 101-00-010/014 statt!
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
- Christian Schindelhauer
- Mittwoch, 14:00 - 16:00 c.t., Seminarraum 101-01-009/013
Übungen
Übungen finden wie unten im Zeitplan vermerkt statt. Übungsabgabe über das Websystem. Näheres dazu gibt es in der Vorlesung.
- Mittwoch 15-16 Uhr (1h) oder 14-16 Uhr (2h) Seminarraum 51-03-026, Thomas Janson
- Mittwoch 15-16 Uhr (1h) oder 14-16 Uhr (2h), Seminarraum 101-01-009/013, Christian Ortolf
- Donnerstag 9-10 Uhr (1h) oder 8-10 Uhr (2h) Seminarraum 78-00-014, Thomas Janson
- Donnerstag 14-15 Uhr (1h) oder 14-16 Uhr (2h), Seminarraum 101-01-016, Christian Ortolf
Zeitplan
| Datum | Vorlesungsstunden | Übungsstunden | Kapitel | Aufzeichnung |
| 23.10.2013 | 2 | Einführung | mp4 | |
| 30.10.2013 | 2 | Einführung | Teil1 Teil2 | |
| 06.11.2013 | 1 | 1 | Speicherung | mkv |
| 13.11.2013 | 2 | Matching | mkv | |
| 20.11.2013 | 2 | Wege, Kreise, Zusammenhang Topologische Sortierung, Eulerscher Weg |
mkv | |
| 27.11.2013 | 2 | Zusammenhang | ||
| 04.12.2013 | 2 | Satz von Euler, Hamiltonsche Graphen, Graphfärbung | Teil1 Teil2 | |
| 11.12.2013 | 2 | Graphfärbung | Teil1 Teil2 | |
| 18.12.2013 | 2 | Bäume, Tiefensuche | ||
| 08.01.2014 | 2 | Tiefensuche | Teil1 Teil2 | |
| 15.01.2014 | 1 | 1 | Flüsse | mkv |
| 22.01.2014 | 2 | Das Flussproblem | Teil1 Teil2 | |
| 29.01.2014 | 2 | Flüsse | ||
| 05.02.2014 | 2 | Zufallsgraphen | Teil1 Teil2 | |
| 12.02.2014 | 1 | 1 | Zufallsgraphen | mkv |
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. Die gesamte Veranstaltung wird aufgezeichnet und hier veröffentlicht.
Übungsblätter
Übungsblätter müssen über das Übungsportal abgegeben werden. Deadline ist der jeweilige Dienstag vor der Besprechung.
- Übungsblatt erschien am 30.10.2013
- Übungsblatt erschien am 20.11.2013
- Übungsblatt erschien am 11.12.2013
- Übungsblatt erschien am 08.01.2014
- Übungsblatt erschien am 22.01.2014
- Übungsblatt erschien am 05.02.2014
Tools
Um Graphen zu zeichnen kann das Tool yEd verwendet werden.
Prüfung
Die schriftliche Prüfung findet am 25.03.2014 um 9 Uhr s.t. im Kinohörsaal, Gebäude 82 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.