Starten

Erinnerung VL 27.06.2016

Kap. 11: Minimale Spannbäume

Minimale Spannbäume (MST)

Minimale aufspannende Wälder (MSF)

Anwendungen

MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property)

MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property)

Der Jarník-Prim-Algorithmus

Analyse

Kruskals Algorithmus (1956)

Kruskals Algorithmus Korrektheit

Union-Find Datenstruktur

Beginn Übung 10

Kürzeste Wege Algorithmen: Bellman-Ford

Bellman-Ford: Pseudo-Code

Bellman-Ford: Korrektheit (Beweis-Idee)

Bellman-Ford: Beispiel

Bellman-Ford: Bestimmung eines negativen Kreises

Minimale Spannbäume

Minimale Spannbäume: Jarník-Prim

Minimale Spannbäume: Kruskal

Steinerbäume

Steinerbaum: Was kann schief gehen?

Problem des Handlungsreisenden (TSP)