Minimale Spannbäume

Ziel des Minimalen-Spannbaum-Problem ist es, eine Menge von Knoten mit minimalen Kosten zu verbinden. Solch ein Problem liegt zum Beispiel vor, wenn man

• einige Rechner möglichst kostengünstig miteinander verbinden möchte
• mit einem möglichst kurzen Rohrnetz alle Häuser eines Blocks mit Wasser versorgen möchte

Ein Spannbaum muss also zwei grundlegende Eigenschaften erfüllen,

• Zusammenhang und
• Kreisfreiheit.

Daraus ergibt sich sofort, dass ein Spannbaum eine Kante weniger als Knoten enthalten muss. Hätte er weniger Kanten, könnte er nicht alle Knoten verbinden, hätte er dagegen mehr, so würde er unweigerlich einen Kreis enthalten.

Ist nun jeder Kante ein Gewicht - beispielsweise Länge oder Kosten - zugeordnet, so kann man nach einem Spannbaum mit möglichst kleiner Gesamtlänge oder möglichst niedrigen Gesamtkosten fragen, also nach einem minimalen Spannbaum.

Zur Bestimmung minimaler Spannbäume gibt es mehrere Algorithmen, die zum Teil mehrmals und unabhängig von einander gefunden wurden. Wir beschränken uns hier auf zwei Varianten:

• Prim - Algorithmus
• Kruskal - Algorithmus