Minimalgerüste
Es sei 
ein zusammenhängender bewerteter Graph.
Ein Gerüst 
von 
heißt Minimalgerüst , wenn seine Gesamtlänge
minimal ist:
 |
(5.339) |
Minimalgerüste sucht man z.B. dann, wenn die Kantenbewertungen Kosten repräsentieren
und man an minimalen Gesamtkosten interessiert ist.
Ein Verfahren zur Ermittlung von Minimalgerüsten ist der
KRUSKAL-Algorithmus :
a) Man wähle eine Kante mit kleinster Bewertung.
b) Man füge solange wie möglich zu den bereits gewählten Kanten eine Kante
mit kleinstmöglicher Bewertung hinzu, die mit den schon gewählten Kanten keinen Kreis
bildet.
Die Auswahl der in Schritt b) zulässigen Kanten kann durch den folgenden
Markierungsalgorithmus erleichtert werden:
- Die Knoten des Graphen werden paarweise verschieden markiert.
- Kanten dürfen in jedem Schritt nur dann hinzugefügt werden, wenn sie Knoten mit
verschiedenen Markierungen verbinden.
- Nach Hinzufügen einer Kante wird den Knoten, die die größere der
Markierungen ihrer Endpunkte tragen, die kleinere der beiden Markierungen zugeordnet.
