Minimalgerüste

Es sei G=(V,E,f) ein zusammenhängender bewerteter Graph. Ein Gerüst H von G heißt Minimalgerüst, wenn seine Gesamtlänge f(H) minimal ist:

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:

1. Man wähle eine Kante mit kleinster Bewertung.
2. 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.