In der Mathematik, mehr spezifisch Graph-Theorie, ist ein Baum ein ungeleiteter Graph, in dem irgendwelche zwei Scheitelpunkte durch genau einen einfachen Pfad verbunden werden. Mit anderen Worten ist jeder verbundene Graph ohne Zyklen ein Baum. Ein Wald ist eine zusammenhanglose Vereinigung von Bäumen.

Die verschiedenen Arten von Datenstrukturen gekennzeichnet als Bäume in der Informatik sind zu Bäumen in der Graph-Theorie gleichwertig, obwohl solche Datenstrukturen allgemein eingewurzelte Bäume sind, und zusätzliche Einrichtung von Zweigen haben können.

Definitionen

Ein Baum ist ein ungeleiteter einfacher Graph G, der einige der folgenden gleichwertigen Bedingungen befriedigt:

• G wird verbunden und hat keine Zyklen.
• G hat keine Zyklen, und ein einfacher Zyklus wird gebildet, wenn ein Rand zu G hinzugefügt wird.
• G wird verbunden, aber wird nicht verbunden, wenn ein einzelner Rand von G entfernt wird.
• G wird verbunden, und der ganze 3-Scheitelpunkte-Graph ist nicht ein Minderjähriger von G.
• Irgendwelche zwei Scheitelpunkte in G können durch einen einzigartigen einfachen Pfad verbunden werden.

Wenn G begrenzt viele Scheitelpunkte hat, sagen Sie n von ihnen, dann sind die obengenannten Behauptungen auch zu einigen der folgenden Bedingungen gleichwertig:

• G wird verbunden und hat n − 1 Ränder.
• G hat keine einfachen Zyklen und hat n − 1 Ränder.

Ein nicht zu vereinfachender (oder Reihe-reduziert) Baum ist ein Baum, in dem es keinen Scheitelpunkt des Grads 2 gibt.

Ein Wald ist ein ungeleiteter Graph, alle sind dessen verbundenen Bestandteile Bäume; mit anderen Worten besteht der Graph aus einer zusammenhanglosen Vereinigung von Bäumen. Gleichwertig ist ein Wald ein ungeleiteter Graph ohne Zyklen. Als spezielle Fälle, ein leerer Graph, ein einzelner Baum, und der getrennte Graph auf einer Reihe von Scheitelpunkten (d. h. der Graph mit diesen Scheitelpunkten, der keine Ränder hat), sind alle Beispiele von Wäldern.

Der Begriff Hecke bezieht sich manchmal auf eine bestellte Folge von Bäumen.

Ein Polybaum oder orientierter Baum sind ein geleiteter Graph mit am grössten Teil eines ungeleiteten Pfads zwischen irgendwelchen zwei Scheitelpunkten. Mit anderen Worten ist ein Polybaum ein geleiteter acyclic Graph, für den es keine ungeleiteten Zyklen auch gibt.

Ein geleiteter Baum ist ein geleiteter Graph, der ein Baum sein würde, wenn die Richtungen an den Rändern ignoriert würden. Einige Autoren schränken den Ausdruck auf den Fall ein, wo die Ränder alle zu einem besonderen Scheitelpunkt geleitet werden, oder alle weg von einem besonderen Scheitelpunkt befohlen haben (sieh arborescence).

Ein Baum wird einen eingewurzelten Baum genannt, wenn ein Scheitelpunkt die Wurzel benannt worden ist, in welchem Fall die Ränder eine natürliche Orientierung, zu oder weg von der Wurzel haben. Die Baumordnung ist die teilweise Einrichtung auf den Scheitelpunkten eines Baums mit u  v, wenn, und nur wenn der einzigartige Pfad von der Wurzel bis v u durchführt. Ein eingewurzelter Baum, der ein Subgraph von einem Graphen G ist, ist ein normaler Baum, wenn die Enden jedes Randes in G in dieser Baumordnung vergleichbar sind, wann auch immer jene Enden Scheitelpunkte des Baums sind. Eingewurzelte Bäume, häufig mit der zusätzlichen Struktur wie Einrichtung der Nachbarn an jedem Scheitelpunkt, sind eine Schlüsseldatenstruktur in der Informatik; sieh Baumdatenstruktur. In einem Zusammenhang, wo Bäume eine Wurzel haben sollen, wird ein Baum ohne jede benannte Wurzel einen freien Baum genannt.

In einem eingewurzelten Baum ist der Elternteil eines Scheitelpunkts der Scheitelpunkt, der damit auf dem Pfad zur Wurzel verbunden ist; jeder Scheitelpunkt außer der Wurzel hat einen einzigartigen Elternteil. Ein Kind eines Scheitelpunkts v ist ein Scheitelpunkt, dessen v der Elternteil ist. Ein Blatt ist ein Scheitelpunkt ohne Kinder.

Ein etikettierter Baum ist ein Baum, in dem jeder Scheitelpunkt ein einzigartiges Etikett gegeben wird. Die Scheitelpunkte eines etikettierten Baums auf n Scheitelpunkten werden normalerweise die Etiketten 1, 2, …, n gegeben. Ein rekursiver Baum ist ein etikettierter eingewurzelter Baum, wo die Scheitelpunkt-Etiketten die Baumordnung respektieren (d. h., wenn u

• Für irgendwelche drei Scheitelpunkte in einem Baum haben die drei Pfade zwischen ihnen genau einen Scheitelpunkt gemeinsam.

Enumeration

Etikettierte Bäume

Die Formel von Cayley stellt fest, dass es n Bäume auf etikettierten Scheitelpunkten von n gibt. Es kann durch die erste Vertretung bewiesen werden, dass die Zahl von Bäumen mit Scheitelpunkten 1,2..., n, Grade d, d..., d beziehungsweise, der multinomial Koeffizient ist

:

Ein alternativer Beweis verwendet Folgen von Prüfer.

Die Formel von Cayley ist der spezielle Fall von ganzen Graphen in einem allgemeineren Problem, Überspannen-Bäume in einem ungeleiteten Graphen aufzuzählen, der durch den Matrixbaumlehrsatz gerichtet wird. Wie man gezeigt hat, ist das ähnliche Problem, alle Subbäume unabhängig von der Größe aufzuzählen, #P-complete im allgemeinen Fall gewesen.

Unetikettierte Bäume

Das Aufzählen der Zahl unetikettierter freier Bäume ist ein härteres Problem. Keine geschlossene Formel für die Nummer t (n) von Bäumen mit n Scheitelpunkten bis zum Graph-Isomorphismus ist bekannt. Die ersten paar Werte von t (n) sind:

: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159....

bewiesen die asymptotische Schätzung:

:

mit C = 0.534949606 … und α = 2.99557658565 …. (Hier, Mittel das.) Das ist eine Folge seiner asymptotischen Schätzung für die Zahl von unetikettierten eingewurzelten Bäumen mit n Scheitelpunkten:

:

mit D = 0.43992401257 … und α dasselbe als oben (vgl, Junge. 2.3.4.4 und, Junge. VII.5).

Typen von Bäumen

Ein Sterngraph ist ein Baum, der irgendein Auftrag n &le hat; 2, oder besteht aus einem einzelnen inneren Knoten (und n − 1 Blätter). Mit anderen Worten ist ein Sterngraph des Auftrags n ein Baum des Auftrags n mit so vielen Blättern wie möglich. Sein Diameter ist höchstens 2.

Ein Baum mit zwei Endscheitelpunkten (das geringstmögliche) ist ein Pfad-Graph. Wenn alle Knoten in einem Baum innerhalb der Entfernung einer eines Hauptpfad-Subgraphen sind, dann ist der Baum ein Raupe-Baum. Wenn alle Knoten innerhalb der Entfernung zwei eines Hauptpfad-Subgraphen sind, dann ist der Baum ein Hummer.

Siehe auch

• Entscheidungsbaum
• Pseudowald
• Baumstruktur
• Baumdatenstruktur
• Uneingewurzelter binärer Baum

.

• Donald E. Knuth. Die Kunst des Computerprogrammierbands 1: Grundsätzliche Algorithmen. Addison-Wesley Professional; 3. Ausgabe (am 14. November 1997).

. .