Uni-Logo
Sie sind hier: Startseite Lehre Frühere Veranstaltungen Universität Freiburg Graph Theory
Artikelaktionen

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.

  1. Definition
  2. Matching
  3. Connectivity
  4. Depth first search
  5. Coloring
  6. Flows in graphs
  7. 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

  1. Mittwoch/Wednesday 13-14 Uhr (1h) oder/or 12-14 Uhr (2h) Hörsaal 101-00-036, Christian Schönweiß
  2. Mittwoch/Wednesday 13-14 Uhr (1h) oder 12-14 Uhr (2h), Seminarraum 52-02-017, Felix Schiller
  3. Donnerstag/Thursday 9-10 Uhr (1h) oder 8-10 Uhr (2h) Seminarraum 101-01-009/13, Christian Schönweiß
  4. 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 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 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.

  1. Übungsblatt/task sheet erschien am 29.10.2014
  2. Übungsblatt/task sheet erschien am 11.11.2014
  3. Übungsblatt/task sheet erschien am 26.11.2014
  4. Übungsblatt/task sheet erschien am 10.12.2014
  5. Übungsblatt/task sheet erschien am 07.01.2015
  6. Übungsblatt/task sheet erschien am 21.01.2015
  7. Ü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.

Benutzerspezifische Werkzeuge