imported>Aka: /* Geschichte */ https

2021-01-17T09:01:26Z

Geschichte: https

Neue Seite

{| class="toccolours float-right" style="font-size:90%;"
|- class="hintergrundfarbe6" style="font-size:105%;"
! colspan="2" | Beispiele
|- class="hintergrundfarbe5"
! colspan="2" | [[Ungerichteter Baum]]
|-
| colspan="2" | [[Datei:undirected-tree.svg|frameless|center|Ungerichteter Baum]]
|- class="hintergrundfarbe5"
! colspan="2" | [[Gewurzelter Baum|Gerichteter Baum]] (hier: [[Out-Tree]])
|-
| colspan="2" | [[Datei:directed-tree.svg|frameless|center|Gerichteter Baum]]
|- class="hintergrundfarbe5"
! colspan="2" | Legende
|-
| '''Blatt''' || ○
|-
| '''Innerer Knoten''' || ●
|-
| '''Wurzel''' || ◉ oder ◎
|}

In der [[Graphentheorie]] werden bei einem [[Baum (Graphentheorie)|Baum]] die [[Knoten (Graphentheorie)|Knoten]] mit genau einem [[Nachbarschaft (Graphentheorie)|Nachbarn]] als '''Blatt''' oder ''Endknoten'' ({{EnS|''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'' ({{EnS|''inner vertex''}}) bezeichnet. Die Einordnung von [[Wurzel (Graphentheorie)|Wurzel]]n und [[Knoten (Graphentheorie)#Spezielle Knoten|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.“<ref>{{BibISBN|9783642149115|Seite=14}}</ref>
* „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).<ref name="Meinel2006">{{Literatur|Autor=Christoph Meinel, Martin Mundhenk|Titel=Mathematische Grundlagen der Informatik|Auflage=3.|Jahr=2006|Verlag=Teubner|ISBN=3-8351-0049-1}}</ref>
* „Eine Ecke mit Ausgangsgrad 0 nennt man ein ''Blatt'' des Baumes. Die anderen Ecken nennt man ''innere Ecken''“ (Turau, 2004, Seite 53).<ref name="Turau2004">{{Literatur|Autor=Volker Turau|Titel=Algorithmische Graphentheorie|Auflage=2.|Jahr=2004|Verlag=Oldenbourg|ISBN=3-486-20038-0}}</ref>

Der genaue Wortlaut hängt unter anderem davon ab, ob die Definition für [[gerichteter Baum|gerichtete Bäume]] (also Bäume mit einer Wurzel) oder für [[Ungerichteter Baum|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.

{| class="wikitable"
|-
! colspan=2 rowspan=2 |
! colspan=2 class="hintergrundfarbe6" | Isolierter Knoten bzw. Wurzel
|-
! class="hintergrundfarbe5" | Blatt
! class="hintergrundfarbe5" | Kein Blatt
|-
! rowspan=3 class="hintergrundfarbe6" | Wurzel mit<br>Ausgangsgrad 1
! class="hintergrundfarbe5" | 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.''
|-
! class="hintergrundfarbe5" | 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.
|-
! class="hintergrundfarbe5" | 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.<ref name="Cayley1857">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 [https://archive.org/details/collmathpapers03caylrich beim Internet Archive]).</ref><ref name="Cayley1859">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 [https://archive.org/details/collmathpapers02caylrich beim Internet Archive]).</ref> 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“)<ref name="Cayley1857"/> 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.<ref name="Cayley1859"/>

[[Datei:Caylrich-first-trees2.png|mini|400px|center|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 {{OEIS|A000670}} entspricht.

== Quellen und weiterführende Literatur ==
<references/>

== Weblinks ==
{{Wiktionary|Blatt}}

{{DEFAULTSORT:Blatter und innere Knoten in der Graphentheorie}}
[[Kategorie:Grundbegriff (Graphentheorie)]]

[[en:Leaf node]]
[[zh:树 (数据结构)#术语]]

Blätter und innere Knoten in der Graphentheorie - Versionsgeschichte

imported>Aka: /* Geschichte */ https