Blätter und innere Knoten in der Graphentheorie

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.

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

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]

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.