132

KAPITEL IV Kombinatorik und Graphen

1. Schlichte Graphen

Graphen sind ein besonders wichtiges Hilfmittel der Informatik. Sie gehören zwar nicht direkt in das Gebiet der algebraischen Grundstrukturen und der linearen Algebra. Sie werden jedoch häufig in Beweisen verwendet, geben Anlaß zur Konstruktion von speziellen Matrizen und sind eng verwandt mit geometrischen und kombinatorischen Problemen und besonderen Abzählungen. Wir wollen daher in diesem Kapitel einige elementare Eigenschaften von Graphen erläutern.

Definition 1.1. Die Menge A ∘ A = {{a, b}|a, b ∈ A} ⊂ P(A) heißt Menge der ungeordneten Paare in A.

Definition 1.2. Ein Graph ist ein Tripel (V, E, π) bestehend aus der Menge V der Knoten (engl. vertex, vertices), der Menge E der Kanten (engl. edge) und der Endpunktbildung π : E ⟶ V ∘ V. Für eine Kante k ∈ E heißen die Knoten a und b mit π(k) = {a, b} Endpunkte von k. Eine Kante k und ein Knoten a heißen inzident, wenn a ein Endpunkt von k ist. Eine Kante heißt eine Schlinge, wenn π(k) = {a} einelementige Menge ist. Ein Graph heißt schlicht, wenn π injektiv ist und der Graph ohne Schlingen ist. Ein Graph heißt endlich, wenn er nur endlich viele Kanten und Knoten besitzt.

Bemerkung 1.3. Ein endlicher schlichter Graph wird häufig durch seine Adjazenzmatrix dargestellt; z.B.

\begin{aligned}& v_{1} & v_{2} & v_{3} & v_{4} \\ v_{1} & 0 & 0 & 1 & 0 \\ v_{2} & 0 & 0 & 1 & 1 \\ v_{3} & 1 & 1 & 0 & 1 \\ v_{4} & 0 & 1 & 1 & 0 \end{aligned} = (\begin{matrix}0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix})

wobei V = {v_{1}, …, v_{4}} und E dargestellt ist durch die 1-en in der Matrix. Diese Matrix stellt den Graphen

[figure]

dar. Die Matrix muß spiegelsymmetrisch zur Diagonalen sein, weil jeder Kante nur ein ungeordnetes Paar {v_{i}, v_{j}} zugeordnet wird.

Definition 1.4. Ein Teilgraph eines Graphen (V, E, π) besteht aus Teilmengen E_{1} ⊂ E, V_{1} ⊂ V, so daß π(E_{1}) ⊂ V_{1} ∘V_{1} gilt. Ein Teilgraph (V_{1}, E_{1}) heißt spannender Teilgraph, wenn V_{1} = V ist. Ein Teilgraph (V_{1}, E_{1}) heißt gesättigter Teilgraph oder von V_{1} induziert, wenn π^{−1}(V_{1} ∘ V_{1}) = E_{1}.

Definition 1.5. Sei X = (V, E, π) ein endlicher Graph. Der Grad d(a) eines Knotens a ∈ V ist die Anzahl der mit a inzidierenden Kanten, wobei eine Schlinge mit Endpunkt a doppelt zu zählen ist. a ∈ V heißt isolierter Punkt, wenn d(a) = 0. Allgemein gilt für einen endlichen schlichten Graphen 0 ≤ d(a) ≤ |V | − 1. a ∈ V heißt ein Endknoten in X, wenn d(a) = 1.

Sind je zwei verschiedene Knoten eines endlichen schlichten Graphen X durch eine Kante verbunden, so heißt X vollständig. Die Vervollständigung eines endlichen schlichten Graphen X = (V, E, π) ist (V, V ∘ V, id).

Ein erstes einfaches aber weitreichendes Abzählprinzip ist in dem folgenden Satz angegeben.

Satz 1.6. In einem endlichen schlichten Graphen X = (V, E, π) gilt

∑_{a∈V} d(a) = 2|E|.

Beweis. Jede Kante in E hat zwei Endpunkte, die beide in der linken Summe berücksichtigt werden. Sie wird also links genau zweimal gezählt.

Folgerung 1.7. Die Anzahl der Knoten ungeraden Grades in einem endlichen schlichten Graphen ist gerade.

Ebenso wie bei algebraischen Grundstrukturen gibt es auch bei Graphen Homomorphismen, also Abbildungen, die die besondere Struktur von Graphen berücksichtigen.

Definition 1.8. Seien X = (V, E, π) und Y = (V′, E′, π′) Graphen. Ein Homomorphismus f : X ⟶ Y besteht aus zwei Abbildungen f_{V} : V ⟶ V′, f_{E} : E ⟶ E′ mit

∀k ∈ E[π(k) = {a, b} ⟹ π′f_{E}(k) = {f_{v}(a), f_{v}(b)}].

Es werden also Knoten auf Knoten und Kanten auf Kanten so abgebildet, daß ihre Inzidenz erhalten bleibt. Ein Isomorphismus f : X ⟶ Y ist ein Homomorphismus, zu dem ein weiterer Homomorphismus g : Y ⟶ X existiert mit gf = id_{X} und fg = id_{Y}. Zwei Graphen heißen isomorph, wenn zwischen ihnen ein Isomorphismus existiert.

Selbst bei endlichen Graphen ist es oft nicht leicht, zu erkennen, ob zwei gegebene Graphen isomorph sind. Für diesen Zweck wollen wir jetzt ein kleines Hilfsmittel entwickeln.

Definition 1.9. Sei Y = (V′, E′) ein Teilgraph des schlichten Graphen X = (V, E, π). Dann ist X \ Y := (V, E \ E′) ein Teilgraph von X, genannt Komplement von Y in X. Das Komplement eines schlichten Graphen X = (V, E, π) ist sein Komplement in der Vervollständigung.

Beispiele 1.10. 1) Das Komplement von

[figure: in; ist]

2) Das Komplement von

[figure: ist]

Satz 1.11. Zwei schlichte Graphen sind genau dann isomorph, wenn ihre Komplemente isomorph sind.

Beweis. Da das doppelte Komplement eines Graphen der Graph selbst ist, genügt es aus der Isomorphie X ≅ Y auf die Isomorphie X′ ≅ Y′ zu schließen. Wir identifizieren entlang π, also E ⊂ V ∘ V. Sei f : V_{X} ⟶ V_{Y} bijektiv und f(E_{X}) = E_{Y}, wobei f(E_{X}) = {{f(a), f(b)}|{a, b} ∈ E}. Dann ist f(V_{X} ∘ V_{X} \ E_{X}) = V_{Y} ∘ V_{Y} \ E_{Y} .

Beispiel 1.12.

[figure: ≅; , denn]

[figure: ≅]

2. Ebene Graphen

Wir beginnen diesen Abschnitt mit zwei einfachen Problemen aus der Graphentheorie, die zu ihrer Lösung schon tiefliegende allgemeinere Sätze benötigen.

Probleme 2.1. (1) Gegeben seien drei Häuser a_{1}, a_{2}, a_{3} und drei Versorgungsanschlüsse a_{4}, a_{5}, a_{6} (für Gas, Wasser und Strom). Kann man alle drei Häuser an die Versorgung so anschließen, daß sich die Leitungen nicht überschneiden?

[figure: a_{1}; a_{2}; a_{3}; a_{4}; a_{5}; a_{6}]

Kann der Graph mit der Adjazenzmatrix

a_{1} a_{2} a_{3} a_{4} a_{5} a_{6}
a_{1} 0 0 0 1 1 1
a_{2} 0 0 0 1 1 1
a_{3} 0 0 0 1 1 1
a_{4} 1 1 1 0 0 0
a_{5} 1 1 1 0 0 0
a_{6} 1 1 1 0 0 0

in der Ebene ohne Überschneidungen realisiert werden?

(2) (Problem der Königsberger Brücken)

[figure: West; Kneiphof; Pregel; C; A; B; D]

Gibt es einen Weg von A, B oder C nach D, der über jede der 7 Brücken genau einmal führt? (Euler 1736)

Die gestellten Probleme benötigen einige weitere Begriffe.

Definition 2.2. (1) Ein endlicher Graph heißt ebener Graph, wenn er sich durch Punkte und Kurven ohne Überschneidungen in der Ebene realisieren läßt.

(2) Ein Weg W der Länge n in einem Graphen X besteht aus einer endlichen Folge von Kanten k_{1}, …, k_{n} mit π(k_{1}) = {a_{0}, a_{1}}, π(k_{2}) = {a_{1}, a_{2}}, …, π(k_{i}) = {a_{i−1}, a_{i}}, π(k_{n}) = {a_{n−1}, a_{n}}. a_{0} heißt Anfangspunkt, a_{n} Schlußpunkt des Weges, beide heißen Endpunkte von W. Ein Weg heißt geschlossen oder eine Schleife, wenn a_{0} = a_{n} gilt, sonst heißt er offen. Ein Weg heißt einfach, wenn alle Knoten a_{0}, a_{1}, …, a_{n} des Weges paarweise verschieden sind mit Ausnahme der Endpunkte. Der Weg ϕ von a_{0} nach a_{0} heißt trivial. Ein Kreis ist eine einfache nicht-triviale Schleife.

Satz 2.3. Jeder Weg von a nach b in einem Graphen X enthält einen einfachen Weg von a nach b.

Beweis. Für a = b ist der triviale Weg einfach. Sei a ≠ b und k_{1}, …, k_{n+1} der Weg von a nach b. Für n = 1 ist W einfach. Enthalte jeder Weg der Länge n einen einfachen Weg. Seien i < j mit a_{i} = a_{j} gegeben. Dann ist k_{1}, …, k_{i}, k_{j+1}, …, k_{n+1} ein Weg, denn π(k_{i}) = {a_{i−1}, a_{j}}, π(k_{j+1}) = {a_{j}, a_{j+1}}. Da die Länge dieses Weges kleiner als n + 1 ist, enthält er einen einfachen Weg von a nach b.

Definition 2.4. Der Abstand d(a, b) zweier Knoten a und b in einem Graphen X ist die kleinste Länge eines (einfachen) Weges von a nach b. Wenn es keinen Weg von a nach b gibt, dann setzen wir d(a, b) = ∞. Es gelten die Gesetze einer Metrik

(1) d(a, b) = 0 genau dann, wenn a = b,

(2) d(a, b) = d(b, a) für alle a, b ∈ V,

(3) d(a, c) ≤ d(a, b) + d(b, c) für alle a, b, c ∈ V. Ein Graph heißt zusammenhängend, wenn je zwei seiner Knoten durch einen Weg verbunden sind. Ein Graph ”zerfällt“ in seine Zusammenhangskomponenten, weil der Zusammenhang zweier Knoten (d(a, b) < ∞) eine Äquivalenzrelation ist.

Definition 2.5. Jede geometrische Realisierung eines ebenen Graphen in der Ebene zerlegt die Ebene in zusammenhängende Gebiete, von denen genau eines, das Außengebiet, nicht beschränkt ist.

[figure: und]

sind zwei ebene Realisierungen desselben Graphen.

Satz 2.6. (Euler) Sei X = (V, E, π) ein zusammenhängender ebener nichtleerer Graph und G die Menge der Gebiete des Graphen. Dann gilt

|V | − |E| + |G| = 2. (Eulersche Polyederformel)

Beweis. Induktion nach |E|. Sei |E| = 1. Dann besitzt X genau eine Kante und entweder einen Knoten (die Kante ist eine Schlinge) oder zwei Knoten. Mehr treten nicht auf, weil X zusammenhängend ist. Im ersten Fall gilt |G| = 2, |V | = 1 und |V | − |E| + |G| = 2. Im zweiten Fall gilt |G| = 1, |V | = 2 und |V | − |E| + |G| = 2. Sei die Behauptung richtig, wenn |E| = n. Sei X ein zusammenhängender ebener Graph mit |E| = n + 1. Fall 1: X besitzt einen Endpunkt a (mit d(a) = 1) mit anhängender Kante k(π(k) = {a, b}). Dann ist auch X′ = (V \ {a}, E \ {k}, π) ein zusammenhängender ebener Graph. Die Anzahl der Gebiete verändert sich nicht, weil durch k kein Gebiet abgeschlossen werden kann. Also ist 2 = (|V | − 1) − (|E| − 1) + |G| = |V | − |E| + |G|. Fall 2: Es gibt keine Endpunkte. Sei k mit π(k) = {a, b} eine Kante auf der Begrenzung eines endlichen Gebietes. Ein solches Gebiet existiert, sonst ist X ein zusammenhängender Graph mit |V | Knoten und |E| = |V | − 1 Kanten, insbesondere mit einem Endpunkt. Wir entfernen k aus X und erhalten einen Graphen X \ {k}, der ein Gebiet weniger als X hat, also 2 = |V | − (|E| − 1) + (|G| − 1) = |V | − |E| + |G|.

Folgerung 2.7. Sei X ein zusammenhängender ebener schlichter Graph mit mindestens 2 Kanten. Dann ist 3|G| ≤ 2|E| und |E| ≤ 3|V | − 6. Außerdem gilt d = min{d(a)|a ∈ V } ≤ 5.

Beweis. Jedes innere Gebiet wird von mindestens 3 Kanten begrenzt, weil X schlicht ist. Jede Kante grenzt an höchstens 2 Gebiete. Also ist 3|G| ≤ 2|E| , wenn wir die Inzidenzpaare (Kante, Gebiet) zählen. Das gilt auch, wenn nur 2 Kanten und kein inneres Gebiet existieren. Mit dem Satz von Euler folgt 2 = |V | − |E| + |G| ≤ |V | − |E| + \frac{2}{3}|E| = |V | − \frac{1}{3}|E|, oder 3|V | − 6 ≥ |E|. Weiter ist d · |V | ≤ 2|E| ≤ 6|V | − 12, ein Widerspruch für d ≥ 6.

Folgerung 2.8. Die beiden Graphen

K_{3,3} = [figure] und K_{5} = [figure]

sind nicht eben.

Beweis. K_{3,3} : Es ist |V | = 6 und |E| = 9. Wäre K_{3,3} eben, so müßte |G| = 2 − |V | + |E| = 5 gelten. Jedes Gebiet wird von mindestens 4 Kanten begrenzt (es gibt keine Dreiecke in K_{3,3}). Jede Kante grenzt an 2 Gebiete an. Also ist 4|G| ≤ 2|E|. Dann wäre aber 20 = 4 · 5 ≤ 2 · 9 = 18, was nicht möglich ist. K_{5} : Es ist|V | = 5 und |E| = 10. Dann ist 3|V | − 6 = 15 − 6 = 9 < 10 = |E| in Widerspruch zu Folgerung 2.7

Bemerkung 2.9. Mit Folgerung 2.8 ist auch das Versorgungsproblem 2.1 (1) gelöst, und zwar negativ.

Da wir jetzt einige Graphen gefunden haben, die nicht eben sind, erhebt sich die Frage, ob es noch weitere solche Graphen gibt. Darüber gibt der Satz von Kuratowski Auskunft, den wir hier nur angeben wollen, weil sein Beweis weitere Hilfsmittel benötigt. Um die Aussage des Satzes zu verstehen, benötigen wir erst noch einen weiteren Begriff.

Definition 2.10. Ein schlichter Graph Y = (V′, E′, π′) entsteht aus dem schlichten Graphen X = (V, E, π) durch einfache Unterteilung der Kante k ∈ E, wenn gelten

\begin{aligned}V′ & = & V ∪ \{a\} mit a ∉ V, \\ E′ & = & (E \ \{k\}) ∪ \{l, m\} mit l, m ∉ E, k ∈ E, \\ π(k) & = & \{b, c\}, π′(l) = \{a, b\}, π′(m) = \{a, c\}. \end{aligned}

Y entsteht aus X durch Unterteilung, wenn Y durch eine endliche Folge von einfachen Unterteilungen aus X entsteht.

Satz 2.11. (Kuratowski) Ein schlichter endlicher Graph ist genau dann eben, wenn er keinen Teilgraphen besitzt, der eine Unterteilung von K_{3,3} oder K_{5} ist.

Eine weitere schöne Anwendung der Eulerschen Polyederformel ist die Aufzählung der möglichen Platonischen Körper.

Bemerkung 2.12. (Platonische Körper) Ein Platonischer Körper besteht aus einer Realisierung eines schlichten Graphen auf der 2−Sphäre S^{2} (Kugeloberfläche), so daß alle entstehenden Gebiete kongruent sind und sich in jedem Knoten gleich viele Gebiete treffen. Sei m die Anzahl der Kanten bzw. Knoten eines (jeden) Gebietes, n die Anzahl der Gebiete, die einen Knoten gemeinsam haben. Wir setzen weiterhin m, n ≥ 3 voraus. Schneiden wir ein Gebiet auf, so entsteht ein ebener Graph, der das aufgeschnittene Gebiet als Außengebiet hat. Sei P = (V, E) eine solche Realisierung eines platonischen Körpers. Also ist 2|E| = m|G|, wenn man die Inzidenzpaare (Kanten, Gebiete) zählt. Zählen wir die Inzidenzpaare (Knoten, Gebiete), so gilt m|G| = n|V |. Mit Eulers Satz folgt 0 < 2 = |V | − |E| + |G| = (\frac{m}{n} − \frac{m}{2} + 1)|G| also \frac{2m−mn+2n}{2n} > 0 oder (m − 2)(n − 2) = (−2m + mn − 2n) + 4 < 4. Es können höchstens folgende Fälle auftreten:

m = 3, n = 3, (m − 2)(n − 2) = 1, Tetraeder,
m = 4, n = 3, (m − 2)(n − 2) = 2, Würfel,
m = 3, n = 4, (m − 2)(n − 2) = 2, Oktaeder,
m = 5, n = 3, (m − 2)(n − 2) = 3, Dodekaeder,
m = 3, n = 5, (m − 2)(n − 2) = 3, Ikosaeder.

Definition 2.13. Gibt es in einem Graphen X einen geschlossenen Weg W, der jede Kante aus E_{X} genau einmal enthält und jeden Knoten (mindestens) einmal enthält, so heißt X ein Eulerscher Graph und W eine Eulersche Linie.

Satz 2.14. Für einen Graphen X sind äquivalent:

(1) X ist ein Eulerscher Graph.

(2) Jeder Knoten von X hat geraden Grad und X ist ein zusammenhängender, endlicher Graph.

Beweis. (1) ⟹ (2) : Eine Eulersche Linie, die in einen Knoten hineinläuft, muß ihn auf einer anderen Kante auch wieder verlassen. Bei jedem Besuch eines Knotens werden 2 weitere Kanten belegt. Man beachte, daß hier Schlingen bei der Bestimmung des Grades von Knoten doppelt gezählt werden. Es ist klar, daß X zusammenhängend und endlich ist.

(2) ⟹ (1) : Wenn |E| = 1, dann ist X von der Form [figure] . Wenn

|E| = 2, dann hat X die Form [figure] oder [figure]. In beiden Fällen ist die Eulersche Linie klar. Sei die Aussage wahr für Graphen mit höchstens n Kanten. Habe X = (V, E, π) n + 1 Kanten. Sei a ∈ V als Anfangspunkt gewählt. Wir bilden einen Weg W von a ausgehend, bei dem jede Kante höchstens einmal auftritt. Wenn dieser Weg nicht mehr zu verlängern ist, d.h. keine Kante mehr aus dem letzten Knoten herausführt, dann muß der Endpunkt dieses Weges a sein, weil alle anderen besuchten Knoten geraden Grad haben. Sind in diesem Weg alle Kanten und Knoten enthalten, so sind wir fertig. Sonst bilden wir X \ W. Dieser Graph kann in Zusammenhangskomponenten zerfallen. Aber jede Komponente hat wieder nur Knoten von geradem Grad, und hat daher Eulersche Linien. Diese müssen sich mit W treffen, weil X zusammenhängend war. Man kann sie daher mit W zu einer Eulerschen Linie zusammenfügen.

Bemerkung 2.15. (Lösung des Königsberger Brückenproblems) Der Graph ist

[figure]

Wir fügen einen zusätzlichen ”Rückweg“ ein und erhalten

[figure: oder; oder]

In keinem Fall liegt ein Eulerscher Graph vor.

Beispiel 2.16. Das Königsberger Brückenproblem kann wie folgt erweitert werden. Der reiche Baron A wohnt in A. Er ärgert sich, daß er nach einem Besuch des Kneiphofes auf der Insel D nicht so nach Hause gehen kann, daß er jede der Brücken genau einmal überquert. Deshalb baut er eine weitere Brücke, so daß er über die nunmehr acht Brücken abends heimgehen kann. Der auf seinen guten Ruf bedachte Graf B wohnt in B und ärgert sich, daß zwar der Baron A jetzt abends vom Kneiphof über alle Brücken heimgehen kann, er selbst aber nicht. Daher baut er noch eine weitere Brücke. Nun kann Graf B abends über alle neun Brücken heimgehen und jede dabei genau einmal überqueren, aber nicht mehr der Baron A. Weil die Kosten für den Brückenbau die Finanzen der beiden Herren stark belastet haben, einigen sie sich auf den Bau nur noch einer weiteren Brücke, so daß sie beide auf einer einzigen Eulerschen Linie den Kneiphof besuchen und wieder heimkehren können. Wie wurden die drei weiteren Brücken gebaut? Zur Lösung wurde die achte Brücke so gebaut:

[figure: und ergab mit Hinweg]

einen Eulerschen Graphen. Die neunte Brücke wurde so gebaut:

[figure: und ergab mit Hinweg]

einen Eulerschen Graphen. Die zehnte Brücke wurde so gebaut

[figure]

Dieser Graph ist Eulersch.

3. Bäume

Besonders häufig benutzte Graphen in der Informatik sind sogenannte Bäume. Sie werden ausführlich in anderen Vorlesungen studiert, so daß wir uns hier mit einer Charakterisierung und einigen Beispielen begnügen können.

Definition 3.1. Ein Baum ist ein zusammenhängender schlichter Graph ohne Kreise. Ein Wald ist ein schlichter Graph ohne Kreise.

Satz 3.2. Sei X ein schlichter Graph mit n Knoten und m Kanten. Dann sind äquivalent

(1) X ist ein Baum.

(2) Je zwei Knoten sind in X durch genau einen Weg verbunden.

(3) X ist zusammenhängend und für jede Kante k ∈ E gilt, daß X \ {k} = (V, E \ {k}) nicht zusammenhängend ist.

(4) X ist zusammenhängend, und es gilt m = n − 1.

(5) X ist ein Graph ohne Kreise, und für jede Kante k im Komplement von X ist X ∪{k} = (V, E ∪{k}) ein Graph mit genau einem Kreis.

Ohne Beweis.

Definition 3.3. Ein Baum zusammen mit einem ausgezeichneten Knoten w (= Wurzel) heißt ein Wurzelbaum. Ein Endknoten eines Wurzelbaumes heißt Blatt. Beachte: Die Bäume der Informatik bzw. Mathematik wachsen im Himmel, d.h. die Wurzel wird immer zuoberst gezeichnet. Sind a und b benachbarte Knoten in einem Wurzelbaum und ist d(a, w) < d(b, w), so heißt a der Vater von b und b ein Sohn von a. Wenn jeder Knoten höchstens n Söhne hat, so sprechen wir von einem n−ären Wurzelbaum. Wenn jeder Knoten, außer den Blättern, genau n Söhne hat, so nennen wir den Baum einen regulären n−ären Wurzelbaum.

Bemerkung 3.4. Ein regulärer binärer Wurzelbaum hat genau einen Knoten von Grad 2, nämlich die Wurzel. Alle anderen Knoten haben den Grad 1 oder 3. Folglich hat er eine ungerade Anzahl von Knoten, denn wegen ∑_{a∈V} d(a) = 2|E| gerade und weil alle Summanden d(a) außer d(w) ungerade sind, muß eine ungerade Anzahl von Summanden vorliegen. Wenn der reguläre binäre Baum n Knoten hat, dann hat er (n + 1)/2 Blätter. Denn hat er t Blätter, so hat er n − t − 1 Knoten vom Grad 3, also ist |E| = \frac{1}{2} · (t + 3 · (n − t − 1) + 2) = n − 1. Daraus bestimmt sich t = (n + 1)/2. Die Knoten in einem Baum, deren Grad größer als eins ist, heißen innere Knoten. Ein regulärer binärer Baum besitzt also (n − 1)/2 innere Knoten, also genau einen inneren Knoten weniger, als er Blätter hat.

Beispiele 3.5. (1) [figure] ist ein Baum.

(2) [figure] ist ein regulärer binärer Wurzelbaum.

(3) [figure] ist ein Wurzelbaum, der als Baum

(Graph) zu dem in Beispiel 2) gezeigten isomorph ist.

(4) Die Veranstaltung eines Sportwettkampfes nach dem k.o. System (der Sieger eines Matches kommt eine Runde weiter, Freilose sind möglich) induziert einen regulären binären Wurzelbaum. Die Teilnehmer sind die Blätter, die inneren Knoten sind die einzelnen Turnierkämpfe. Es werden genau n − 1 Turnierkämpfe stattfinden, wenn n Teilnehmer gemeldet sind.

(5) Ein algebraischer Ausdruck ((a + b) · c + d · (e + f · g)) · h definiert einen regulären binären Baum mit den Blättern a, …, h und den Knoten +, ·, +, ·, +, ·, ·. Der Baum ist

[figure: a; b; c; d; e; f; g; h; +; +; +]

Beim Auftreten von nicht-kommutativen Operationen ist die Reihenfolge in der Schicht der Söhne eines Knotens zu beachten.