Minimalspannende Bäume

Vor langer Zeit gab es eine Stadt, die keine Straßen hatte. Sich in dieser Stadt zu bewegen war insbesondere dann schwierig, wenn der Regen nach starken Gewittern die Wege sehr matschig machte. Fahrzeuge blieben stecken und jeder hatte ziemlich dreckige Schuhe. Daher entschied der Bürgermeister, einige Straßen zu asphaltieren. Allerdings wollte er nicht mehr Geld ausgeben als unbedingt nötig, damit auch noch ein Schwimmbad gebaut werden konnte.

¹⁾

Also legte er zwei Bedingungen fest:

• Es müssen ausreichend Straßen asphaltiert werden, damit jeder von seinem Haus jedes andere Haus trockenen Fußes erreichen kann.
• Das Asphaltieren soll so wenig kosten wie möglich. Die Anzahl der Pflastersteine ist das Maß für die Kosten.

Finde die Wege, die alle Häuser miteinander verbinden und deren Asphaltierung am wenigsten kostet (=Pflastersteine beinhaltet).

Tipp

Lösung

Welche Strategien hast du genutzt, um das Problem zu lösen?

Wende einen Algorithmus zur Bestimmung des minimalen Spannbaums im Graphentester auf die Karte der größten Städte in Deutschland an (02_deutschlandkarte.csv). Beachte, dass nur markierte Kanten sichtbar sind, da es zu viele Kanten gibt, um sie alle übersichtlich darzustellen. Vergleiche mit dem Autobahnnetz in Deutschland. Nenne Ursachen für Unterschiede.

Öffne den Stadtplan von Baden-Baden (03_badenbaden.csv) und die Karte mit den Fährstrecken (04_inseln.csv) jeweils im Graphentester. Gib je eine praktische Aufgabenstellung für diese Graphen an, bei denen ein minimaler Spannbaum die beste Lösung ist.

Lösungsvorschläge

Wir betrachten zwei Algorithmen zur Lösung des Problems des minimal spannenden Baums:

• Algorithmus von **Kruskal**²⁾
• Algorithmus von Prim³⁾