Graph Theory
(Graphentheorie I)

Bachelor, 4.Semester

Veranstalter:

Reinhard Diestel

Inhalt:

Leitprobleme und grundlegende Sätze der Graphentheorie.

Die Graphentheorie ist eines der jüngsten und zugänglichsten Gebiete der Mathematik. Ohne, wie in den klassischen Disziplinen oft unumgänglich, zunächst ein umfassendes Instrumentarium an Begriffsapparat und Techniken beherrschen lernen zu müssen, begegnet man hier vom ersten Tag an mathematischen Problemen, die man im Prinzip ohne weitere Voraussetzungen selbst bearbeiten könnte. Hierzu soll die Vorlesung einerseits den ordnend-motivierenden Rahmen darstellen und andererseits anhand besonders schöner Beweise inspirieren.

Charakter:

Die Vorlesung folgt zwar keinem Buch – aber es gibt ein Buch, das dieser Vorlesung folgt. Dort ist der netto-Vorlesungsstoff (Definitionen, Aussagen, Beweise) vollständig zu finden, so dass in der Vorlesung niemand diesen Grundstoff mitschreiben muss und sich auf den dort gebotenen Mehrwert konzentrieren kann: woher die Begriffe kommen, welchem Ziel sie dienen, welche Ideen den Beweisen zugrundeliegen – und welche scheinbar offensichtlicheren Ideen nicht funktionieren, und weshalb nicht.

Dieser auf Ideen fokussierte Charakter der Vorlesung macht sie vielleicht etwas anspruchsvoller als sie es bei häppchenweiser Stoffvermittlung wäre, die sich auf das Lernen und Nachvollzie-hen des Stoffes beschränkte (was natürlich auch erwartet wird). Aber – so hoffe ich – auch interessanter für alle, die sich darauf einlassen, richtig mitzumachen.

Übungen:

Zur Vorlesung gibt es Übungen, die durchaus über den Vorlesungsstoff hinausgehen können und eine Spielwiese für eigene Beweisversuche bieten.

Vorkenntnisse:

Die Vorlesung wendet sich typischerweise an Hörer im 4. Semester, setzt aber nur Grundbegriffe aus dem 1. Semester voraus. Wichtig jedoch ist ein in der Anfängerausbildung gewachsener Mut zum Mitdenken in Echtzeit, während der Vorlesung ebenso wie in den Übungen.

Vorherige oder gleichzeitige Teilnahme an der Vorlesung "Diskrete Mathematik" ist nicht Voraussetzung. Jene Vorlesung ist als Alternative zur Graphentheorie
gedacht, mit eher einführendem und angewandterem Charakter.

Sprache:

Die Vorlesung wird englisch gehalten, die Übungen deutsch oder englisch nach Bedarf.

Literatur:

R.Diestel, Graph Theory (5th ed'n), GTM 173, Springer 2017
(R.Diestel, Graphentheorie (5. Auflage), Springer 2017)

Die deutsche Auflage ist eine Übersetzung großer Teile der englischen und deckt den Stoff dieser Vorlesung ab. Die englische Ausgabe enthält zusätzlich ein Kapitel über unendliche Graphen, das Gegenstand einer Master-Vorlesung und in der deutschen Ausgabe nicht enthalten ist.

Zusatzmaterial:

Grundlegende Begriffe für die erste Vorlesungswoche.
(Kaufen Sie sich das Buch erstmal nicht; zu den verschiedenen Möglichkeiten dafür sage ich in der ersten Vorlesung mehr.)

Übungsblätter:

Übung 1
Übung 2
Übung 3
Übung 4
Übung 5
Übung 6
Übung 7
Übung 8
Übung 9
Übung 10
Übung 11
Übung 12
Übung 13

Die Übungen werden in der Regel am Dienstag um 14 Uhr veröffentlicht. Ihre Lösung der schriftlichen Aufgabe geben Sie bitte am Anfang Ihrer jeweiligen Übungsgruppe ab. Bei Bedarf können Sie auch per Mail abgeben. Sprechen Sie dazu Sandra Albrechtsen oder Paul Knappe an. Bringen Sie Ihre Lösungen der mündlichen Aufgaben präsentierbereit zur Übung mit. Vorort geben Sie an, welche Aufgaben Sie bearbeitet haben. Dies bringt ihnen die unten beschriebenen Punkte. Weiter wählen wir darauf basierend aus, wer welche Lösung vorträgt.


Deutsch-englisches Glossar

Prüfungen:

Die Prüfung zur Vorlesung ist formal kategorisiert als mündlich. Sie enthält jedoch einen schriftlichen vorbereitenden Teil. Beide Teile werden an aufeinanderfolgenden Tagen Anfang Oktober 2024 stattfinden, damit Sie über die Sommermonate genug Zeit zur Vorbereitung haben.

Prüfungsstoff: die Abschnitte, die im Inhaltsverzeichnes der englischen Ausgabe des Buchs ein Sternchen haben. Ausnahmen und Zusatzmaterial werden ggf. in der Vorlesung angegeben.

Bewertung der Übungsleistung: Erforderlich für das Bestehen der Übung, und damit für die Zulassung zur Modulprüfung, ist das Erreichen von jeweils 50% der in den mündlichen Aufgaben und der in den schriftlichen Aufgaben erreichbaren Punkte. Die schriftlichen Aufgaben werden zwar auch mündlich besprochen, doch geht dies nicht in die Bewertung ein.

Bewertungskriterien der schriftlichen Aufgaben
  • Eine schriftliche Aufgabe ist drei Punkte wert.
  • Für eine sinnvolle Bearbeitung oder eine sinnvolle schriftliche Erklärung, woran man beim Lösen der Aufgabe gescheitert ist, gibt es einen Punkt.
  • Ist die Aufgabe richtig gelöst, gibt es zwei weitere Punkte.
Bewertungskriterien der mündlichen Aufgaben
  • Eine Minusaufgabe ist einen Punkt wert.
  • Eine normale Aufgabe ist zwei Punkte wert.