Blätter und innere Knoten in der Graphentheorie
Beispiele
Ungerichteter Baum
Ungerichteter Baum
Gerichteter Baum (hier: Out-Tree)
Gerichteter Baum
Legende
Blatt
Innerer Knoten
Wurzel ◉ oder ◎

In der Graphentheorie werden bei einem Baum die Knoten mit genau einem Nachbarn als Blatt oder Endknoten (engl. leaf) und die Knoten mit mehr als einem Nachbarn als innerer Knoten oder Nicht-Endknoten (engl. inner vertex) bezeichnet. Die Einordnung von Wurzeln und isolierten Knoten hängt von der jeweiligen Definition ab.

Inhaltsverzeichnis

Definition

Übliche Definitionen von Blättern und innereren Knoten in einem Baum sind beispielsweise:

  • „Die Ecken [Knoten] vom Grad 1 eines Baumes sind seine Blätter“ (Diestel, 2006, Seite 14)[1]
  • „Die Knoten eines Baumes vom Grad 1 werden Blätter genannt, die Knoten vom Grad größer als 1 heißen innere Knoten“ (Meinel und Mundhenk, 2006, Seite 260)[2]
  • „Eine Ecke mit Ausgangsgrad 0 nennt man ein Blatt des Baumes. Die anderen Ecken nennt man innere Ecken“ (Turau, 2004, Seite 53)[3]

Der genaue Wortlaut hängt unter anderem davon ab, ob die Definition für gerichtete Bäume (also Bäume mit einer Wurzel) oder für ungerichtete Bäume gelten soll. Beim gerichteten Baum wird die Wurzel oft als Sonderfall von der Definition ausgenommen. Ebenso gelten die meisten Definitionen nicht für den Sonderfall eines isolierten Knotens, also eines Baumes, der lediglich aus einem Knoten besteht.

Sonderfälle

Je nachdem, ob isolierte Knoten und Wurzeln als Blatt aufgefasst werden (und ggf. Wurzeln als innere Knoten) oder als Sonderfall, sind folgende Definitionen möglich. Für ungerichtete Bäume ist nur die erste Zeile relevant. Der Sonderfall isolierter Knoten lässt sich beispielsweise dadurch eliminieren, indem gefordert wird, dass ein Baum aus mindestens zwei Knoten bestehen muss.

Isolierter Knoten (bzw. Wurzel)
Blatt Kein Blatt
Wurzel mit
Ausgangsgrad 1
Blatt Ein Blatt ist ein Knoten vom Grad kleiner als 2. Alle anderen Knoten sind innere Knoten. Ein Blatt ist ein Knoten vom Grad 1. Knoten vom Grad größer als 1 sind innere Knoten.
Innerer Knoten Ein Blatt ist ein Knoten vom Ausgangsgrad 0. Alle anderen Knoten sind innere Knoten. Ein Blatt ist ein Knoten mit Ausgangsgrad 0 und Eingangsgrad 1. Ein innerer Knoten ist ein Knoten mit Ausgangsgrad größer 0.
Sonderfall Ein Blatt ist ein Knoten mit Ausgangsgrad 0. Alle anderen Knoten außer der Wurzel sind innere Knoten. Ein Blatt ist ein Knoten vom Grad 1. Alle anderen Knoten sind innere Knoten. Die Wurzel ist von dieser Definition ausgenommen.

Geschichte

Bäume als mathematische Strukturen wurde 1857 von Arthur Cayley eingeführt.[4][5] Cayley geht dabei lediglich auf gewurzelte Bäume ein. Er unterscheidet zunächst drei Typen von Knoten („either the root itself, or proper knots or the extremities of the free branches“)[4] und später die zwei Typen „terminal knot“ (Blatt) und „non-terminal knot“ (innerer Knoten). Sein zweiter Artikel zur Theorie der Bäume enthält eine Auflistung aller möglichen Bäume mit ein, zwei, drei bzw. vier Blättern.[5]

Mögliche Bäume mit ein bis vier Blättern (Cayley, 1859)

.

Für die Anzahl der Bäume mit m Blättern leitet er eine Formel her, die Folge A000670 in OEIS entspricht.

Quellen und weiterführende Literatur

  1. Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 3-540-21391-0.
  2. Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik. 3. Auflage. Teubner, 2006, ISBN 3-8351-0049-1.
  3. Volker Turau: Algorithmische Graphentheorie. 2. Auflage. Oldenbourg, 2004, ISBN 3-486-20038-0.
  4. a b Arthur Cayley (1857): On the Theory of Analytical Forms called Trees. In: Philosophical Magazine, Band 13, S. 172-176 (Reprint in: The Collected Mathematical Papers of Arthur Cayley. Band 3, Cambridge University Press, Cambridge, 1890, S. 242-246; digitalisiert beim Internet Archive).
  5. a b Arthur Cayley (1859): On the Theory of Analytical Forms called Trees. Second Part. In: Philosophical Magazine, Band 17, S. 374-378. (Reprint in: The Collected Mathematical Papers of Arthur Cayley. Band 4, Cambridge University Press, Cambridge, 1891, Seite 112-115; digitalisiert beim Internet Archive).

Weblinks

Wiktionary Wiktionary: Blatt – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • In-order — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • In-Tree — Ein In Tree ist in der Graphentheorie ein spezieller Graph, genauer ein gewurzelter Baum. Definition Ein In Tree ist ein gerichteter Graph mit einem ausgezeichneten Knoten, der so genannten Wurzel, für den im Gegensatz zu Out Trees gilt, dass die …   Deutsch Wikipedia

  • Blatt (Graphentheorie) — Beispiele Ungerichteter Baum Gerichteter Baum (hier: Out Tree) …   Deutsch Wikipedia

  • Innerer Knoten — Beispiele Ungerichteter Baum Gerichteter Baum (hier: Out Tree) …   Deutsch Wikipedia

  • Baum (Graphentheorie) — 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 Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Binary Tree — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Binäre Bäume — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Binärer Baum — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Linearisierung von Binärbäumen — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

  • Linkes Kind — Ein voller, aber nicht vollständiger Binärbaum Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen gewurzelten Baum, bei dem jeder Knoten höchstens zwei Kindknoten besitzt …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”