Gedächtnisprotokoll Graphentheorie

Datum: 15.4.2003
Note: 1.0
Beisitzer: Dr. Müller

Die Fragen:

• Definition eines Graphen
• Was wird dabei ausgeschlossen - habe schlichte Graphen erklärt
• Definition der zu den Graphen gehörigen Matrizen, habe Adjazenz - und Inzidenzmatrix erklärt
• Was sind Knotenraum, Kantenraum, Rand- und Korandabbildung?
• Wir hängen sie mit den Matrizen zusammen?
• Wie geht der Satz von Kirchhoff? Inzidenzmatrix erläutert, algebraisches Komplement erläutert, Satz genannt
• Wie geht der Satz von Cailey? War die einzige Frage der Prüfung, die ich nicht konnte
• Was ist ein Baum? Definition genannt: Von jedem Knoten zu jedem genau ein Kantenweg
• Was für Eigenschaften hat ein Baum? minimal zusammenhängend, maximal kreislos, |V| - 1 Kanten
• Was sind Euler- und Hamiltongraphen?
• Bedingung für Eulergraph?
• Was besagt das Lemma von Bondy-Chvatal?
• Welche Korollare gibt es dazu?
• irgendwann muß da noch gefallen sein, daß vollständige Graphen trivialerweise hamiltonsch sind und die Idee des ganzen ist, aus dem gegebenen Graphen den vollständigen zu konstruieren
• Was besagen die Sätze von Menger und Ford-Fulkerson? Habe einen hingeschrieben, einen verbal genannt und noch gesagt, daß dahinter die Idee "maximaler Fluß = minimale Trennkapazität" steht
• Was für Färbungsprobleme gibt es? Knoten- und Kantenfärbungen erläutert
• Welche Abschätzung gilt für die Kantenfärbung? Satz von Vizing, dann sollte ich noch anhand von Kreisgraphen erläutern, das tatsächlich beide Fälle eintreten (habe einen mit gerader und einen mit ungerader Kantenzahl aufgezeichnet und "gefärbt")
• Was besagt der Vierfarbensatz?

Die Prüfung verlief ziemlich problemlos. Hr. Kamps fragte mich zu Anfang, ob ich den Schein gemacht habe (nein), daß er mich aber irgendwo her erkenne. Ich antwortete, daß das wohl daran liege, daß ich auf dem Studientag gewesen sei, was Hr. Müller dann sogar bestätigte. Bei der Definition der Graphen (als 5-Tupel) merkte Hr. Kamps an, daß wir die gerichteten wohl nicht behandeln werden, was dann auch eintrat. Ich würde sie sicherheitshalber trotzdem zumindest in all den Fällen lernen, in denen sowieso alles ziemlich wie im ungerichteten läuft oder die anderweitig ganz gut zu behalten sind, so als Reserve für den Fall, daß irgend etwas anderes nicht so gut läuft.
Beweise hat er gar nicht gefragt. Beim Studientag sagte er, daß z. B. der Beweis vom Lemma von Bondy-Chvatal, den er da auch demonstriert hatte, in einer Prüfung dran kommen könnte, während andere einfach zu lang und aufwändig für eine Prüfung wären.

Die Gesamtatmosphäre der Prüfung fand ich etwas fließbandmäßig. Wobei es meine vierte und wohl letzte (zumindest in diesem Studium) Prüfung bei Prof. Kamps war. Ich finde grundsätzlich, daß man immer gut zu ihm zu einer Prüfung gehen kann.

Also, falls Ihr Euch zu der Prüfung entschließt: Viel Erfolg!