| Prüfer: | Prof.Dr.R.Verbeek |
| Datum: | 27.02.2001 |
| Dauer: | 20min |
| Note: | 1.0 |
Welche Verfahren zum Durchsuchen von Graphen kennen Sie?
DFS und BFS - beide ausführlich erklärt
Welche klassischen Anwendungen kennen Sie?
Leider fielen mir hier plötzlich keine klassischen Anwendungen ein – aber ich habe dann für BFS die Phase 1 von dem Algorithmus von Dinic genannt und für DFS den Test für paare Graphen durch abwechselndes Färben der Knoten und Berücksichtigung der Rückwärtskanten
Welche Verfahen kennen Sie, um Minimalgerüste zu bestimmen?
Zuerst habe ich das Prinzip erklärt – mit der Menge U, V\U und der Kante e0 mit minimalem Gewicht. Dann bin ich auf den Algorithmus von Jarnik, Prim, Dijksta sehr ausführlich eingegangen und auf die Algorithmen von Kruskal und Boruvka, Sollin nur oberflächlich.
Jetzt gibt es da ja auch noch so einen greedy-Algorithmus – wie funktioniert der denn?
Hier habe ich den Algorithmus komplett aufgeschrieben und grob erklärt.
Wann ist der denn jetzt optimal?
Wenn M=(E,J) Matroid ist
Ist denn der Algorithmus von Jarnik, Prim, Dijkstra optimal?
Konnte ich auf Anhieb erstmal nicht beantworten, aber er meinte dass ich das ja schon vorher durch das Prinzip bei den Minimalgerüsten erklärt hätte und er sei optimal!
Kennen Sie ein Beispiel, bei dem das nicht der Fall ist?
TSP fiel mir ein – musste aber nichts weiter dazu erklären.
Was wissen Sie denn über unabhängige Knotenmengen
U unabhängige Knotenmenge ó V\U Knotenüberdeckung
Und wie bestimmt man sie jetzt?
Hmmm – in paaren Graphen?
Nein – in beliebigen Graphen
NP-vollständig (VERTEX COVER)
Und wie sieht es mit unabhängigen Kantenmengen aus?
Bei beliebigen Graphen: Ergänzungspfadmethode. Diese habe ich ausführlich erklärt mit Definitionen von Zuordnungen, M-alternierenden Pfaden und M-Ergänzungspfaden.
Bei paaren Graphen: Rückführung auf das Maximalflussproblem. Hier habe ich den Algorithmus von Floyd/Fulkerson erklärt.
Da müssen ja nicht unbedingt ganzzahlige Flüsse rauskommen.
Hier hatte ich erst widersprochen... er hat mir dann aber ein Beispiel aufgemalt.
Bei Floyd/Fulkerson ist es aber gerade so, dass immer ganzzahlige Flüsse rauskommen.
Angenehme Prüfungsatmosphäre. Ohne Vorgespräch wurde gleich mit der Prüfung begonnen. Danach haben wir uns noch etwas unterhalten. Verbeek hatte ich aus diversen Prüfungsprotokollen als unangenehmen Prüfer erwartet – dem war allerdings gar nicht so. Komplexitäten wurden gar nicht abgefragt.
Viel Erfolg!