Graphentheoretische Zählungen

Zur Illustration der Mächtigkeitsberechnung betrachten wir zwei exemplarische Fragen der Graphentheorie.

1. Zählen von Kantenzügen

Wir fragen:

Wie viele Kantenzüge der Länge m gibt es zwischen zwei Ecken eines Graphen?

Diese auf den ersten Blick schwierige Frage lässt sich überraschend einfach beantworten. Wir betrachten hierzu einen Graphen G = (E, K) mit E = { 1, …, n }. Für alle m ≥ 0 definieren wir eine (n × n)-Matrix C_m durch

C_m(i, j) = |{ Z | Z ist ein Kantenzug der Länge m von i nach j in G }|.

Es gilt

C₀ = E_n mit der Einheitsmatrix E_n,

C₁ = A mit der Adjazenz-Matrix A von G.

Sei nun m ≥ 1, und seien i, j  ∈  E. Zur Berechnung von C_m + 1(i, j) zerlegen wir die Menge aller Kantenzüge von i nach j der Länge m + 1 in disjunkte Mengen gemäß der vorletzten besuchten Ecke. Es gilt:

(a)	Jeder Kantenzug von i nach j der Länge m + 1 hat eine vorletzte besuchte Ecke k.

(b)	Jeder Kantenzug der Länge m von i nach k kann genau dann zu einem Kantenzug von i nach j der Länge m + 1 fortgesetzt werden, wenn kj eine Kante des Graphen ist, d. h. wenn A(k, j) = 1.

Damit erhalten wir die rekursive Beziehung

C_m + 1(i, j) = C_m(i, 1) A(1, j) + … + C_m(i, n) A(n, j) für alle i, j und alle m ≥ 0.

Nach der Definition „Zeile mal Spalte“ der Matrizen-Multiplikation gilt also

C_m + 1 = C_m A,

woraus sich induktiv ergibt, dass C_m = A^m für alle m ≥ 0. Die Potenzen der Adjazenz-Matrix zählen also Kantenzüge. Genauer zeigen unsere Überlegungen:

Satz (Zahl der Kantenzüge, Abstandsberechnung)

Sei G = (E, K) ein Graph mit der Eckenmenge E = { 1, …, n }, und sei A die Adjazenz-Matrix von G. Weiter seien i, j  ∈  E und m ≥ 0. Dann ist A^m(i, j) die Anzahl der Kantenzüge in G von i nach j der Länge m. Speziell ist j erreichbar von i in G, wenn A^m(i, j) ≠ 0 für ein m. In diesem Fall ist

d(i, j) = „das kleinste m mit A^m(i, j) ≠ 0“.

2. Zählen von Bäumen

Wir fragen:

Wie viele graphentheoretische Bäume mit n Ecken gibt es?

Für n ≥ 1 sei T_n die Menge der Bäume mit der Eckenmenge { 1, …, n }. Zunächst hat T₁ genau ein Element. Eine konkrete Aufzählung aller Bäume ergibt

|T₂| = 1 = 2⁰, |T₃| = 3 = 3¹, |T₄| = 16 = 4².

Die 16 Bäume mit den Ecken 1, 2, 3, 4

Wir vermuten:

(+) |T_n| = n^n − 2 für alle n ≥ 2.

Gefunden und bewiesen wurde die Formel (+) zuerst von Arthur Cayley (1854). Ein induktiver Beweis ist möglich, aber nicht trivial. Eine bestechende Alternative ist ein auf Heinz Prüfer (1918) zurückgehender Beweis, der für alle n ≥ 2 eine konkrete Bijektion Pr zwischen T_n und der Menge

C_n = { 1, …, n }^n − 2

aller Tupel in { 1, …, n } der Länge n − 2 konstruiert. Wir können das einem Baum G zugeordnete Tupel Pr(G) = (a₁, …, a_n − 2)  ∈  C_n als Kode des Baumes ansehen, aus dem sich der Baum rekonstruieren lässt. Diese Kodes sind als Prüfer-Kodes bekannt.

Erstellung des Prüfer-Kodes eines Baumes

Sei n ≥ 2, und sei G  ∈  T_n. Wir definieren rekursiv Teilbäume G₁, …, G_n − 2 von G (durch schrittweises Entfernen von Ecken) und den Prüfer-Kode Pr(G) = (a₁, …, a_n − 2) von G wie folgt.

Zunächst sei G₁ = G.

Ist G_i konstruiert, so sei a die kleinste Ecke von G_i mit Grad 1, d. h. a ist das erste Blatt von G_i. Weiter sei b der eindeutige Nachbar von a in G_i. Dann setzen wir

a_i = b, G_i + 1 = G_i − { a } (Streichen der Ecke a).

Rekonstruktion des Baumes aus seinem Prüfer-Kode

Sei Pr(G) = (a₁, …, a_n − 2) der Prüfer-Kode des Baumes G = (E, K). Wir definieren eine Folge (b₁, …, b_n − 2) rekursiv wie folgt:

b_i = „das kleinste i  ∈  { 1, …, n } mit i ≠ b₁, …, b_i − 1, a_i, … a_n“.

Das Ergebnis der Berechnung ist die Kantenmenge

{ a_i b_i | 1 ≤ i ≤ n − 2 } ∪ { i*j* },

wobei i*, j* die beiden in b fehlenden Ecken von G sind.

Beispiel

Wir betrachten den folgenden Baum G = (E, K) mit den Ecken { 1, …, 8 }:

Das 6 mal wiederholte Streichen der kleinsten Blätter ergibt die Blattfolge (2, 3, 4, 7, 1, 6) und den Prüfer-Kode

Pr(G) = (1, 1, 5, 1, 6, 5).

Die Rekonstruktion (für die nur Pr(G) verwendet wird) ergibt die b-Folge

(2, 3, 4, 7, 1, 6)

und reproduziert damit die Blattfolge. Es ergeben sich die Kanten

{ a_i b_i | i = 1, …, 6 } ∪ { i*j* } = { 12, 13, 54, 17, 61, 56 } ∪ { 58 } = K.

Insgesamt ergibt sich (Übung):

Satz (Satz von Cayley-Prüfer)

Sei n ≥ 2. Dann ist |T_n| = n^n − 2. Genauer ist die Abbildung Pr : T_n → C_n, die jedem Baum G  ∈  T_n seinen Prüfer-Kode Pr(G) zuordnet, bijektiv. Ist G  ∈  T_n, so ist die Rekonstruktionsfolge (b₁, …, b_n − 2) die Folge der Blätter, die bei der rekursiven Erstellung des Kodes Pr(G) gestrichen wurden.