Baum (Graphentheorie)

Grundidee und Begriffe

Ein Baum ist in der Graphentheorie ein spezieller Graph: Er ist zusammenhängend und enthält keine geschlossenen Pfade, also keine Kreise. Damit kann man zum Beispiel eine Monohierarchie modellieren. Ein Baum ist außerdem ein Wald mit genau einer Zusammenhangskomponente.

Ein ungerichteter Baum ist ein zusammenhängender kreisfreier ungerichteter Graph. Knoten mit Grad 1 heißen Blätter; alle übrigen Knoten heißen innere Knoten. Der Grad eines Knotens ist die Anzahl der anliegenden Kanten.

Ein gerichteter Baum ist ein gerichteter Graph, der zu einem ungerichteten Baum wird, wenn man die Richtungen der Kanten ignoriert. Er ist also schwach zusammenhängend und kreisfrei. Ein gewurzelter Baum ist ein gerichteter, von einem Knoten w aus zusammenhängender kreisfreier Graph. Dieser Knoten w heißt Wurzel. Bei einem Out-Tree hat die Wurzel Eingangsgrad 0 und ist der einzige Knoten mit dieser Eigenschaft; die Kanten zeigen von der Wurzel weg. Knoten mit Ausgangsgrad 0 heißen Blätter, Knoten mit positivem Ausgangsgrad innere Knoten. Werden alle Kantenrichtungen umgekehrt, entsteht ein In-Tree, bei dem die Kanten zur Wurzel zeigen.

Jeder ungerichtete Baum kann an einem beliebigen Knoten w als Wurzel aufgefasst werden. Dann erhalten alle Kanten eine Richtung von w weg, und der Baum wird zu einem gewurzelten Baum. Hat ein ungerichteter Baum m Kanten, kann man diesen Kanten 2^m verschiedene Richtungen geben. Daraus entstehen 2^m gerichtete Bäume. Genau n=m+1 davon sind Out-Trees und ebenso viele sind In-Trees. Entfernt man bei einem gerichteten Baum die Orientierung der Kanten, erhält man wieder einen ungerichteten Baum.

Gleichwertige Kennzeichen

Für einen endlichen Graphen G=(V,E) mit |V|=n Knoten und |E|=m Kanten gibt es mehrere äquivalente Arten, einen ungerichteten Baum zu beschreiben:

• Zwischen je zwei Knoten von G gibt es genau einen Pfad.
• G ist zusammenhängend und enthält keinen Kreis.
• G ist leer oder G ist zusammenhängend und es gilt m=n-1.
• G ist leer oder G enthält keinen Kreis und es gilt m=n-1.
• G ist minimal zusammenhängend: G ist zusammenhängend, aber sobald man eine beliebige Kante entfernt, ist er nicht mehr zusammenhängend.
• G ist maximal azyklisch: G ist kreisfrei, aber jede zusätzliche Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis.

Bei unendlichen Graphen gelten die Aussagen mit m=n-1 nicht als Teil dieser Äquivalenz. Wichtig ist also besonders: Ein endlicher Baum mit n Knoten hat genau n-1 Kanten, und zwischen zwei Knoten gibt es genau einen Weg.

Warum diese Kennzeichen gelten

Die Beweise nutzen vor allem Zusammenhang und Kreisfreiheit. Weil ein Baum zusammenhängend ist, gibt es zwischen je zwei Knoten mindestens einen Pfad. Gäbe es zwischen zwei Knoten zwei verschiedene Pfade, dann ließen sich daraus zwei disjunkte Wege zwischen geeigneten Knoten u und v finden; zusammen würden diese Wege einen Kreis bilden. Das widerspricht der Kreisfreiheit. Daher gibt es genau einen Pfad.

Die Formel m=n-1 lässt sich für endliche Bäume durch vollständige Induktion zeigen. Für n=1 hat ein Baum nur einen Knoten und wegen Kreisfreiheit keine Schlinge, also m=0=n-1. Für einen Baum mit n Knoten betrachtet man einen längsten Pfad v1,v2,…,vk. Der Knoten v1 kann nur v2 als Nachbarn haben, sonst wäre der Pfad nicht längstmöglich oder es entstünde ein Kreis. Entfernt man v1 und die Kante (v1,v2), bleibt ein Baum mit n-1 Knoten und einer Kante weniger. Nach Induktionsvoraussetzung hat dieser m-1=n-2 Kanten; also hat der ursprüngliche Baum m=n-1 Kanten.

Auch die Begriffe minimal zusammenhängend und maximal azyklisch folgen aus der Kreisfreiheit. Würde ein Baum nach Entfernen einer Kante e=(u,v) zusammenhängend bleiben, gäbe es noch einen Pfad von u nach v; zusammen mit e ergäbe das einen Kreis. Fügt man umgekehrt eine Kante e=(u,v) hinzu, dann existiert im Baum bereits ein eindeutiger Pfad von u nach v. Die neue Kante bildet mit diesem Pfad einen Kreis.

Weitere wichtige Eigenschaften

Entfernt man aus einem Baum eine Kante, zerfällt er in zwei Teilbäume. Er wird damit zu einem Wald mit zwei Komponenten. Entfernt man einen Knoten zusammen mit seinen anliegenden Kanten, zerfällt der Baum in einen Wald aus k Bäumen, wobei k der Grad des entfernten Knotens ist. Entfernt man ein Blatt, also einen Knoten mit k=1, bleibt der Rest immer noch ein Baum.

Fügt man zwischen zwei vorhandenen Knoten eines ungerichteten Baums eine Kante hinzu, entsteht ein Kreis. Das passt zur Eigenschaft, dass Bäume maximal azyklisch sind.

Bäume sind wegen ihrer Kreisfreiheit stets bipartit. Bipartit bedeutet, dass man die Knoten in zwei Gruppen aufteilen kann, sodass jede Kante zwischen den Gruppen verläuft. Außerdem können Bäume topologisch sortiert werden und sind planar, also so zeichnbar, dass sich Kanten nicht überschneiden.

Typen, Zeichnung und Anzahl

Es gibt viele spezielle Baumarten. Der leere Graph enthält keine Knoten und keine Kanten. Ein isolierter Knoten hat keine Kanten. Lineare Graphen P_n sind Bäume, bei denen die inneren Knoten jeweils genau zwei Nachbarn haben. Sterngraphen S_n oder K_{1,n} besitzen einen inneren Knoten und n Blätter. Raupenbäume sind Bäume, bei denen alle Blätter höchstens Abstand 1 zu einem zentralen Pfad haben.

Bei Bäumen mit konstantem Verzweigungsfaktor haben innere Knoten eine feste Zahl von Nachfolgern. Binärbäume untergliedern eindimensionale Daten; ihre inneren Knoten haben zwei Nachfolger. Dazu gehören vollständige Binärbäume, AVL-Bäume und Rot-Schwarz-Bäume. Quadtrees untergliedern zweidimensionale Daten und haben vier Nachfolger pro innerem Knoten, Octrees untergliedern dreidimensionale Daten und haben acht Nachfolger. Binomial-Bäume haben einen variablen, aber festgelegten Verzweigungsfaktor: Ein Binomial-Baum der Ordnung k besitzt eine Wurzel mit Grad k, deren Kinder genau die Ordnungen k-1,k-2,…,0 besitzen. Bäume können außerdem nach Höhe, Knotengewicht oder Anordnung der Wurzel balanciert sein.

Das Zeichnen von Bäumen ist nicht trivial. Jeder Baum ist planar und kann ohne Kantenüberschneidungen gezeichnet werden. Je nach Zweck wünscht man zusätzlich gerade Kanten, ganzzahlige Koordinaten, kleinen Platzbedarf bei ästhetischem Ergebnis oder streng monoton fallende Kanten vom Elternelement zum Kind. Bekannte Algorithmen sind HV-Bäume und der Algorithmus von Walker.

In der Kombinatorik zählt man, wie viele verschiedene Bäume es gibt. Nach der Cayley-Formel gibt es n^{n-2} verschiedene bezeichnete Bäume mit n Knoten. Bezeichnet bedeutet, dass die Knoten nummeriert oder unterscheidbar sind. Der Prüfer-Code liefert einen einfachen Beweis, weil er eine Bijektion zwischen Codes der Länge n-2 und bezeichneten Bäumen mit n Knoten herstellt. Wenn die Knoten nicht nummeriert sind und isomorphe Bäume nicht mehrfach gezählt werden, wächst die Anzahl asymptotisch wie C·α^n·n^{-5/2}, mit C≈0,534949606 und α≈2,95576528565; dies bewies Richard Otter 1948. Eine genaue mathematische Formel ist nicht bekannt. Für n=12 gibt es zum Beispiel 61.917.364.224 bezeichnete und 551 unbezeichnete Bäume.

Spannbäume und Verallgemeinerungen

Jeder ungerichtete zusammenhängende Graph enthält einen Spannbaum, also einen Teilgraphen, der alle Knoten des ursprünglichen Graphen verbindet und selbst ein Baum ist. Minimale Spannbäume haben eine möglichst kleine Anzahl von Kanten oder eine möglichst kleine Summe der Kantengewichte. Sie werden praktisch genutzt, um kostengünstige zusammenhängende Netzwerke zu erstellen, zum Beispiel Telefonnetze oder elektrische Netze.

Ein Wald ist ein ungerichteter Graph, dessen Zusammenhangskomponenten Bäume sind. Ein Baum ist damit ein Wald mit genau einer Zusammenhangskomponente.

Eine weitere Verallgemeinerung ist der k-Baum. Ein ungerichteter Graph heißt k-Baum, wenn er rekursiv erzeugt werden kann: Der vollständige Graph K_k ist ein k-Baum. Fügt man zu einem k-Baum G einen neuen Knoten v hinzu und verbindet v mit allen Knoten einer Clique der Größe k aus G, dann ist auch der neue Graph ein k-Baum. Eine Clique ist eine Knotengruppe, in der jeder Knoten mit jedem anderen verbunden ist.

Ein partieller k-Baum entsteht durch Entfernen von Kanten aus einem k-Baum: Ist G=(V,E) ein k-Baum, dann ist H=(V,F) mit F⊆E ein partieller k-Baum. Weil diese Definition immer mindestens k Knoten verlangt, gibt es auch die Definition: Ein partieller k-Baum ist ein Teilgraph eines k-Baumes. Die Menge der partiellen k-Bäume ist genau die Menge der Graphen mit Baumweite höchstens k.