DFS:

• Was kann man mit Tiefensuche in ungerichteten Graphen berechnen?
• Woran erkenne ich Artikulationspunkte?
• Warum funktioniert das?
• Warum O(|V|+|E|)? (das V ist hierbei nicht so wichtig)

Fluesse:

• Flussproblem: Was ist gegeben?
• Fluss erklaeren (er fand es nicht gut, dass ich erst erklaeren wollte wie man den Fluss berechnet und dann das Konservierungsgesetz. Sagt das Gesetz vorher )
• Was war voll der wichtige Begriff? (erweiternder Pfad)
• Was habe ich fuer einen Graphen, wenn ich die Kanten entsprechend in beide Richtungen einzeichne und so? (Residualgraph)
• Warum ist der Fluss maximal, wenn es keinen erweiternden Pfad gibt? (hier ist Schnitt wichtig)
• *malt das Beispiel mit potenziellem O(maximale Kapazitaet) aus der Vorlesung* Hier ist wichtig, dass die Laufzeit exponentiell sein kann.
• Dann kamen wir zu geschichteten Netzwerken.
• Wichtig: Auf dem geschichteten Netzwerk wird der maximale Fluss (des geschichteten Netzwerks) berechnet.
• Warum ist diese Methode mit dem geschichteten Netzwerk geil fuer die Berechnung des maximalen Flusses auf dem urspruenglichen Netzwerk? (ich sagte O(|V|^2 * |E|) ist besser als O(|V| * |E|^2); er wollte hoeren, dass es besser ist als das exponenzielle (und unabh. von Kapazitaeten))
• Irgendwann hat er auch nach dem integrality theorem gefragt. (beide fanden es ganz lustig, als ich integrity theorem sagte)

Zu den anderen Themen kam tatsaechlich nix. Ich wusste das meiste, brauchte aber teilweise etwas Hilfestellung, um auf die Antworten zu kommen. Notengebung ist fair. Die Atmosphaere war recht angenehm, wobei er teilweise etwas unzufrieden wirkte, wenn er es (denke ich) gar nicht war.