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, 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

Graphentheorie, Master (2SWS-Grundstock; hinzu kommen weitere Themen im Umfang von 2SWS)

Zyklenraum, algebraische Plättbarkeitskriterien und Dualität: Kap. 0.9, 2.1.2-3, 2.2.3 (Beweis: Extrablatt bzw. 4. Auflage) und 3.5-6

Packungen und Überdeckungen: Kap. 1.3-4

Perfekte Graphen: Kap. 4.5

Algebraische Flüsse: das ganze Kapitel 5 außer 5.2

Extremale Graphentheorie: Kap. 2.5 ohne Beweis von Satz 2.5.3; Kap. 6.2; Kap. 6.4

Minorentheorie (Spezialvorlesung Master; 2SWS)

Minorenkapitel (Ch.12) der englischen Ausgabe und zusätzliches Material

Unendliche Graphentheorie (Spezialvorlesung Master; 2SWS)

Extremale Graphentheorie (Spezialvorlesung Master; 2SWS)

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

Zusätzliches Material zum Austausch: Kap. 1.2.3 (Gallai-Edmonds); Kap.3.3; Kap. 8.3 (Fleischner); Kap. 7.3 (Ramsey induziert)