20 |

0:00:00 Starten

0:00:06 Erinnerung VL 27.06.2016

0:02:09 Kap. 11: Minimale Spannbäume

0:02:28 Minimale Spannbäume (MST)

0:03:22 Minimale aufspannende Wälder (MSF)

0:03:36 Anwendungen

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

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

0:15:54 Der Jarník-Prim-Algorithmus

0:28:39 Analyse

0:32:00 Kruskals Algorithmus (1956)

0:37:47 Kruskals Algorithmus - Korrektheit

0:40:56 Union-Find Datenstruktur

0:44:15 Beginn Übung 10

0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford

0:45:40 Bellman-Ford: Pseudo-Code

0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee)

0:48:53 Bellman-Ford: Beispiel

0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises

0:55:03 Minimale Spannbäume

0:57:00 Minimale Spannbäume: Jarník-Prim

0:58:37 Minimale Spannbäume: Kruskal

1:00:00 Steinerbäume

1:05:42 Steinerbaum: Was kann schief gehen?

1:10:09 Problem des Handlungsreisenden (TSP)