TU Wien:Algorithmen auf Graphen VU (Chwatal)/Prüfungsfragen WS09

Shortest Path (NP oder P), wieso findet bellman ford den optimalen weg, wie findet man negative zyklen

Minimum Cost Network, wie findet man feasible flow, (optimalität, feasible, supply/demand)bedingungen

als zusatzfrage dann korrektheit von SCC

---

planarer graph, eulerscher graph, hamiltonscher graph

johnson

preflow push

als zusatzfrage dann korrektheit von SCC

---

Wie funktioniert Floyd-Warshal, kurze Demonstration, welches SP-Problem löst er + Laufzeit.

Welcher Algo ist besser für dünne Graphen (Johnson)

Wie funktioniert Johnson, warum gibt es Probleme mit negativen Kantengewichten, was gilt die für neuen Kantengewichte (Lemma 61, SP und NCC bleiben gleich)

Was ist ein Matching, ein augmentierender Pfad, Beweis (in Ansätzen) das ein Matching maximal ist, wenn es keinen aug. Pfad gibt

---

Erklären des Johnson Algorithmus (Wie funktioniert er? Warum funktioniert er? Wann funktioniert er nicht? (Negative Kostenzyklen)) Warum können bei Dijkstra keine negativen Kantengewichte verwendet werden bzw. warum funktioniert das transformieren auf positive Kantengewichte durch addition eines konstanten Wertes nicht.

Minimum Cost Network: Was ist das? Nebenbedingungen. Supply/Demand. Gültige Lösung? Negative Cycle Optimality Condition und Algorithmus

Was ist ein Hamiltonscher Zyklus.