Uni-Logo
You are here: Home Lehre Frühere Veranstaltungen Universität Freiburg Graphentheorie WS15
Document Actions

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.

  1. Grundlagen
  2. Matching
  3. Zusammenhang
  4. Planare Graphen
  5. Färbbarkeit
  6. Flüsse in Graphen
  7. 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.

  1. Freitag 15-16 Uhr (1h) oder 14-16 Uhr (2h) Seminarraum 101-01-018, Felix Schiller 
  2. 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.

  1. Übungsblatt erschienen am 30.10.2015
  2. Übungsblatt erschienen am 13.11.2015
  3. Übungsblatt erschienen am 27.11.2015
  4. Übungsblatt erschienen am 11.12.2015
  5. Übungsblatt erschienen am 8.1.2016
  6. Übungsblatt erschienen am 22.1.2016
  7. Ü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.

Personal tools