Bäume und Wälder

Definition (Baum, Wald)

Ein Graph G heißt ein Wald, falls G keine Kreise besitzt. Ein Wald heißt ein (graphentheoretischer) Baum, wenn er zusammenhängend ist.

 Ein Baum ist also ein zusammenhängender kreisfreier Graph. Jeder Baum lässt sich „baumartig“ organisieren, indem wir eine Ecke als Wurzel auszeichnen und dann die Nachbarecken stufenweise anordnen:

Beispiel

Sei G = (E, K) mit E = { 1, …, 14 } und

K  =  { 12, 13, 16, 17, 18, 19, 34, 35, 9-10, 10-11, 11-12, 11-13, 11-14 }.

ema21-AbbID2-5-1

Der Graph ist ein Baum. Wir wählen die Ecke 9 als Wurzel und erhalten:

Stufe 0{ 9 }
Stufe 1{ 1, 10 }
Stufe 2{ 2, 3, 6, 7, 8, 11 }
Stufe 3{ 4, 5, 12, 13, 14 }
ema21-AbbID2-5-2

Wählen wir dagegen die 1 als Wurzel, so erhalten wir eine Stufe mehr:

ema21-AbbID2-5-3

 Ein graphentheoretischer Baum hat keine feste Wurzel. Wir können jede Ecke als Wurzel auszeichnen und den Baum entsprechend anordnen und zeichnen, wahlweise nach unten, oben, links oder rechts wachsend. Die Auszeichnung einer Wurzel führt zu einer eindeutigen Stufung des Baumes.

 Ein Wald ist eine Ansammlung von Bäumen, und diese Bäume sind genau die Zusammenhangskomponenten des Waldes. Zeichnen wir in jeder Komponente eine Wurzel aus, so ergibt sich eine Stufung des Waldes.

Beispiel

Durch Entfernen der Kante 9-10 aus obigem Baum entsteht ein Wald mit zwei Teilbäumen. Mit den Wurzeln 1 und 11 ergibt sich die Darstellung:

ema21-AbbID2-5-4

 Wir betrachten noch weitere Beispiele für Bäume, wobei wir die Ecken unbenannt lassen.

ema21-AbbID2-5-5

Vollständig binär verzweigter Baum mit vier Stufen

ema21-AbbID2-5-6

Vollständig binär verzweigter Baum mit fünf Stufen

ema21-AbbID2-5-7

Vollständig vierfach verzweigter Baum mit drei Stufen

ema21-AbbID2-5-8

Sterngraph mit 18 Ecken

Charakterisierungen

 Bäume lassen sich durch verschiedene Äquivalenzen beschreiben. Eine derartige Charakterisierung ist:

Satz (Wegkriterium)

Sei G = (E, K) ein Graph. Dann sind äquivalent:

(1)

G ist ein Baum.

(2)

Für alle a, b  ∈  E gibt es genau einen Weg von a nach b in G.

Beweis

(1) impliziert (2): 

Sei G ein Baum, und seien a, b  ∈  E. Da G zusammenhängend ist, gibt es mindestens einen Weg von a nach b. Zum Beweis der Eindeutigkeit seien

W1  =  a0, …, an,  W2 = b0, …, bm

zwei Wege von a0 = b0 = a nach an = bm = b. Annahme W1 ≠ W2. Dann existiert eine Stelle i, an der sich die beiden Wege trennen, d. h. ai = bi und ai + 1 ≠ bi + 1. Weiter gibt es eine erste Stelle j > i auf W1, an der sich die Wege wieder treffen, sodass also aj = bk für ein eindeutig bestimmtes k > i. Dann ist aber

C  =  ai, …, aj, bk − 1, …, bi

ein Kreis in G, im Widerspruch zu G Baum.

(2) impliziert (1): 

Sei G derart, dass es für alle Ecken a, b  ∈  E genau einen Weg von a nach b gibt. Dann ist G zusammenhängend. Weiter kann G keinen Kreis besitzen, denn ist C = a0, …, an, a0 ein Kreis, so sind a0, …, an und a0, an zwei verschiedene Wege von a0 nach an in G.

 Ein weiteres nützliches Kriterium ist:

Satz (Kantenkriterium)

Sei G = (E, K) ein zusammenhängender Graph. Dann sind äquivalent:

(1)

G ist ein Baum.

(2)

Es gilt |K| = |E| − 1.

 Allgemeiner ist ein Graph mit genau c Komponenten genau dann ein Wald, wenn

|K|  =  |E| − c.

Der Beweis dieser Äquivalenzen sei dem Leser zur Übung überlassen.