TreeEdit

Ein Baum ist ein ungerichteter Graph G, der eine der folgenden äquivalenten Bedingungen erfüllt:

• G ist verbunden und azyklisch (enthält keine Zyklen).
• G ist azyklisch, und ein einfacher Zyklus wird gebildet, wenn eine Kante zu G hinzugefügt wird.
• G ist verbunden, würde aber getrennt, wenn eine einzelne Kante von G entfernt wird.
• G ist verbunden und der vollständige 3-Scheitelpunkt-Graph K3 ist kein Nebenwert von G.
• Zwei beliebige Scheitelpunkte in G können durch einen eindeutigen einfachen Pfad verbunden werden.

Wenn G endlich viele Eckpunkte hat, sagen wir n, dann sind die obigen Aussagen auch äquivalent zu einer der folgenden Bedingungen:

• G ist verbunden und hat n − 1 Kanten.
• G ist verbunden, und jeder Untergraph von G enthält mindestens einen Scheitelpunkt mit null oder einer einfallenden Kante. (Das heißt, G ist verbunden und 1-entartet.)
• G hat keine einfachen Zyklen und hat n − 1 Kanten.

Wie anderswo in der Graphentheorie wird der Graph der Ordnung Null (Graph ohne Eckpunkte) im Allgemeinen nicht als Baum betrachtet: während es als Graph leer verbunden ist (zwei beliebige Scheitelpunkte können durch einen Pfad verbunden sein), ist es in der algebraischen Topologie im Gegensatz zu nicht leeren Bäumen nicht 0-verbunden (oder sogar (-1) -verbunden) und verletzt die Beziehung „ein Scheitelpunkt mehr als Kanten“. Es kann jedoch als ein Wald betrachtet werden, der aus null Bäumen besteht.

Ein innerer Scheitelpunkt (oder innerer Scheitelpunkt oder Verzweigungsscheitelpunkt) ist ein Scheitelpunkt des Grades mindestens 2. In ähnlicher Weise ist ein äußerer Scheitelpunkt (oder äußerer Scheitelpunkt, terminaler Scheitelpunkt oder Blatt) ein Scheitelpunkt des Grades 1.

Ein irreduzibler Baum (oder serienreduzierter Baum) ist ein Baum, in dem es keinen Scheitelpunkt des Grades 2 gibt (aufgezählt in der Sequenz A000014 im OEIS).

ForestEdit

Ein Wald ist ein ungerichteter Graph, in dem zwei beliebige Eckpunkte durch höchstens einen Pfad verbunden sind. Äquivalent ist ein Wald ein ungerichteter azyklischer Graph, dessen alle verbundenen Komponenten Bäume sind; mit anderen Worten, der Graph besteht aus einer disjunkten Vereinigung von Bäumen. Als Sonderfälle sind der Graph der Ordnung Null (ein Wald, der aus null Bäumen besteht), ein einzelner Baum und ein kantenloser Graph Beispiele für Wälder.Da für jeden Baum V – E = 1 ist, können wir leicht die Anzahl der Bäume zählen, die sich in einem Wald befinden, indem wir die Differenz zwischen den Gesamtscheitelpunkten und den Gesamtkanten subtrahieren. TV – TE = Anzahl der Bäume in einem Wald.

PolytreeEdit

Ein Polybaum (oder gerichteter Baum oder orientierter Baum oder einfach verbundenes Netzwerk) ist ein gerichteter azyklischer Graph (DAG), dessen zugrunde liegender ungerichteter Graph ein Baum ist. Mit anderen Worten, wenn wir seine gerichteten Kanten durch ungerichtete Kanten ersetzen, erhalten wir einen ungerichteten Graphen, der sowohl verbunden als auch azyklisch ist.Einige Autoren beschränken den Ausdruck „gerichteter Baum“ auf den Fall, dass die Kanten alle auf einen bestimmten Scheitelpunkt gerichtet sind oder alle von einem bestimmten Scheitelpunkt weg gerichtet sind (siehe Arboreszenz).

PolyforestEdit

Ein Polyforest (oder gerichteter Wald oder orientierter Wald) ist ein gerichteter azyklischer Graph, dessen zugrunde liegender ungerichteter Graph ein Wald ist. Mit anderen Worten, wenn wir seine gerichteten Kanten durch ungerichtete Kanten ersetzen, erhalten wir einen ungerichteten Graphen, der azyklisch ist.

Einige Autoren beschränken den Ausdruck „gerichteter Wald“ auf den Fall, dass die Kanten jeder verbundenen Komponente alle auf einen bestimmten Scheitelpunkt gerichtet sind oder alle von einem bestimmten Scheitelpunkt weg gerichtet sind (siehe Verzweigung).

Verwurzelter Baumbearbeiten

Ein verwurzelter Baum ist ein Baum, in dem ein Scheitelpunkt als Wurzel bezeichnet wurde. Den Rändern eines bewurzelten Baumes kann eine natürliche Orientierung zugewiesen werden, entweder weg von oder in Richtung der Wurzel, in welchem Fall die Struktur zu einem gerichteten bewurzelten Baum wird. Wenn ein gerichteter verwurzelter Baum eine Orientierung von der Wurzel weg hat, wird er als Arboreszenz oder Out-Baum bezeichnet; Wenn es eine Orientierung zur Wurzel hat, wird es als Anti-Arboreszenz oder In-Baum bezeichnet. Die Baumordnung ist die partielle Ordnung an den Eckpunkten eines Baumes mit u < v genau dann, wenn der eindeutige Pfad von der Wurzel zu v durch u . Ein verwurzelter Baum T, der ein Untergraph eines Graphen G ist, ist ein normaler Baum, wenn die Enden jedes T-Pfades in G in dieser Baumordnung vergleichbar sind (Diestel 2005, S. 15). Verwurzelte Bäume, oft mit zusätzlicher Struktur wie der Reihenfolge der Nachbarn an jedem Scheitelpunkt, sind eine wichtige Datenstruktur in der Informatik; siehe Baumdatenstruktur.

In einem Kontext, in dem Bäume eine Wurzel haben sollen, wird ein Baum ohne eine bestimmte Wurzel als freier Baum bezeichnet.

Ein beschrifteter Baum ist ein Baum, in dem jeder Scheitelpunkt eine eindeutige Bezeichnung erhält. Die Eckpunkte eines beschrifteten Baums auf n Eckpunkten erhalten typischerweise die Beschriftungen 1, 2, …, n. Ein rekursiver Baum ist ein beschrifteter Wurzelbaum, bei dem die Scheitelpunktbeschriftungen die Baumreihenfolge respektieren (dh., wenn u < v für zwei Eckpunkte u und v , dann ist die Beschriftung von u kleiner als die Beschriftung von v).

In einem verwurzelten Baum ist das übergeordnete Element eines Scheitelpunkts v der Scheitelpunkt, der mit v auf dem Pfad zur Wurzel verbunden ist; Jeder Scheitelpunkt hat ein eindeutiges übergeordnetes Element mit Ausnahme der Wurzel, die kein übergeordnetes Element hat. Ein Kind eines Scheitelpunkts v ist ein Scheitelpunkt, dessen Elternteil v ist. Ein Aszendent eines Scheitelpunkts v ist jeder Scheitelpunkt, der entweder der Elternteil von v oder (rekursiv) der Aszendent des Elternteils von v ist. Ein Nachkomme eines Scheitelpunkts v ist jeder Scheitelpunkt, der entweder das Kind von v oder (rekursiv) der Nachkomme eines der Kinder von v ist. Ein interner Scheitelpunkt ist ein Scheitelpunkt, der kein Blatt ist.

Die Höhe eines Scheitelpunkts in einem verwurzelten Baum ist die Länge des längsten Abwärtspfades von diesem Scheitelpunkt zu einem Blatt. Die Höhe des Baumes ist die Höhe der Wurzel. Die Tiefe eines Scheitelpunkts ist die Länge des Pfades zu seiner Wurzel (Wurzelpfad). Dies wird häufig bei der Manipulation der verschiedenen selbstausgleichenden Bäume, insbesondere der AVL-Bäume, benötigt. Die Wurzel hat die Tiefe Null, die Blätter haben die Höhe Null und ein Baum mit nur einem einzigen Scheitelpunkt (daher sowohl Wurzel als auch Blatt) hat die Tiefe und Höhe Null. Herkömmlicherweise hat ein leerer Baum (ein Baum ohne Scheitelpunkte, falls solche zulässig sind) Tiefe und Höhe -1.

Ein k-ary-Baum ist ein verwurzelter Baum, in dem jeder Scheitelpunkt höchstens k Kinder hat. 2-ary Bäume werden oft binäre Bäume genannt, während 3-ary Bäume manchmal ternäre Bäume genannt werden.

Ordered treeEdit

Ein geordneter Baum (oder Platane) ist ein verwurzelter Baum, in dem eine Reihenfolge für die Kinder jedes Scheitelpunkts angegeben ist. Dies wird als „Platanenbaum“ bezeichnet, da eine Anordnung der untergeordneten Elemente einer Einbettung des Baums in die Ebene entspricht, wobei die Wurzel oben und die untergeordneten Elemente jedes Scheitelpunkts niedriger als dieser Scheitelpunkt sind. Wenn bei einer Einbettung eines verwurzelten Baumes in die Ebene eine Richtung von Kindern festgelegt wird, z. B. von links nach rechts, ergibt eine Einbettung eine Reihenfolge der Kinder. Umgekehrt können bei einem geordneten Baum und herkömmlichem Zeichnen der Wurzel oben die untergeordneten Scheitelpunkte in einem geordneten Baum von links nach rechts gezeichnet werden, was zu einer im Wesentlichen eindeutigen planaren Einbettung führt.