Blätter und innere Knoten in der Graphentheorie - LinkFang.de





Blätter und innere Knoten in der Graphentheorie


Beispiele
Ungerichteter Baum
Gerichteter Baum (hier: Out-Tree)
Legende
Blatt
Innerer Knoten
Wurzel ◉ oder ◎

In der Graphentheorie werden bei einem Baum die Knoten mit genau einem Nachbarn als Blatt oder Endknoten (englisch leaf; auch als äußere oder externe Knoten bezeichnet) und die Knoten mit mehr als einem Nachbarn als interner bzw. innerer Knoten oder Nicht-Endknoten (englisch inner vertex) bezeichnet. Die Einordnung von Wurzeln und isolierten Knoten hängt von der jeweiligen Definition ab.

Definition

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

  • „Die Ecken [Knoten] vom Grad 1 eines Baumes sind seine Blätter.“[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 Baums, 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]

.

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. 4. Auflage. Springer, 2010, ISBN 978-3-642-14911-5, S. 14.
  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. 4,0 4,1 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. 5,0 5,1 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: Blatt – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
zh:树 (数据结构)#术语

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Blätter und innere Knoten in der Graphentheorie (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.