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)
- 25.09.2020: 1. Klausur in Gebäude 101, Einlass um 7:45. Räume 00-026, 00-036, 00-010/14, 01-009/13
Bitte beachten Sie die Hinweise im ILIAS-Forum! Bringen Sie die Corona-Erklärung unterschrieben zur Klausur mit! - Klausureinsichten nur auf Anfrage und nach Absprache eines Termins!
Inhalt
In dieser Vorlesung wird Graphentheorie für Bachelor-Studenten der Informatik behandelt. Unter anderem werden folgende Themen gelehrt:
- Grundlagen
- Speicherung
- Kreisfreie Graphen
- Topologische Sortierung
- Zusammenhang
- Eulersche/Hamiltonsche Graphen
- Bäume und Wälder
- Breiten/Tiefensuche
- Minimale Spannbäume
- Flüsse und Schnitte
- Matching
- Knotenüberdeckung
- Färbungen
- Cliquen
- Chordale und Perfekte Graphen
- 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. Die Mindestzahl von 30% der Übungspunkte 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.