Blatt (Graphentheorie)

Blatt (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


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Blatt — bezeichnet einen Teil einer Pflanze, siehe Blatt (Pflanze) ein Stück Papier, siehe Papier#Blattbildung eine Zeitschrift oder Zeitung, siehe Periodikum eine Informationsschrift als Loseblatt, siehe Flugblatt einen Abzug einer künstlerischen… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Inzidenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schlinge (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Tiefe (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Valenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Glossar Graphentheorie — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel… …   Deutsch Wikipedia

  • Blätter und innere Knoten in der Graphentheorie — Beispiele Ungerichteter Baum Gerichteter Baum (hier: Out Tree) …   Deutsch Wikipedia

Share the article and excerpts

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