Definition Baum

Ein Baum ist ein zusammenhängender Graph, der frei von Kreisen ist.

Äquivalent mit der Aussage „ein Graph ist ein Baum“ sind auch folgende Aussagen:
a.) Ein Graph ist zusammenhängend, aber das Streichen einer beliebigen Kante führt dazu, dass der Graph nicht mehr zusammenhängend ist.
b.) Der Graph ist frei von Kreisen, es gibt aber keine Möglichkeit eine Kante hinzuzufügen, ohne dass ein Kreis entsteht.
c.) Der Graph hat n Knoten, ist zusammenhängend und hat n-1 Kanten.
d.) Der Graph hat n Knoten, keine Kreise und n-1 Kanten.
e.) Es gibt nur genau einen Weg zwischen zwei Knoten.

Gerichtete Graphen werden häufig wie ungerichtete Graphen behandelt, d.h. die Pfeilrichtung spielt keine Rolle, d.h. es reicht, wenn der Baum schwach zusammenhängend ist.

Wurzel

Im ungerichteten Baum ist die Wurzel ein besonders hervorgehobener Knoten, der typischerweise in einer grafischen Darstellung an oberster Stelle steht. Unter mathematischen Gesichtspunkten kann im ungerichteten Baum jeder Knoten Wurzel sein. Typischerweise ergibt sich die Wahl des Knoten aus der inhaltlichen Struktur des realen Gegenstandes, der durch den Baum abgebildet wird.

In einem gerichteten Baum ist es der Knoten von dem ein Weg zu allen anderen Knoten existiert oder der Knoten zu dem von jedem Knoten ein Weg aus führt. Zur Erinnerung, wir haben weiter oben vereinbart, dass bei einem Weg die Pfeile nur in Pfeilrichtung benutzt werden dürfen.

In Abb. 1-12 sind zwei Beispiele für Wurzeln dargestellt. Links: Der Knoten, der als Wurzel gewählt wurde, ist farbig markiert. Es könnte aber auch jeder andere sein. Rechts: Eine Ordnerstruktur, auch Verzeichnisbaum genannt, auf einer Festplatte kann graphentheoretisch als Baum interpretiert werden. Hier ergibt sich aus der Sache, dass das Stammverzeichnis, hier C://, die Wurzel ist.

Minimale Spannbäume / Gerüste

Eine Teilmenge B von Kanten eines ungerichteten Graphens bildet einen Spannbaum, wenn jeder Knoten des Baums mit mindestens einer Kante inzidiert und B ein Baum ist. Um ein anderes Bild zu bemühen, ein Spannbaum ist ein Gerüst, das alle Knoten trägt, aber kein überflüssiges Element hat.

Zu jedem Graphen gibt es im Allgemeinen viele verschiedene Spannbäume. In einem Netzwerk, d.h. in einem Graphen in dem die Kanten mit Gewichten verbunden sind, stellt sich die Frage, welche Kanten ausgewählt werden müssen, damit die Summe der Kantengewichte minimal ist. Ein solcher Baum ist ein Minimaler Spannbaum.

Kruskals-Algorithmus ist ein sogenannter Greedy-Algorithmus. Die „Gier“ des Algorithmus besteht darin, dass die Kanten einmal zu Beginn nach den Kantengewichten sortiert werden und dann nach und nach, angefangen bei der Kante mit der geringsten Bewertung, versucht wird die Kanten in B einzufügen. Einmal in B eingefügt bleiben die Kanten auch dort.

Greedy-Algorithmen führen in der Regel zu einer guten Lösung, aber nur selten zum Optimum. Kruskals-Algorithmus ist eine Ausnahme. Er führt zum Optimum, d.h. es gibt keinen Spannbaum mit in Summe geringeren Kantengewichten, es gibt höchstens einen anderen Spannbaum mit in Summe gleichen Kantengewichten.

Um den Unterschied zu verdeutlichen: Der Simplex-Algorithmus ist kein Greedy-Algorithmus. Zwar wird auch dort zunächst die Variable mit dem geringsten Zielzeilenkoeffizienten in die Basis aufgenommen. Allerdings werden in jedem Schritt neue Zielzeilenkoeffizienten berechnet um neue, der aktuellen Situation angepasste Informationen zu gewinnen. Ist eine Variable einmal in der Basis enthalten, kann es durchaus sein, dass sie in einer späteren Iteration wieder entfernt wird.

Kruskal-Algorithmus (Ablaufdarstellung)

Bei einer kleinen Handrechnung ist Kruskals Algorithmus einfach auszuführen. Bei der Programmierung wird ein Sortieralgorithmus benötigt. Außerdem bedarf es einer Routine, um festzustellen, ob durch das Hinzufügen einer Kante ein Kreis entsteht.

Damit wäre auch schon ein Algorithmus vorgestellt. Er wurde erstmals 1956 von Joseph Bernard Kruskal veröffentlicht. Eine Alternative zu Kruskals Algorithmus ist der 1930 von dem tschechischen Mathematiker Vojtech Jarnik entwickelte und von Robert C. Prim 1957 wiederentdeckte Prims Algorithmus.

Prims Algorithmus ist Kruskals Algorithmus ähnlich. Unterschied ist, dass B während der gesamten Berechnung zusammenhängend ist und dementsprechend in jeder Iteration nur Kanten betrachtet werden, die mit einem Knoten inzidieren, der seinerseits bereits mit einer in E_B enthaltenen Kante inzidiert.