Uni-Logo
Sie sind hier: Startseite Lehre Frühere Veranstaltungen Universität Freiburg Vorlesung Graphentheorie (Sommer 2023)
Artikelaktionen

Vorlesung Graphentheorie (Sommer 2023)

Einführungsvorlesung in Graphentheorie für Bachelorstudenten der Informatik

News

  • 10.04.2023 Webseite online 
  • 10.04.2023 ILIAS-Seite online
  • 18.07.2023 Letzte Vorlesung, Besprechung der Evaluation

Inhalt

In dieser Bachelorvorlesung für Informatiker werden folgende Inhalte aus der Graphentheorie behandelt: 

  1. Zusammenhang
  2. Dominatoren
  3. BFS/DFS
  4. Minimaler Fluss/Maximaler Schnitt
  5. Gewichtetes Matching in bipartiten Graphen
  6. Graphfärbung
  7. Planare Graphen

Plan

  • Vorlesung Dienstag (2h): 16:15-18:00 101-00-026 
  • oder Dienstag  (1h): 16:15-17:00 101-00-026 an Übungstagen
Datum Vorlesung Übung  
18.04.2023 01: Organisation, Motivation & Ungerichtete Graphen (2h) -  
25.04.2023 02: Satz von König, Satz von Euler (2h) -  
02.05.2023 03: Gerichtete Graphen (1h) 01  
09.05.2023 04: Bäume, MST  (2h) -  
16.05.2023 05: Gerichtete Bäume, Dominatoren (1h) 02  
23.05.2023 06: BFS, DFS  (2h) -  
06.06.2023 07: Theorem von Berge und Hall (1h) 03  
13.06.2023 08: Min Flow Max Cut  (2h) -  
20.06.2023 09: Bipartite Matchings, Duale Probleme (1h) 04  
27.06.2023 10: Weighted Matching in Bipartite Graphs  (2h) -  
04.07.2023 11: Min-Cut/Max-Flow (1h) 05  
11.07.2023 12: Graph-Färbung und Planare Graphen  (2h) -  
18.07.2023 13: Kuratowskis Satz, Zusammenfassung und Ausblick (1h) 06  

Material

Übungsgruppen

  • Gruppe 1, Hans Albert, Dienstag 17-18 Uhr, 051-00-006, deutsch, Präsenz
  • Gruppe 2, Jürgen Mattheis, 17-18 Uhr, 051-00-034, deutsch, hybrid (BigBlueButton)
  • Gruppe 3, Matthias Herrmann, 17-18 Uhr, 101-00-026, deutsch, online (BigBlueButton)
  • Gruppe 4, Jürgen Mattheis, 18–19 Uhr, 051-00-034, englisch, hybrid (BigBlueButton)
  • Gruppe 5, Hans Albert, 18-19 Uhr, 051-00-006, deutsch, Präsenz
  • Gruppe 6, Matthias Herrmann, 18–19 Uhr, 051-00-031, deutsch, online  (BigBlueButton)

Übungsgruppen werden in den ersten beiden Vorlesungswochen nach der Präferenz hinsichtlich Sprache und Präsenz eingeteilt.

Prüfung

Die 90-minütige schriftliche  Prüfung findet am 8.09.2023 von 9:00-11:00 Uhr statt. Zusätzlich findet eine zweite ebenfalls schriftliche Prüfung für Studenten, die am 8.09.2023 verhindert sind am 26.07.2023 um 10 Uhr in Raum 051-02-007 statt. Melden Sie sich hierfür formlos im Forum dieser ILIAS-Seite im entsprechenden Thread an. Als Hilfsmittel außer Lebensmittel und Getränke ist ein eigenhändig beidseitig beschriebenes A4-Blatt zulässig. Versehen Sie es mit Ihren Namen und Matrikelnummer. Bitte melden Sie sich rechtzeitig elektronisch über das Campus-System an. 

Literatur

  • Introduction to Graph Theory, Second Edition, Douglas West, Prentice Hall 2002.
  • Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online)
  • Graph Theory, Reinhard Diestel, Electronic Edition 2010 pdf

 Weitere Literatur wird in der Veranstaltung angegeben.

 

 

Benutzerspezifische Werkzeuge