Reinhard Diestel

Prüfungsinhalte Graphentheorie


Alle Angaben beziehen sich, soweit nicht anders angegeben, auf die Abschnittsnumerierung meines Buchs Graphentheorie in der vierten deutschen Auflage. Die Inhalte unten sind nur Vorschläge; Änderungen sind nach Absprache jederzeit möglich. Die SWSAngaben beziehen sich auf die reine Vorlesung, ohne Übungen.

Graphentheorie 1 (Bachelor, 4SWS)

Grundbegriffe: Kap. 0.1-8

Paarungen: Kap. 1.1 (nur zwei Beweise des Heiratssatzes), Satz. 1.2.1, Kap. 1.5

Zusammenhang: Kap. 2.1.1, 2.1.4; Kap. 2.2: beide Sätze zur Konstruktion 3-zh'er Graphen, die Kontraktionsvariante mit Beweis; Kap. 2.3: Satz von Menger mit ersten zwei Beweisen

Graphen in der Ebene: Kap. 3.1-2 und 3.4

Färbungen: Kap. 4.1-4

Flüsse: Kap. 5.2, sowie die dazu notwendigen Definitionen aus 5.1

Extremale Graphentheorie: Kap. 6.1 und 6.3. Satz 6.2.2, Lemma 2.5.1 und Übung 6.19+. Aussagen (ohne Beweise) von 6.2.1 und 6.2.3.

Unendliche Graphentheorie (englische Ausgabe): Chapters 8.1, 8.2.1, 8.3, 8.4.1

Ramseytheorie: Kap. 7.1-2 (außer 7.2.2) und 7.4

Hamiltonkreise: Kap. 8.1-2

Zufallsgraphen: Kap. 9

Beispiele typischer Prüfungsfragen finden sich hier.


Graphentheorie 2 (Master, 4SWS)

Alle Inhalte der englischen aktuellen Ausgabe des Buchs, die nicht in Graphentheorie 1 bereits abgedeckt sind, außer Kapitel 8 (Unendliche Graphen) und in der Vorlesung ggf. ausgelassenem Stoff.

Die englische Ausgabe geht, abgesehen vom Kapitel über unendliche Graphen, nur im Minorenkapitel wesentlich über die deutsche hinaus.


Unendliche Graphentheorie (Spezialvorlesung Master; 4SWS)

Kapitel 8 der englischen Ausgabe einschließlich ausgewählter Übungen, plus zusätzliches Material. Kapitel 8.5 und diesen Übersichtsartikel behandle ich zuletzt; falls die Vorlesung geteilt wird in zwei 2-stündige Vorlesungen in aufeinanderfolgenden Semestern, geschieht dies im zweiten Semester.


Extremale Graphentheorie (Spezialvorlesung Master; 2SWS)

Je nach Dozent


Die Probabilistische Methode in der Diskreten Mathematik (Spezialvorlesung Master; 2SWS)

Auszüge aus dem Buch von Alon & Spencer und zusätzliches Material