Graph Theory
Aktuelles/News
- 13.10.2014: Webseiten online/web pages online
- 22.10.2014: First lecture
- 25.03.2015: 9:00 s.t. Exam in Building 082 – 00 -- 006
Inhalt/Contents
In diesem Jahr wird die Vorlesung auf Englisch durchgeführt. Sie ist inhaltsgleich mit der Vorlesung von 2013/2014. Für deutschsprachige Aufzeichnungen sei auf diese Veranstaltung verwiesen.
We present basics of graph theory for computer scientists.
- Definition
- Matching
- Connectivity
- Depth first search
- Coloring
- Flows in graphs
- Random graph
Organization
Vorlesung/Lecture
- Christian Schindelhauer
- Wednesday, 12:00 - 14:00 c.t., Hörsaal 101-00-036
Übungen/Exercises
Übungen finden wie unten im Zeitplan vermerkt statt. Übungsabgabe über das Websystem. Näheres dazu gibt es in der Vorlesung.
Exercises are organized as follows. For submissions please use the Web-system.
- Mittwoch/Wednesday 13-14 Uhr (1h) oder/or 12-14 Uhr (2h) Hörsaal 101-00-036, Christian Schönweiß
- Mittwoch/Wednesday 13-14 Uhr (1h) oder 12-14 Uhr (2h), Seminarraum 52-02-017, Felix Schiller
- Donnerstag/Thursday 9-10 Uhr (1h) oder 8-10 Uhr (2h) Seminarraum 101-01-009/13, Christian Schönweiß
- Donnerstag/Thursday 18-19 Uhr (1h) oder 18-20 Uhr (2h), Seminarraum 101-01-016, Felix Schiller
Zeitplan
| Datum | Vorlesungsstunden | Übungsstunden | Kapitel/Chapter | Aufzeichnung |
| 22.10.2014 | 2 | Introduction/directed graphs | mkv | |
| 29.10.2014 | 2 | undirected graphs/storing graphs/Line graphs | mkv | |
| 05.11.2014 | 1 | 1 | Paths, cycles | mkv |
| 12.11.2014 | 2 | Toplogocial sorting, Eulerian paths | mkv | |
| 19.11.2014 | 1 | 1 | Theorem of Euler | mkv |
| 26.11.2014 | 2 | Connectivity, Theorem of Euler, Trees | mkv | |
| 03.12.2014 | 2 | Euler, Line Graph, Hamiltonian | ||
| 10.12.2014 | 2 | DFS | mkv | |
| 17.12.2014 | 1 | 1 | MST | mkv |
| 07.01.2015 | 2 | Min-Max Flows | mkv | |
| 14.01.2015 | 1 | 1 | Matching | mkv |
| 21.01.2015 | 2 | Coloring | mkv | |
| 28.01.2015 | 1 | 1 | Chordal Graphs | mkv |
| 04.02.2015 | 2 | Random Graphs | mkv | |
| 11.02.2015 | 1 | 1 | Random Graphs | 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.
Please use the forum for discussion and further questions. No registration needed.
Material
Bei dieser Veranstaltung wird hauptsächlich die Tafel und nur ausnahmsweise Vorlesungsfolien verwendet. Die gesamte Veranstaltung wird aufgezeichnet und hier veröffentlicht.
The lecture is performed at the black board and slides are only used at times. The lecture will be recorded and published, here.
The lecture notes can be downloaded here (pdf).
Übungsblätter/Task sheets
Übungsblätter müssen über das Übungsportal abgegeben werden. Deadline ist der jeweilige Dienstag vor der Besprechung.
Please submit the task sheets using the web system. Submission deadline is Tuesday before the corresponding class.
- Übungsblatt/task sheet erschien am 29.10.2014
- Übungsblatt/task sheet erschien am 11.11.2014
- Übungsblatt/task sheet erschien am 26.11.2014
- Übungsblatt/task sheet erschien am 10.12.2014
- Übungsblatt/task sheet erschien am 07.01.2015
- Übungsblatt/task sheet erschien am 21.01.2015
- Übungsblatt/task sheet erschien am 04.02.2015
Tools
Um Graphen zu zeichnen kann das Tool yEd verwendet werden.
We recommend yEd for drawing graphs.
Prüfung/exam
Es findet eine schriftliche Prüfung statt. Die Prüfungsanmeldung erfolgt online. 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.
There will be a written exam. Do not forget to register online. Further prerequisites are not necessary. You are allowed to use your own solutions of the tasks in case you have submitted them using the web-system. Only reasonable submissions will be handed out, no program listings and no corrections of the tutors. If you have not participated in the peer-review system, the corresponding solution is not provided. In case of plagiarism we may withhold all material. Before the exam you will be allowed to have a look at the selection printed out for you.
Die zugeordneten Studiengänge und Prüfungsmodule sind im Vorlesungsverzeichnis aufgeführt.
Literatur(e)
- 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.
Further literature will be published during the lecture.