Baum (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 17. Juni 2022 um 10:18 Uhr durch imported>Pacogo7(56134) (lf zush graphenth).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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.[1]

Darstellung aller Bäume[Anm. 1] 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 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 machen 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.

Eigenschaften

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 .
  • 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} gibt es genau einen Pfad.

Zwischen je zwei Knoten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} gibt es mindestens einen Pfad, weil jeder Baum zusammenhängend ist. Gäbe es zwei Knoten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} mit mindestens zwei Pfaden, dann gäbe es zwei Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} auf diesen Pfaden, deren Pfade keinen gemeinsamen inneren Knoten haben (disjunkte Wege), zum Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, v_1, \dots, v_k, v} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, u_1, \dots, u_l, v} . Dann wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, v_1, \dots, v_k, v, u_l, \cdots, u_1, u} ein Kreis von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} im Widerspruch zur Annahme, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ein Baum ist.

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist leer oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist zusammenhängend und es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=n-1} .

Dies lässt sich mit vollständiger Induktion zeigen. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 1} , also einen leeren Graphen mit einem einzelnen Knoten und ohne Kanten, gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=n-1=0} . Nach Induktionsvoraussetzung nehmen wir an, dass die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=n-1} für jeden Baum mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} Knoten gilt. Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ein Graph mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1, v_2, \dots, v_k} die Knoten eines längsten Pfades von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} . Alle Nachbarn von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1} liegen auf diesem Pfad, sonst wäre er nicht der längste Pfad. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_2} ist der einzige Nachbar von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1} , denn sonst würde Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} einen Kreis enthalten. Entfernen wir Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1} und die Kante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (v_1, v_2)} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} , dann erhalten wir einen zusammenhängenden Graphen, denn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_2} ist der einzige Nachbar von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v_1} . Der entstandene Graph hat genau einen Knoten und eine Kante weniger als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-1} Knoten. Nach Induktionsvoraussetzung gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=n-1} , also hat der entstandene Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m-1=n-2} Kanten. Daraus folgt, dass der Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=n-1} Kanten hat.

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist minimal zusammenhängend, das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist zusammenhängend, aber nicht mehr zusammenhängend, sobald man eine beliebige Kante daraus entfernt.

Wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} nach Entfernen der Kante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = (u, v)} immer noch zusammenhängend, dann würde der entstandene Graph einen Pfad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, v_1, \dots, v_k, v} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} enthalten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, v_1, \dots, v_k, v, u} wäre ein Kreis von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} .

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist maximal azyklisch, das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ist kreisfrei, aber jede weitere Kante zwischen zwei beliebigen Knoten erzeugt einen Kreis.

Wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} nach Hinzufügen der Kante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e = (u, v)} immer noch kreisfrei, dann würde Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} keinen Pfad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} enthalten und wäre nicht zusammenhängend im Widerspruch zur Annahme, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Bäumen, mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} als Grad des entfernten Knotens[2]. Entfernt man von einem Baum ein Blatt (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k=1} ), so ist der Rest immer noch ein Baum.[1]
  • Durch Hinzufügen einer Kante zwischen zwei vorhandenen Knoten entsteht im ungerichteten Baum ein Kreis.[3]

Spezielle Bäume

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

  • den leeren Graphen. Dieser enthält keine Knoten und Kanten.
  • den isolierten Knoten ohne Kanten
  • lineare Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_n} . Die inneren Knoten haben jeweils genau zwei Nachbarn.
  • Sterngraphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_{1,n}} . Diese enthalten einen inneren Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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):
  • 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_4} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_5} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.

    Kombinatorik

    Es gibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} verschiedene bezeichnete Bäume mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-2} und allen bezeichneten Bäumen auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Knoten ermöglicht.

    Wenn die Knoten nicht nummeriert sind, isomorphe Bäume (siehe Isomorphie von Graphen) also nicht mitgezählt werden, verhält sich diese Anzahl asymptotisch wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C \cdot \alpha^n \cdot n^{-\tfrac{5}{2}}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C \approx 0,534949606} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha \approx 2,95576528565} , wie Richard Otter im Jahr 1948 bewies.[4] Eine genaue mathematische Formel ist nicht bekannt.

    Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \leq 12} :[5]

    Anzahl der Bäume
    n mit nummerierten Knoten ohne nummerierte Knoten
    1 1 1
    2 1 1
    3 3 1
    4 16 2
    5 125 3
    6 1.296 6
    7 16.807 11
    8 262.144 23
    9 4.782.969 47
    10 100.000.000 106
    11 2.357.947.691 235
    12 61.917.364.224 551

    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 Telefonnetzen oder elektrischen Netzen.

    Verallgemeinerungen

    Wald

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

    k-Baum

    Ein ungerichteter Graph heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum, wenn er wie folgt rekursiv erzeugbar ist:

    • Der vollständige Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_k} ist ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum.
    • Fügt man zu einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} einen neuen Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} hinzu, indem man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} mit allen Knoten einer Clique der Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} verbindet, so ist dieser neue Graph ebenfalls ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum.

    Ein partieller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum entsteht durch die Entfernung von Kanten aus einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum: Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G = (V, E)} ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H = (V, F)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F \subseteq E} ein partieller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Baum.[6][7][8][9]

    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.[13][14]

    Programmierung

    Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines ungerichteten Graphen mit Adjazenzlisten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die auf der Konsole ausgibt, ob der Graph ein Baum ist.[15]

    using System;
using System.Collections.Generic;
using System.Linq;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
	public int index;
	public string value;
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten
}

// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	
	// Diese Methode verbindet die Knoten node1 und node2 miteinander.
	public void ConnectNodes(Node node1, Node node2)
	{
		node1.adjacentNodes.Add(node2);
		node2.adjacentNodes.Add(node1);
	}
	
	// Diese rekursive Methode prüft, ob der Graph Zyklen enthält
	public bool IsCyclic(Node node, Dictionary<Node, bool> areConnected, Node parentNode)
	{
		areConnected[node] = true; // Setzt den aktuellen Knoten als durchlaufen
		foreach (Node nextNode in node.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des aktuellen Knotens durchläuft
		{
			if (!areConnected[nextNode]) // Wenn der benachbarten Knoten noch nicht durchlaufen wurde
			{
				if (IsCyclic(nextNode, areConnected, node)) // Rekursiver Aufruf der Methode mit dem benachbarten Knoten als aktuellen Knoten
				{
					return true; // Wenn der rekursive Aufruf true zurückgibt
				}
			}
			else // Wenn der benachbarten Knoten schon durchlaufen wurde ...
			{
				if (nextNode != parentNode) // ... und der benachbarte Knoten nicht der Elternknoten ist, bilden die durchlaufenen Knoten einen Zyklus
				{
					return true;
				}
			}
		}
		return false; // Sonst enthält der Graph keinen Zyklus
	}
	
	// Diese Methode prüft, ob der Graph ein Baum ist.
	public bool IsTree()
	{
		Dictionary<Node, bool> areConnected = new Dictionary<Node, bool>();
		foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
		{
			areConnected.Add(node, false); // Setzt alle Knoten als nicht durchlaufen
		}
		if (IsCyclic(nodes.ElementAt(0), areConnected, null)) // Wenn die Komponente mit dem ersten Knoten Zyklen enthält, false zurückgeben
		{
			return false;
		}
		foreach (Node node in nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
		{
			if (!areConnected[node]) // Wenn ein Knoten nicht verbunden ist, dann false zurückgeben
			{
				return false;
			}
		}
		return true; // Sonst ist der Graph ein Baum
	}
}

class Program
{
	// Hauptmethode, die das Programm ausführt
	public static void Main(string[] args)
	{
		// Deklariert und initialisiert 5 Knoten
		Node node1 = new Node{index = 0, value = "A"};
		Node node2 = new Node{index = 1, value = "B"};
		Node node3 = new Node{index = 2, value = "C"};
		Node node4 = new Node{index = 3, value = "D"};
		Node node5 = new Node{index = 4, value = "E"};
		// Deklariert und initialisiert ein Array mit den Knoten
		Node[] nodes = {node1, node2, node3, node4, node5};
		// Erzeugt einen ungerichteten Graphen
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
		{
			undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
		}
		// Verbindet Knoten des Graphen miteinander
		undirectedGraph.ConnectNodes(node2, node1);
		undirectedGraph.ConnectNodes(node1, node3);
		undirectedGraph.ConnectNodes(node1, node4);
		undirectedGraph.ConnectNodes(node4, node5);
		if (undirectedGraph.IsTree()) // Aufruf der Methode, die prüft, ob der Graph ein Baum ist
		{
			Console.WriteLine("Der Graph ist ein Baum."); // Ausgabe auf der Konsole
		}
		else
		{
			Console.WriteLine("Der Graph ist kein Baum."); // Ausgabe auf der Konsole
		}
		
		Console.ReadLine();
	}
}

    Siehe auch

    Anmerkungen

    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. Es sind nur ungerichtete Bäume dargestellt. Fasst man den obersten Knoten als Wurzel auf, so ergeben sich entsprechend unterschiedliche (heteromorphe) gewurzelte Bäume.

    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.

    Weblinks

    Commons: Baumstrukturen – Sammlung von Bildern, Videos und Audiodateien

    Einzelnachweise

    1. ↑ a b Reinhard Diestel: Graphentheorie. 3., neu bearb. und erw. Auflage. Springer, Berlin 2006, ISBN 3-540-21391-0, S. 14.
    2. ↑ Angelika Steger: Diskrete Strukturen. 2. Auflage. Band 1: Kombinatorik, Graphentheorie, Algebra. Springer, Berlin 2007, ISBN 978-3-540-46660-4, S. 65.
    3. ↑ Stephan Hußmann, Brigitte Lutz-Westphal: Kombinatorische Optimierung erleben : in Studium und Unterricht. 1. Auflage. Vieweg, Wiesbaden 2007, ISBN 978-3-528-03216-6, S. 47.
    4. ↑ Richard Otter: The Number of Trees. In: Annals of Mathematics. 49, Nr. 3, 1948, S. 583–599. doi:10.2307/1969046.
    5. ↑ Folge A000055 in OEIS
    6. ↑ 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.
    7. ↑ Sven Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner Verlag, 2012, ISBN 978-3-8348-2264-2.
    8. ↑ Daniel Granot: On some optimization problems on k-trees and partial k-trees. In: Discrete Applied Mathematics. Elsevier, 1994.
    9. ↑ Janka Chlebı́ková: Partial k-trees with maximum chromatic number. In: Discrete Applied Mathematics. 2002.
    10. ↑ Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki: Edge-Coloring Partial k-Trees. In: Journal of Algorithms. Nr. 21, 1996, S. 598–617.
    11. ↑ Ton Kloks: Treewidth. Springer-Verlag, Berlin/ Heidelberg 1994, ISBN 3-540-48672-0.
    12. ↑ 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 2003, ISBN 3-540-24587-1.
    13. ↑ Hans L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth. In: Theoretical Computer Science. 1998, S. 1–45.
    14. ↑ Jan van Leeuwen: Algorithms and Complexity Theory. In: Handbook of Theoretical Computer Science. vol. A. North Holland, Amsterdam 1990, S. 527–631.
    15. ↑ GeeksforGeeks: Check if a given graph is tree or not
    Abgerufen von „https://de.wikiup.org/index.php?title=Baum_(Graphentheorie)&oldid=223768880“