Graphentheorie
Sommersemester 2021
Fabian Kuhn

 

Inhalt

In dieser Vorlesung für Bachelorstudenten der Informatik werden die Grundlagen der Graphentheorie gelehrt. Dazu gehören die mathematische Definition von gerichteten und ungerichteten Graphen, Adjazenzmatritzen und andere Repräsentationsmöglichkeiten, Bäume und Wälder, topologische Sortierungungen, Zusammenhangskomponenten, eulersche/hamiltonsche Wege und Kreise, Tiefen-/Breitensuche, Spannbäume, Flüsse, Schnitte, Matchings, Knotenüberdeckungen, Färbungen, Cliquen sowie chordale und perfekte Graphen.

Ablauf der Vorlesungen

Am 20.04.21 um 16:15 Uhr wird es eine Einführungsveranstaltung via Zoom geben. Die Zugangsdaten dafür finden Sie im nächsten Abschnitt.

Die Vorlesungen wurden im Voraus aufgezeichnet und sind unter folgendem Link zu erreichen.

Vorlesungsaufzeichnungen und -folien (+ Altklausur)

Es wird zudem jede zweite Woche eine interaktive Fragestunde geben. Der Termin ist immer Dienstags um 16:15.

Für Fragen zur Vorlesung und den Übungen wird ein Forum auf Zulip eingerichtet.

Zugangsdaten

Die notwendigen Daten für die Zoom-Meetings und das Forum finden Sie auf dieser Website. Bitte beachten Sie dass dieser Link nur innerhalb des Uni-Netzwerkes funtkioniert. Möchten Sie von ausserhalb zugreifen, können Sie einen VPN Tunnel benutzen.

Übungen

Die Übungen werden online mit dem Kursverwaltungssystem Daphne durchgeführt.

Hinweis: Abgabe der Übungsbätter ist stets um 16:00 Uhr!

Es gibt zur Vorlesung keine Studienleistung. Die Abgabe der Übungsblätter ist deshalb fakultativ.

Richtlinien zur Abgabe der Übungsblätter

Eine gemeinsame Abgabe in Gruppen von bis zu drei Personen ist erlaubt. Um eine Übungsgruppe zu bilden, senden Sie bitte eine Mail an Philipp Bamberger, welche die RZ-Kürzel der Gruppenmitglieder enth?lt. Bitte beachten Sie, dass jedes Gruppenmitglied die Lösungen in seinen SVN-Ordner laden muss. Bitte teilen Sie zudem Ihrem Tutor Ihre Gruppenpartner mit.

Laden sie Ihre Lösungen als (einzelnes) PDF in Ihr SVN Repository in einen Unterordner mit dem Namen uebungsblatt-XY wobei XY die aktuelle Nummer des Übungsblattes angibt (mit führender Null falls die Nummer einstellig ist). Am liebsten sind uns Lösungen, die mit Latex angefertigt wurden. Word oder andere Zeichensetzungsprogramme sind ok, Scans müssen gut lesbar sein.

Klausur

Hauptklausur

• Datum: Die Klausur findet am 24.09 statt.
• Uhrzeit: Klausurbeginn ist um 9 Uhr mit Einlass ab ca. 8.45 Uhr. Wir bitten Sie darum um 8.45 Uhr anwesend zu sein denn der Einlass muss geordnet durchgeführt werden und könnte etwas mehr Zeit in Anspruch nehmen.
• Dauer: 90 Minuten.
• Ort: Die großen Hörsäle (101-00-026 und 101-00-036) im 101 .
• Modus: Schriftlich. Hilfsmittel sind nicht erlaubt!
• Maßnahmen bzgl. COVID-19: Der Raum soll der Reihe nach mit 1,5m Mindestabstand zwischen Personen betreten werden. Sitzreihen sollen von hinten nach vorne aufgefüllt werden. Beim Einlass und Rausgehen besteht Maskenpflicht. Zusätzlich gilt die 3G Regelung (alle Teilnehmer müssen einen aktuellen Test, eine vollständige Impfung oder Genesung nachweisen können).

Einsicht

• Eine Klausureinsicht wird am 05.11. von 16 bis 17 Uhr im Seminarraum 106-00-007 angeboten. Es gilt die 3G-Regel.

Einsicht Nachklausur

• Die Klausureinsicht der Nachklausur wird am 07.04. von 14 bis 15 Uhr im Seminarraum 106-00-007 angeboten.

Verantwortliche

Lehrmaterial

• Graphentheoretische Konzepte und Algorithmen, Sven Oliver Krumke und Hartmut Noltemeier. Springer 2012. (Online, innerhalb des Uni-Netzwerks erreichbar)
• Graph Theory, Reinhard Diestel, Electronic Edition 2010 (Online)