Uni-Logo
You are here: Home Lehre Aktuelle Lehre Graphentheorie (Sommer 2020)
Document Actions

Graphentheorie (Sommer 2020)

Aktuelles

  • 27.04.2020: Webseiten online
  • 28.04.2020: Bereitstellung ILIAS-Link
  • 11.05.2020: Allgemeiner Vorlesungsbeginn
  • 12.05.2020: Erste Vorlesungsvideos online
  • 12.05.2020: Erste Fragerunde (nur zum Organisatorischen, Beitritt über ILIAS)

Inhalt

In dieser Vorlesung wird Graphentheorie für Bachelor-Studenten der Informatik behandelt. Unter anderem werden folgende Themen gelehrt:

  1. Grundlagen
  2. Speicherung
  3. Kreisfreie Graphen
  4. Topologische Sortierung
  5. Zusammenhang
  6. Eulersche/Hamiltonsche Graphen
  7. Bäume und Wälder
  8. Breiten/Tiefensuche
  9. Minimale Spannbäume
  10. Flüsse und Schnitte
  11. Matching
  12. Knotenüberdeckung
  13. Färbungen
  14. Cliquen
  15. Chordale und Perfekte Graphen
  16. Zufallsgraphen und die Propabilistische Methode

Corona

Wegen der anhaltenden Corona-Pandemie wird die Lehre im Sommersemester 2020 bis auf Weiteres online stattfinden. Statt einer Vorlesung im Hörsaal werden Videos produziert und hier veröffentlicht. Zu dem Termin der Vorlesung wird es eine Online-Konferenz geben, bei der die Studierenden Fragen zu den Themen aus den Videos der Vorwoche stellen können (inverted classroom). Die Videos werden alle 2 Wochen 135 Minuten Vorlesung abdecken.

Auch die Übungen werden per Online-Konferenz stattfinden. Es gibt also keine Präsenzübungen. Die Übungszettel werden aber bepunktet und eine Mindestzahl von Übungspunkten wird Voraussetzung für die Klausur sein.

Organisation

Vorlesung

  • Wöchendlich Montags: Veröffentlichung der Vorlesungs-Videos 
  • Wöchentlich Dienstags, ab 16:15: Fragerunde zu den Vorlesungsthemen der Vorwoche 
  • Die Vorlesungsvideos und -folien finden Sie im ILIAS-System
  • Dozent: Dr. Sven Köhler

Übungen

Alle zwei Wochen finden die Übungen statt. Es gibt 7 Übungsgruppen. Die Termine sind:

  • Gruppe 1: Dienstags 17-18 Uhr (Ming-Yi Hu)
  • Gruppe 2: Dienstags 17-18 Uhr (Florian Probst)
  • Gruppe 3: Dienstags 17-18 Uhr (Max Nazarati)
  • Gruppe 4: Dienstags 17-18 Uhr (Margarita Zhdanovich)
  • Gruppe 5: Dienstags 18-19 Uhr (Ming-Yi Hu)
  • Gruppe 6: Dienstags 18-19 Uhr (Florian Probst)
  • Gruppe 7: Dienstags 18-19 Uhr (Max Nazarati)


Im ILIAS ist für jede Gruppe eine BigBlueButton eine separate Videokonferenz angelegt. Gehen Sie im ILIAS zu den Übungsgruppen und klicken Sie dort auf Ihre Gruppe um zur Videokonferenz zu gelangen.

Die Übungsblätter werden über das ILIAS-System veröffentlicht.

Blatt Übung Kapitel
1 26.5. 01,02,03
2 9.6.  
3 23.6.  
4 7.7.  
5 21.7.  
6 28.7.  

 

Forum

Ein Forum für Fragen und Diskussion wird im ILIAS eingerichtet.

Material

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

Es wird eine schriftliche Prüfung mit einer Dauer von 90 Minuten geben. Die Prüfungsanmeldung erfolgt online über das Online-System. Eine Mindestzahl an Übungspunkten ist Voraussetzung für die Teilnahme an der Klausur. Außer Schreibzeug sind keine Hilfsmittel erlaubt.

Über den Übungsabgaben vermeiden Sie copy&paste von Inhalten aus der Vorlesung sowie Plagiate von Kommilitonen. Im Falle von Plagiaten bei der Übungsabgabe behalten wir uns vor Sie von der Klausur auszuschließen.

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 im Verlauf der Veranstaltung veröffentlicht.

Personal tools