Minimaler Spannbaum
Glasfaser für alle Dörfer
Sieben Dörfer sollen ans Glasfasernetz. Die Kabel dürfen nur entlang der Straßen verlegt werden (Länge in km). Jedes Dorf muss – direkt oder über andere Dörfer – mit jedem anderen verbunden sein. Die Bagger kosten pro Kilometer, also soll das Kabelnetz möglichst kurz sein.
O = Oberdorf, B = Bergweiler, W = Waldhausen, M = Mittelbach, K = Kirchheim, T = Talheim, N = Niederau
Merke
Zulässig ist jedes Kabelnetz, das alle Dörfer miteinander verbindet. Ein Teilgraph, der alle Knoten verbindet und keinen Kreis enthält, heißt Spannbaum. Optimal ist der minimale Spannbaum mit der kleinsten Summe der Gewichte.
Algorithmus von Kruskal (greedy): Gehe die Kanten von der kürzesten zur längsten durch. Nimm eine Kante, wenn sie keinen Kreis schließt, sonst lass sie weg. Höre auf, wenn alle Knoten verbunden sind.
Auch hier führt die gierige Wahl garantiert zur optimalen Lösung.
Aufgabe 2: Warum lässt Kruskal eine Kante weg, die einen Kreis schließen würde?
Aufgabe 3
Die sechs größten Städte des Saarlandes sollen mit einem neuen Glasfaser-Ring verbunden werden – entlang der Straßen aus Kapitel 2.
MZG = Merzig, SLS = Saarlouis, SB = Saarbrücken, NK = Neunkirchen, WND = St. Wendel, HOM = Homburg