Minimaler Spannbaum WS13-14
Inhaltsverzeichnis |
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
Die Schleifeninvariante wird wie folgt verwendet:
- Initialisierung : Nach der ersten Zeile wird die Schleifeninvariante erfüllt.
- Fortsetzung : In den Zeilen 2-4 erhält die Schleife die Schleifeninvariante, da nur sichere Kanten hinzugefügt werden.
- Terminierung : Alle Kanten die A hinzugefügt werden, sind in einem minimalem Spannbaum. Also ist die Menge A, ein minimaler Spannbaum und wird zurückgegeben.
Bestimmung einer sicheren Kante
Dies ist das eigentlich wichtige. Eine sichere Kante muss existieren. Denn wenn, wie im Pseudocode die dritte Zeile ausgeführt wird, ist dies durch die Schleifeninvariante festgelegt. Das heißt es existiert ein Spannbaum T mit A\subseteq T.\\ In der While-Schleife muss A eine echte Teilmenge von T sein. Es existiert also eine Kante\left(u,v\right) \in E, welche sicher für A ist aber nicht zu A gehört.\\ \textbf{Genauer}\\ Um diese Kanten genau bestimmen zu können, benötigen wir einige Definitionen.\\ \textbf{Schnitt eines ungerichteten Graphen}\\ Ein Schnitt \left(S,V - S\right), ist eine Partitionierung von V, eines ungerichteten Graphen G=\left( V,E\right). Wenn eine Kante \left( u,v\right) \in E mit einem ihrer Endpunkte in S und der andere in V - S liegt, dann kreuzt die Kante \left( u,v\right) den Schnitt \left(S,V -V\right). Ein Schnitt respektiert eine Kantenmenge A, falls keine Kante von A den Schnitt kreuzt. Wenn eine Kante das kleinste Gewicht aller Kanten besitzt, welche den Schnitt kreuzen, ist es eine leichte Kante. \subsubsection{Regel zu Identifizierung sicherer Kanten} G=\left(V,E\right) sei ein Zusammenhängender, ungerichteter Graph, für den eine reellwertige Gewichtsfunktion auf E definiert ist. Weiter seien A eine Teilmenge von E, die zu einem minimalen Spannbaum für G gehört \left(S,V -V\right) ein Schnitt von G, der A respektiert und \left( u,v\right) eine leichte Kante, die \left(S,V -V\right) kreuzt. Dann ist die Kante \left( u,v\right) für A sicher.\\