Baum (Graphentheorie)

Ein Baum ist in der Graphentheorie ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen Pfade enthält, d. h. damit lässt sich eine Monohierarchie modellieren. Je nachdem, ob die Kanten des Baums eine ausgezeichnete und einheitliche Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in ungerichtete Bäume und gewurzelte Bäume, und für gewurzelte Bäume in Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen Kanten in Richtung Wurzel zeigen.

Ein Baum ist ein Wald mit genau einer Zusammenhangskomponente.

Darstellung aller Bäume mit einer, zwei oder drei Kanten bei der ersten mathematischen Modellierung von Bäumen durch Arthur Cayley (1857)

Definitionen

Ungerichteter Baum mit vier inneren Knoten (schwarz) und fünf Blättern (weiß)

Ein Baum ist ein zusammenhängender kreisfreier ungerichteter Graph. Die Knoten mit Grad 1 heißen Blätter, die übrigen Knoten heißen innere Knoten.

Gewurzelter Baum (hier: Out-Tree) mit einer Wurzel (umrandet), vier inneren Knoten (schwarz) und fünf Blättern (weiß)

Ein gerichteter Baum ist ein gerichteter Graph, der ein ungerichteter Baum ist, wenn man die Richtungen der Kanten ignoriert. Er ist also ein gerichteter schwach zusammenhängender kreisfreier Graph. Bei vielen Autoren müssen die Richtungen einheitlich von einem Knoten weg oder auf einen Knoten zu orientiert sein. Dafür gibt es aber auch den schärferen Begriff des gewurzelten Baums.

Ein gewurzelter Baum ist ein gerichteter von einem Knoten $w$ aus stark zusammenhängender kreisfreier Graph. Der den starken Zusammenhang definierende Knoten $w$ wird Wurzel genannt. Er hat Eingangsgrad 0 und ist der einzige Knoten mit dieser Eigenschaft. Alle Knoten mit Ausgangsgrad 0 heißen Blätter. Alle Knoten mit positivem Ausgangsgrad heißen innere Knoten. So geht die Definition eines Out-Trees.

Werden die Richtungen aller Kanten eines solchen Graphen invertiert, so wird er zu einem In-Tree. Dieser wird ebenfalls als gewurzelter Baum angesehen.

Man kann jeden ungerichteten Baum an einem beliebigen Knoten $w$ fassen und „schütteln“ – die Schwerkraft gibt allen Kanten eine definierte Richtung von $w$ weg, die aus dem ursprünglich ungerichteten Baum einen gewurzelten machen mit $w$ als Wurzel.

Den $m$ Kanten eines ungerichteten Baums kann man $2^{m}$ verschiedene Richtungen geben und so $2^{m}$ gerichtete Bäume ableiten. Genau $n=m+1$ davon sind Out-Trees und ebenso viele sind In-Trees. Entfernt man umgekehrt bei einem gerichteten Baum die Orientierung der Kanten, so erhält man einen ungerichteten Baum.

Eigenschaften

Ein endlicher Graph $G=(V,E)$ mit $|V|=n$ Knoten und $|E|=m$ Kanten kann durch folgende äquivalente Aussagen als Baum definiert werden:

• 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, das heißt $G$ ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt.
• $G$ ist maximal azyklisch, das heißt $G$ ist kreisfrei, aber jede weitere Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis.

Im Falle unendlicher Graphen müssen hier die dritte und vierte Bedingung aus der Äquivalenz ausgenommen werden.

Beweise

• Zwischen je zwei Knoten von $G$ gibt es genau einen Pfad.

Zwischen je zwei Knoten von $G$ gibt es mindestens einen Pfad, weil jeder Baum zusammenhängend ist. Gäbe es zwei Knoten von $G$ mit mindestens zwei Pfaden, dann gäbe es zwei Knoten $u$ und $v$ auf diesen Pfaden, deren Pfade keinen gemeinsamen inneren Knoten haben (disjunkte Wege), zum Beispiel $u,v_{1},\dots ,v_{k},v$ und $u,u_{1},\dots ,u_{l},v$. Dann wäre $u,v_{1},\dots ,v_{k},v,u_{l},\cdots ,u_{1},u$ ein Kreis von $G$ im Widerspruch zur Annahme, dass $G$ ein Baum ist.

• $G$ ist leer oder $G$ ist zusammenhängend und es gilt $m=n-1$.

Dies lässt sich mit vollständiger Induktion zeigen. Für $n=1$, also einen leeren Graphen mit einem einzelnen Knoten und ohne Kanten, gilt $m=n-1=0$. Nach Induktionsvoraussetzung nehmen wir an, dass die Gleichung $m=n-1$ für jeden Baum mit $n-1$ Knoten gilt. Ist $G$ ein Graph mit $n$ Knoten und $v_{1},v_{2},\dots ,v_{k}$ die Knoten eines längsten Pfades von $G$. Alle Nachbarn von $v_{1}$ liegen auf diesem Pfad, sonst wäre er nicht der längste Pfad. $v_{2}$ ist der einzige Nachbar von $v_{1}$, denn sonst würde $G$ einen Kreis enthalten. Entfernen wir $v_{1}$ und die Kante $(v_{1},v_{2})$ aus $G$, dann erhalten wir einen zusammenhängenden Graphen, denn $v_{2}$ ist der einzige Nachbar von $v_{1}$. Der entstandene Graph hat genau einen Knoten und eine Kante weniger als $G$, also $n-1$ Knoten. Nach Induktionsvoraussetzung gilt $m=n-1$, also hat der entstandene Graph $m-1=n-2$ Kanten. Daraus folgt, dass der Graph $G$ genau $n$ Knoten und $m=n-1$ Kanten hat.

• $G$ ist minimal zusammenhängend, das heißt $G$ ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt.

Wäre $G$ nach Entfernen der Kante $e=(u,v)$ immer noch zusammenhängend, dann würde der entstandene Graph einen Pfad $u,v_{1},\dots ,v_{k},v$ von $u$ nach $v$ enthalten und $u,v_{1},\dots ,v_{k},v,u$ wäre ein Kreis von $G$.

• $G$ ist maximal azyklisch, das heißt $G$ ist kreisfrei, aber jede weitere Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis.

Wäre $G$ nach Hinzufügen der Kante $e=(u,v)$ immer noch kreisfrei, dann würde $G$ keinen Pfad von $u$ nach $v$ enthalten und wäre nicht zusammenhängend im Widerspruch zur Annahme, dass $G$ ein Baum ist.

Weitere Eigenschaften

• Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen Wald mit zwei Komponenten.

• Entfernt man einen Knoten zusammen mit den anliegenden Kanten, zerfällt ein Baum in einen Wald aus $k$ Bäumen, mit $k$ als Grad des entfernten Knotens. Entfernt man von einem Baum ein Blatt ($k=1$), so ist der Rest immer noch ein Baum.

• Durch Hinzufügen einer Kante zwischen zwei vorhandenen Knoten entsteht im ungerichteten Baum ein Kreis.

• Bäume sind aufgrund der Kreisfreiheit stets auch bipartit und können topologisch sortiert werden.

• Bäume sind planar.

Spezielle Bäume

Es existiert eine Vielzahl von Begriffen, die Bäume näher spezifizieren. So gibt es zum Beispiel

• den leeren Graph. Dieser enthält keine Knoten und Kanten.
• den isolierten Knoten ohne Kanten
• lineare Graphen $P_{n}$. Die inneren Knoten haben jeweils genau zwei Nachbarn.
• Sterngraphen $S_{n}$ oder $K_{1,n}$. Diese enthalten einen inneren Knoten und $n$ Blätter.
• Raupenbäume. Alle Blätter haben einen maximalen Abstand von 1 zu einem zentralen Pfad.
• Bäume mit konstantem Verzweigungsfaktor, also Grad der inneren Knoten (Bereichsbaum):
  • Binärbäume (untergliedern eindimensionale Daten, innere Knoten haben zwei Nachfolger), darunter vollständige Binärbäume, AVL-Baum und Rot-Schwarz-Baum,
  • Quadtrees (untergliedern zweidimensionale Daten, innere Knoten haben vier Nachfolger),
  • Octrees (untergliedern dreidimensionale Daten, innere Knoten 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 Ordnung $k-1,k-2,\dots ,0$ besitzen.
• Bäume können nach ihrer Höhe, dem Gewicht der Knoten oder der Anordnung der Wurzel balanciert sein.
• 

  Binärbaum mit Knotentypen

• 

  balancierter Binärbaum

• 

  Binomial-Heap mit 13 Elementen. Die Schlüssel der Väter sind höchstens so groß wie die Schlüssel ihrer Kinder.

• 

  Raupenbaum (caterpillar tree)

• 

  Die Sterngraphen $S_{3}$, $S_{4}$, $S_{5}$ und $S_{6}$

Zeichnen von Bäumen

Die grafische Ausgabe eines Baums ist ein nicht triviales Problem. Allgemein gilt, dass jeder Baum planar, das heißt ohne Überschneidungen der Kanten gezeichnet werden kann. Je nach Anwendungszweck gibt es weitere Wünsche an die Art der Ausgabe:

• alle Kanten sind gerade Linien
• alle Knoten haben ganzzahlige Koordinaten
• möglichst kleiner Platzbedarf bei möglichst ästhetischem Ergebnis
• alle Kanten vom Elternelement zum Kind streng monoton fallend

Es gibt verschiedene Algorithmen, deren Ergebnisse recht verschieden aussehen. Meist lösen sie nur einige, aber nicht alle Wünsche an die Ausgabe. Bekannte Algorithmen sind die HV-Bäume und der Algorithmus von Walker.

Anzahl von Bäumen

Es gibt $n^{n-2}$ verschiedene bezeichnete Bäume mit $n$ Knoten. Diese Aussage ist als Cayley-Formel bekannt. Einen einfachen Beweis liefert der Prüfer-Code, der eine Bijektion zwischen allen möglichen Codes der Länge $n-2$ und allen bezeichneten Bäumen auf $n$ Knoten ermöglicht.

Spannbäume

Jeder ungerichtete, zusammenhängende Graph enthält einen ihn aufspannenden Baum als Teilgraphen. Minimale Spannbäume haben eine möglichst kleine Anzahl von Kanten oder eine möglichst kleine Summe der Kantengewichte. Die Berechnung minimaler Spannbäume findet direkte Anwendung in der Praxis, beispielsweise für die Erstellung von kostengünstigen zusammenhängenden Netzwerken, wie beispielsweise Telefonnetze oder elektrische Netze.

Verallgemeinerungen

Wald

Ein Wald ist ein ungerichteter Graph, dessen Zusammenhangskomponenten Bäume sind.

k-Baum

Ein ungerichteter Graph heißt $k$-Baum, wenn er wie folgt rekursiv erzeugbar ist:

• Der vollständige Graph $K_{k}$ ist ein $k$-Baum.
• Fügt man zu einem $k$-Baum $G$ einen neuen Knoten $v$ hinzu, indem man $v$ mit allen Knoten einer Clique der Größe $k$ aus $G$ verbindet, so ist dieser neue Graph ebenfalls ein $k$-Baum.

Ein partieller $k$-Baum entsteht durch die Entfernung von Kanten aus einem $k$-Baum: Ist $G=(V,E)$ ein $k$-Baum, so ist $H=(V,F)$ mit $F\subseteq E$ ein partieller $k$-Baum.

Durch die angegebene Definition haben partielle k-Bäume immer mindestens k Knoten, was nicht immer wünschenswert ist. Darum gibt es auch die folgende Definition:

• Ein partieller k-Baum ist ein Teilgraph eines k-Baumes.

Eine weitere Eigenschaft ist, dass die Menge der partiellen k-Bäume gleich der Menge der Graphen mit Baumweite höchstens k ist.

Siehe auch

• Baum (Datenstruktur)
• Baumweite
• Nested Sets
• Suchbaum

Literatur

• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme. Springer-Verlag, Berlin/ Heidelberg 2010, ISBN 978-3-642-04499-1.
• Sven Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 3. Auflage. Springer Vieweg Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2.

Siehe auch: Literatur zur Graphentheorie

Weblinks

 Commons: Baumstrukturen – Sammlung von Bildern, Videos und Audiodateien