AuK/Minimaler Spannbaum WS13-14

Wiki-Quelltext dieser Seite.

<language>Processing</language>
Autoren:
* [mailto:s3darich@stud.hs-zigr.de Daniel Richter]
* [mailto:s3addank@stud.hs-zigr.de Adrian Danker]

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.

[[Datei:Breitensuche.png|350px|thumb|right|Anwendung von BFS auf einen ungerichteten Graphen]]

<div style="background-color:#EEE; max-width:500px">
'''Generischer Algorithmus'''  <br>
1  $A\longleftarrow \emptyset$ <br>
2  '''while''' A bildet keinen Spannbaum<br>
3  $\;\;\;\ $do bestimme eine Kante $\left(u,v\right)$, die  sicher für A ist<br>
4  $\;\;\;\  A\leftarrow A\cup\lbrace\left(u,v\right)\rbrace$ <br>
5  '''return''' A <br>
</div>