Minimaler Spannbaum WS13-14
Autoren:
Als minimale Spannbäume wird die Menge aller Verbindungen zwischen Punkten bezeichnet, die nötig sind, um alle Punkte mit minimaler Distanz zu verbinden.
Spannbäume, Motivation
Mit Hilfe von minimalen Spannbäumen lassen sich effiziente Lösungen für...
...sie sind sehr nützlich, um Probleme wie das TSP zu vereinfachen oder kostengünstige Lösungen für zusammenhängende Netzwerke (Telefonnetz, Gas-/Wasser-/Abwasserversorgung, Internet) zu finden.
Aufbau minimaler Spannbäume
generischer Ansatz
Allgemeine Festlegung : Invariante: ist eine Aussage, die über die Ausführung bestimmter Programmbefehle hinweg gilt. Unmittelbar vor jeder Iteration ist A eine Teilmenge eines minimalen Spannbaumes. In jedem Schritt wird eine Kante \left(u,v\right) bestimmt, welche zu dem minimalen Spannbaum A hinzugefügt werden kann. Dadurch sind A\cup\lbrace\left(u,v\right)\rbrace eine Teilmenge von einem minimalen Spannbaum ist. Diese Kante wird als sichere Kante für A bezeichnet, ohne die Invariante zu verletzen.
Generischer Algorithmus
1 A\longleftarrow \emptyset
2 while A bildet keinen Spannbaum
3 \;\;\;\ do bestimme eine Kante \left(u,v\right), die sicher für A ist
4 \;\;\;\ A\leftarrow A\cup\lbrace\left(u,v\right)\rbrace
5 return A