Kurs:Diskrete Mathematik (Osnabrück 2026)/Vorlesung 21

Aufspannende Bäume

Die U-Bahn Osnabrück soll renoviert werden, deshalb müssen einzelne Streckenabschnitte geschlossen werden. Einerseits möchte man möglichst viele Streckenabschnitte gleichzeitig renovieren, andererseits möchte man sicherstellen, dass noch jede Station angefahren wird und dass das Netz zusammenhängend bleibt. In einem engmaschigen Netz wie der Osnabrücker U-Bahn gibt es viele Möglichkeiten, das Netz in der beschriebenen Weise aufzubrechen. Ein solches verbleibendes Restnetz nennt man einen Spannbaum oder aufspannenden Baum.

Definition

Ein Untergraph $B \subseteq G$ eines Graphen $G = (V, E)$ heißt aufspannender Baum von $G$ , wenn $B$ ein Baum mit der vollen Knotenmenge $V$ ist.

Ein Graph, der einen aufspannenden Baum besitzt, ist zusammenhängend. Davon gilt auch die Umkehrung.

Satz

Ein zusammenhängender Graph

besitzt einen aufspannenden Baum.

Beweis

Wir führen Induktion über die Anzahl der Kanten. Der Induktionsanfang ist klar, da ein kantenfreier Graph nur im einpunktigen Fall zusammenhängend ist, und dies ein Baum ist. Es sei $G = (V, E)$ ein zusammenhängender Graph mit $m$ Kanten. Wenn $G$ ein Baum ist, sind wir fertig. Es sei also $G$ kein Baum. Dann gibt es einen Kreis

v_{1}, v_{2}, \dots, v_{r}, v_{r + 1} = v_{1}

mit $r \geq 3$ in $G$ . Wir betrachten den Graphen $G^{'}$ mit der gleichen Knotenmenge $V$ und der neuen Kantenmenge

E^{'} = E ∖ {v_{1} v_{2}} .

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen $v_{1}$ und $v_{2}$ über das verbleibende „Kreissegment“ $v_{2}, \dots, v_{r} = v_{1}$ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in $G^{'}$ , und dieser ist auch ein aufspannender Baum von $G$ .

◻

Dieser Beweis zeigt zugleich, wie man einen aufspannenden Baum in einem zusammenhängenden Graphen finden kann. Nach Satz 20.22 ist die Anzahl der Kanten in einem Spannbaum eindeutig bestimmt, sie ist um $1$ kleiner als die Knotenanzahl des Graphen. Insbesondere besitzt jeder Spannbaum die gleiche Kantenanzahl.

Beispiel

Wir betrachten den Spielzuggraphen des Turmes auf dem Schachbrett und interessieren uns für die Spannbäume darauf. Beispielsweise gibt es lineare Spannbäume, man kann ja die erste Zeile ablaufen, an deren Ende vertikal in die zweite Zeile wechseln und diese rückwärts durchlaufen usw. Man kann auch „eckig spiralförmig“ lineare Spannbäume angeben. Nichtlineare Spannbäume erhält man, wenn man eine Zeile linear durchläuft und an jeden Punkt der Zeile linear eine Spalte anhängt. Diese Spannbäume verfügen alle über $63$ Kanten. Die angegebenen Bäume sind auch Spannbäume auf der gleichknotigen Menge, bei der nur geometrisch direkt (vertikal oder horizontal) nebeneinander liegende Felder durch eine Kante verbunden sind.

Matroide

Wir wollen die Gesamtheit aller Wälder und insbesondere aller Bäume in einem Graphen verstehen. Dazu ist ein kombinatorisches Konzept hilfreich, das auch in anderen Kontexten auftritt und eine abstrakte Theorie von Unabhängigkeit beschreibt.

Definition

Zu einer endlichen Menge $E$ heißt eine Teilmenge

ℳ \subseteq 𝔓 (E)

ein Matroid, wenn folgende Bedingungen erfüllt sind.

Es ist $\emptyset \in ℳ$ .
Aus $A \in ℳ$ und $B \subseteq A$ folgt $B \in ℳ$ .
Wenn $A, B \in ℳ$ mit
$# (A) = # (B) + 1,$

so gibt es ein $a \in A ∖ B$ derart, dass $B \cup {a} \in ℳ$ .

Die dritte Eigenschaft heißt dabei die Austauscheigenschaft. Sie besagt, dass man jede Menge $B$ , die zu dem Matroid gehört, zu einer größeren Menge des Matroids mit Hilfe eines Elements von $A$ auffüllen kann, sobald $A$ mehr Elemente als $B$ besitzt und ebenfalls zum Matroid gehört. Das folgende Standardbeispiel für ein Matroid ist aus der linearen Algebra bekannt.

Beispiel

Es sei $V$ ein $K$ -Vektorraum und sei $v_{i}$ , $i \in I$ , eine Familie von Vektoren in $V$ zu einer endlichen Indexmenge $I$ . Wir setzen

ℳ = {J \subseteq I ∣ Die Familie v_{j}, j \in J, ist linear unabhängig}

und behaupten, dass es sich dabei um ein Matroid handelt. Die Eigenschaften ergeben sich aus Lemma 7.6 (Lineare Algebra (Osnabrück 2024-2025)) (1,2) und aus folgender Überlegung: Wenn die Teilfamilien $v_{j}$ , $j \in J$ und $v_{ℓ}$ , $ℓ \in L$ zu $J, L \subseteq I$ jeweils linear unabhängig sind, und $L$ ein Element mehr als $J$ besitzt, so gilt für die erzeugten Untervektorräume aus Dimensionsgründen

⟨ v_{ℓ}, ℓ \in L ⟩ \subseteq̸ ⟨ v_{j}, j \in J ⟩ .

Daher gibt es auch ein $v_{k}$ , $k \in L$ , mit $v_{k} \notin ⟨ v_{j}, j \in J ⟩$ . Doch dann ist die erweiterte Familie $v_{j}, j \in J, v_{k}$ ebenfalls linear unabhängig.

Wegen dieses Beispiels nennt man die Mengen aus $E$ , die zu einem Matroid gehören, die unabhängigen Mengen. Die folgende Terminologie orientiert sich ebenfalls an der linearen Algebra.

Definition

In einem Matroid $ℳ$ auf einer Menge $I$ nennt man die maximalen Mengen aus $ℳ$ Basen.

Ein $B \in ℳ$ ist also genau dann eine Basis, wenn keine Teilmenge $A \subseteq I$ mit $B \subset A$ zu $ℳ$ gehört. Aufgrund der Austauscheigenschaft besitzt jede Basis in einem Matroid die gleiche Anzahl, siehe Aufgabe 21.8.

Definition

In einem Matroid $ℳ$ auf einer Menge $I$ nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von $ℳ$ den Rang des Matroids.

Wir werden im Folgenden zeigen, dass auch die Wälder in einem Graphen ein Matroid bilden.

Aufspannende Wälder

Definition

Ein Untergraph $W \subseteq G$ eines Graphen $G = (V, E)$ heißt aufspannender Wald von $G$ , wenn $W$ ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von $V$ (als Knotenmenge) übereinstimmen.

Ein aufspannender Wald ist also dadurch gekennzeichnet, dass er auf jeder Zusammenhangskomponenten von $G$ ein aufspannender Baum ist. Insbesondere ist ein aufspannender Wald knotengleich zu $G$ und er lässt sich nicht zu einem Unterwald von $G$ vergrößern.

Wir bezeichnen die Menge der Wälder in einem Graphen $G = (V, E)$ , die $V$ als Knotenmenge besitzen, mit $𝒲 (G)$ . Ein solcher Wald ist durch seine Kanten festgelegt, da ja die Knotenmenge mit der von $G$ übereinstimmt. Insbesondere gehört jeder aufspannende Wald von $G$ zu $𝒲 (G)$ , aber auch der kantenfreie Graph auf $V$ gehört dazu. Es gibt natürlich auch Wälder in $G$ , deren Knotenmenge kleiner ist, das folgende Lemma gilt auch für sie.

Satz

Zu einem Graphen $G = (V, E)$ ist die Waldmenge $𝒲 (G)$ (mit der vollen Knotenmenge)

ein Matroid auf $E$ .

Der Rang dieses Matroids ist die Anzahl der Kanten in einem aufspannenden Wald.

Beweis

Wir gehen die Axiome für ein Matroid durch. Die Menge $(V, \emptyset)$ ist ein Wald, bestehend aus den einpunktigen Bäumen. Ein Untergraph eines Waldes ist wieder ein Wald. Es seien nun $W = (V, F)$ und $Z = (V, K)$ Wälder von $G$ und $Z$ enthalte eine Kante mehr als $W$ . Es ist zu zeigen, dass man $W$ durch eine Kante aus $K$ zu einem größeren Wald ergänzen kann. Es seien $B_{i} = (V_{i}, F_{i})$ , $i = 1, \dots, m$ , die Bäume (also die Zusammenhangskomponenten) von $W$ . Dabei gilt

# (F_{i}) = # (V_{i}) - 1

nach Satz 20.22 (3). Die Einschränkungen von $Z$ auf die $V_{i}$ sind ebenfalls Wälder. Das bedeutet, dass die Anzahl der Kanten $K \cap F_{i}$ höchstens gleich $# (V_{i}) - 1$ ist. Wegen

# (K) > # (F) = \sum_{i = 1}^{m} # (F_{i}) = \sum_{i = 1}^{m} (# (V_{i}) - 1) \geq \sum_{i = 1}^{m} (K \cap F_{i})

folgt, dass es eine Kante $f \in K$ geben muss, die zu keinem $K \cap F_{i}$ gehört. Dies bedeutet, dass diese Kante zwei Bäume $B_{i}$ und $B_{j}$ (in $Z$ ) verbindet, also $f = {v_{i}, v_{j}}$ mit $v_{i} \in V_{i}$ und $v_{j} \in V_{j}$ . Wir behaupten, dass

W^{'} = (V, F \cup {f})

ebenfalls ein Wald ist. Würde es nämlich in $W^{'}$ einen Kreis geben, so müsste darin die neue Kante $f$ beteiligt sein. Wenn man $f$ wieder herausnimmt, so bleibt aber der Restkreis (als ein linearer Graph) zusammenhängend im Widerspruch dazu, dass $v_{i}$ und $v_{j}$ zu verschiedenen Zusammenhangskomponenten von $W$ gehören.

◻

Mit dem Sprachgebrauch der Matroidtheorie kann man sagen, dass die Wälder den unabhängigen Untergraphen und die aufspannenden Wälder den maximal unabhängigen Untergraphen, also den Basen, entsprechen, wobei unabhängig im graphentheoretischen Kontext als zykelfrei zu verstehen ist.

Multigraphen

Wir beschreiben eine rekursive Möglichkeit, um die Anzahl der aufspannenden Bäume in einem Graphen zu bestimmen. Dazu ist es für den induktiven Aufbau der Argumentation sinnvoll, mit Multigraphen zu arbeiten.

Definition

Ein Multigraph $(V, E, θ)$ besteht aus einer Knotenmenge $V$ , einer Kantenmenge $E$ und einer Abbildung

θ : E ⟶ 𝔓_{2} (V) .

Genauer spricht man von einem ungerichteten Multigraphen ohne Schleifen. In der Definition ist $E$ zunächst eine abstrakte Kantenmenge, wobei $e \in E$ erst durch die Abbildung $θ$ die beiden Punkte aus $θ (e)$ miteinander „verbindet“. Einen Multigraphen kann man einfach skizzieren, indem man $V$ als Punktemenge skizziert und für jede abstrakte Kante jeweils eine Verbindungskante zwischen den zugehörigen Punkten zeichnet. Zwei Punkte können dann durch mehrere Kanten miteinander verbunden sein. Wichtig ist, dass die Kanten als verschieden anzusehen sind, was von einem Bildchen her klar ist. Die Kanten haben eine eigene Identität.

Ein Multigraph ist etwas anderes als ein einfacher ungerichteter Graph, bei dem die Kanten noch zusätzlich positive natürliche Zahlen (Gewichte) bekommen. Man überlege sich, was jeweils ein Unterobjekt ist!

Ein ungerichteter Graph ist dasselbe wie ein Multigraph, bei dem die Abbildung $θ$ injektiv ist. In diesem Fall kann man $E$ mit einer gewissen Menge von zweielementigen Teilmengen der Knotenmenge identifizieren.

Die Definition eines Spannbaumes ändert sich für einen Multigraphen nicht, es ist ein (einfacher) Baum, der jeden Knotenpunkt trifft. Unter der Kontraktion entlang einer Kante $e$ verstehen wir im Kontext von Multigraphen denjenigen Graphen, der entsteht, wenn die beiden Endpunkte von $e$ miteinander identifiziert werden und jede Kante des Ausgangsgraphen im Kontraktionsgraphen übernommen wird, entstehende Schleifen aber weggelassen werden. Insbesondere werden sämtliche Kanten, die mit $e$ Anfangs- und Endpunkt teilen, ebenfalls kontrahiert. Dabei kann aus einem einfachen Graphen ein Multigraph entstehen. Diese Kontraktion wird wieder mit $G / e$ bezeichnet.

Zur Anzahl von aufspannenden Bäumen

Lemma

Es sei $G$ ein schleifenfreier Multigraph und $e$ eine Kante von $G$ .

Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

$t (G) = t (G ∖ e) + t (G / e) .$

Beweis

Es sei $e = {u, v}$ . Ein Spannbaum in $G$ enthält entweder diese Kante oder nicht. Wir zeigen, dass es im ersten Fall eine Bijektion zu den Spannbäumen der Kontraktion $G / (e)$ und im zweiten Fall eine Bijektion zu den Spannbäumen von $G ∖ {e}$ gibt. Dies ist im zweiten Fall unmittelbar klar. Betrachten wir also die Spannbäume in $G$ , in denen $e$ vorkommt. Wenn man diese Kante herausnimmt, so erhält man einen Spannbaum von $G / (e)$ , da ja die Endpunkte von $e$ miteinander identifiziert werden und bei dieser Identifizierung wieder ein Baum entsteht. Es sei umgekehrt ein Spannbaum von $G / (e)$ gegeben. Dieser durchläuft jeden Punkt von $G / (e)$ , also auch den Kontraktionspunkt $[u] = [v]$ . Indem man die Kante $e$ an dieser Stelle einbaut, erhält man einen Spannbaum von $G$ .

◻

Im vorstehenden Lemma ist es durchaus erlaubt, dass der Graph nicht zusammenhängend ist (dann gibt es keine aufspannenden Bäume), oder dass durch die Herausnahme einer Kante der Zusammenhang verloren geht. Das Konzept Multigraph ist für die vorstehende Argumentation unverzichtbar, man denke etwa an einen Rundgang mit drei Knotenpunkten. Dieser hat offenbar drei Spannbäume. Wenn man eine Kante herausnimmt, so erhält man einerseits einen dreipunktigen Pfad und andererseits bei der Kontraktion einen zweipunktigen Graphen, wo aber zwei verbindende Kanten geerbt werden.

Beispiel

Wir betrachten den Diamantgraphen und führen die Kontraktionen und Herausnahmen wie im Bild durch. Dieser Algorithmus liefert letztlich $8$ lineare Graphen, die jeweils einen Spannbaum haben (und einen Spannbaum des ursprünglichen Graphen repräsentieren). Nach Lemma 21.11 gibt es also $8$ Spannbäume.

<< \| Kurs:Diskrete Mathematik (Osnabrück 2026) \| >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)