Reinhard Diestel

Prüfungsinhalte Graphentheorie

Elementare Prüfungsinhalte sind zunächst alle Definitionen und Aussagen der Sätze. Zum Grundwissen gehören auch elementare Aussagen, die nicht die Form eines Satzes haben – etwa, dass die Komponenten eines Graphen seine Eckenmenge partitionieren, dass jeder Kantenzug von a nach b einen a-b-Weg "enthält", usw. Solche Dinge sollten Sie ggf. auch aus dem Stand beweisen können: nicht, weil Sie ihre (elementare) Beweise auswendig gelernt hätten, sondern weil Sie sich bei jeder Verwendung solcher Grundtatsachen in längeren Beweisen gefragt haben, weshalb dies wirklich der Fall ist, und Sie deshalb schon etliche Male in Gedanken diese elementaren Dinge für sich bewiesen haben. (Nicht wahr?)

Wer die Prüfung nicht nur bestehen sondern gut bestehen möchte, sollte auch die Beweise aller Sätze zumindest ansatzweise kennen. Rechnungen, etwa im Kapitel über Zufallsgraphen, müssen Sie nicht lernen; Sie sollten aber in der Lage sein, sie zu erklären, wenn ich ihnen eine aus dem Buch vorlege und genügend Zeit dafür gebe.

Hier sind ein paar typische weitergehende oder allgemeinere Prüfungsfragen:

Graphentheorie 1:

Zu jedem Kapitel: was sind die Leitfragen, und wie hängen diese zusammen? Gibt es Verbindungen zu anderen Kapiteln?

Was sind die wichtigsten Invarianten für Graphen, und wie hängen diese zusammen?

Welche Kantendichte erzwingt welche Teilstrukturen?

Führen Sie exemplarisch einen Induktionsbeweis einer einfachen Aussage. Kann es sein, dass eine stärkere Aussage leicher mit Induktion beweisbar ist als eine schwächere, und wenn ja, warum? Kennen  Sie ein Beispiel?

Was haben der Heiratssatz, der 1-Faktorsatz von Tutte, der Satz von Menger, und der Satz von Kuratowski gemeinsam? Ist auch die Hadwiger-Vermutung von diesem gemeinsamen Typ?

Was gibt es an dem vermeintlichen 3-Zeilen-Beweis der Eulerformel, wie er in den meisten Büchern zu finden ist (und ich ihn in der Vorlesung zur Motivation vorgestellt habe), alles zu präzisieren? Können Sie dies präzisieren – und zumindest klarmachen, was genau für einen präzisen Beweis alles zu zeigen ist?

Was ist so besonders an der chromatischen Zahl, verglichen mit anderen Invarianten?

Hat die kantenchromatische Zahl als Invariante etwas zu tun mit der gewöhnlichen chromatischen Zahl? Was unterscheidet sie wesentlich?

Was hat das Max-Flow-Min-Cut-Theorem über Netzwerke mit dem Satz von Menger zu tun?

Wie unterscheiden sich die typischen Fragestellungen der Ramseytheorie von denen der extremalen Graphentheorie – etwa der Satz von Ramsey vom Satz von Turan?

Welche seltsamen Phänomene können bei Aussagen über möglicherweise unendliche Graphen auftreten? Nennen Sie ein paar Beispiele.

Wie vergleicht sich der Satz von Chvatal über Gradsequenzen mit dem Satz von Dirac über Hamiltonkreise?

Was sind Zufallsgraphen, und weshalb werden sie betrachtet?

Was bedeutet die Aussage "Fast alle Graphen sind zusammenhängend"? Ist dies der Fall?

Wie unterscheiden sich bereits im Ansatz die beiden Teile des Beweises in Kapitel 9.4, dass die Funktion t=t(n) Schwellenfunktion der Grapheneigenschaft P_H ist?