Baum (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. 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.

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

In der Informatik werden Bäume häufig als Datenstruktur eingesetzt. In diesem Fall werden sie aber anders repräsentiert als allgemeine Graphen. Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen so genannten Wald.

Definitionen[Bearbeiten]

Ungerichteter Baum mit zwei inneren Knoten (blau) und vier Blättern (rot)

Ein (ungerichteter) 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 mit einer Wurzel (rot), zwei inneren Knoten (gelb) und vier Blättern (grün)

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 Ausgangsgrad >0 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 macht mit w als Wurzel.
Den m Kanten eines ungerichteten Baums kann man 2m verschiedene Richtungen geben und so 2m 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.

Spezielle Bäume[Bearbeiten]

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

Äquivalente Charakterisierungen von Bäumen[Bearbeiten]

Ein 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 zusammenhängend und es gilt m=n-1. (Es gibt immer eine Kante weniger als Knoten.)
  • 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.

Bäume als Datenstruktur[Bearbeiten]

Gewurzelte Bäume, insbesondere Out-Trees, werden häufig als Datenstruktur verwendet. Bei beschränkter Ordnung können diese so implementiert werden, dass jeder Knoten einen festen Satz an Variablen oder ein Array für die Referenzen auf seine Kinder enthält. Häufig besitzen die Knoten auch eine Referenz auf ihren Elternknoten (back pointer). Ein Baum unbeschränkter Ordnung kann implementiert werden, indem man statt Arrays dynamische Listen verwendet. In Programmiersprachen ohne dynamische Listen hat sich auch ein Verfahren bewährt, bei dem ein allgemeiner Baum durch einen Binärbaum implementiert wird:

Allgemeiner-baum.png

Die rötliche Linie zeigt dabei den realisierten allgemeinen Baum, während die Pfeile die tatsächlichen Zeigerstrukturen repräsentieren. Das Grundprinzip besteht darin, dass ein Zeiger jeweils auf das am weitesten links stehenden Kind zeigt, während der andere auf den rechten Geschwister-Knoten verweist. Hierbei ist zwar ein direkter Zugriff auf einzelne bestimmte Kind-Knoten nicht mehr möglich, da man sich über die Geschwister voranarbeiten muss. Dafür ist diese Implementierung sehr speichereffizient.

Zeichnen von Bäumen[Bearbeiten]

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 (Horizontal-Vertikal) und der Algorithmus von Walker.

Anzahl von Bäumen[Bearbeiten]

Es gibt n^{n-2} verschiedene bezeichnete Bäume mit n Knoten. Diese Aussage ist als Cayley-Formel bekannt.

Verallgemeinerungen[Bearbeiten]

Wald[Bearbeiten]

Hauptartikel: Wald (Graphentheorie)

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

k-Baum[Bearbeiten]

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.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  • 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.

Weblinks[Bearbeiten]

 Commons: Baumstrukturen – Sammlung von Bildern, Videos und Audiodateien

Quellen[Bearbeiten]

Anmerkungen[Bearbeiten]

  1. Einige der dargestellten Bäume sind isomorph zueinander; nämlich beide Bäume in Fig. 2 sowie in Fig. 3 (von links gezählt) die Bäume 1 und 3 sowie 2 und 4.