Hauptmenü öffnen

Baum (Graphentheorie)

Graph, mit dem sich eine Monohierarchie modellieren lässt

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.

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

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

Inhaltsverzeichnis

DefinitionenBearbeiten

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

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 (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   aus stark zusammenhängender kreisfreier Graph. Der den starken Zusammenhang definierende Knoten   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   fassen und „schütteln“ – die Schwerkraft gibt allen Kanten eine definierte Richtung von   weg, die aus dem ursprünglich ungerichteten Baum einen gewurzelten macht mit   als Wurzel.

Den   Kanten eines ungerichteten Baums kann man   verschiedene Richtungen geben und so   gerichtete Bäume ableiten. Genau   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äumeBearbeiten

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

Äquivalente Charakterisierungen von BäumenBearbeiten

Ein endlicher Graph   mit   Knoten und   Kanten kann durch folgende äquivalente Aussagen als Baum definiert werden:

  • Zwischen je zwei Knoten von   gibt es genau einen Pfad.
  •   ist zusammenhängend und enthält keinen Kreis
  •   ist leer oder   ist zusammenhängend und es gilt  . (Es gibt immer eine Kante weniger als Knoten.)
  •   ist leer oder   enthält keinen Kreis und es gilt  .
  •   ist minimal zusammenhängend, das heißt   ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt.
  •   ist maximal azyklisch, das heißt   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.

Zeichnen von BäumenBearbeiten

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äumenBearbeiten

Es gibt   verschiedene bezeichnete Bäume mit   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   und allen bezeichneten Bäumen auf   Knoten ermöglicht.

SpannbäumeBearbeiten

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.

VerallgemeinerungenBearbeiten

WaldBearbeiten

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

k-BaumBearbeiten

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

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

Ein partieller  -Baum entsteht durch die Entfernung von Kanten aus einem  -Baum: Ist   ein  -Baum, so ist   mit   ein partieller  -Baum.[1][2][3][4]

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:

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

Siehe auchBearbeiten

AnmerkungenBearbeiten

  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.

LiteraturBearbeiten

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

WeblinksBearbeiten

  Commons: Baumstrukturen – Sammlung von Bildern, Videos und Audiodateien

EinzelnachweiseBearbeiten

  1. 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.
  2. Sven Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner Verlag, 2012, ISBN 978-3-8348-2264-2.
  3. Daniel Granot: On some optimization problems on k-trees and partial k-trees. In: Discrete Applied Mathematics. Elsevier, 1994.
  4. Janka Chlebı́ková: Partial k-trees with maximum chromatic number. In: Discrete Applied Mathematics. 2002.
  5. XiaoZhou, Shin-ichi Nakano, Takao Nishizeki: Edge-Coloring Partial k-Trees. In: Journal of Algorithms. Nr. 21, 1996, S. 598–617.
  6. Ton Kloks: Treewidth. Springer-Verlag, Berlin/Heidelberg 1994, ISBN 978-3-540-48672-5.
  7. A. Yamaguchi, H. Mamitsuka: Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees. Springer, Berlin / Heidelberg, ISBN 978-3-540-24587-2.
  8. Hans L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth. Hrsg.: Theoretical Computer Science. 1998, S. 1–45.
  9. Jan van Leeuwen: Algorithms and Complexity Theory. In: Handbook of Theoretical Computer Science. vol.A. North Holland, Amsterdam 1990, S. 527–631.