Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 18

Da der Wurf ziemlich groß war, und Vorli als letzte geboren wurde, bekam sie wenig Milch ab. Die prallen Zitzen waren immer schon von den Geschwistern besetzt. Eine Zeitlang stand es kritisch um sie und sie musste von Hand aufgezogen werden.

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. 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},\ldots ,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\setminus \{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},\ldots ,v_{r}=v_{1}$ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in ${}G'$, und dieser ist auch ein aufspannender Baum von ${}G$.

$\Box$

Dieser Beweis zeigt zugleich, wie man einen aufspannenden Baum in einem zusammenhängenden Graphen finden kann. Nach Satz 17.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 zur zweiten Zeile überwechseln und diese rückwärts durchlaufen u.s.w. 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

Wie 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 abstakte Theorie von Unabhängigkeit beschreibt.

Definition

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

${}{\mathcal {M}}\subseteq {\mathfrak {P}}\,(E)\,$

ein Matroid, wenn folgende Bedingungen erfüllt sind.

1. Es ist ${}\emptyset \in {\mathcal {M}}$.
2. Aus ${}A\in {\mathcal {M}}$ und ${}B\subseteq A$ folgt ${}B\in {\mathcal {M}}$.
3. Wenn ${}A,B\in {\mathcal {M}}$ mit

   ${}{\#\left(A\right)}={\#\left(B\right)}+1\,,$

   so gibt es ein ${}a\in A\setminus B$ derart, dass ${}B\cup \{a\}\in {\mathcal {M}}$.

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

${\mathcal {M}}={\left\{J\subseteq I\mid {\text{Die Familie }}v_{j},j\in J,{\text{ ist linear unabhängig}}\right\}}\,$

und behaupten, dass es sich dabei um ein Matroid handelt. Die Eigenschaften ergeben sich aus Lemma 23.8 (Mathematik für Anwender (Osnabrück 2023-2024))  (1,2) und aus folgender Überlegung: Wenn die Teilfamilien ${}v_{j}$, ${}j\in J$ und ${}v_{\ell }$, ${}\ell \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

${}\langle v_{\ell },\ell \in L\rangle \not \subseteq \langle v_{j},j\in J\rangle \,.$

Daher gibt es auch ein ${}v_{k}$, ${}k\in L$, mit ${}v_{k}\notin \langle v_{j},j\in J\rangle$. 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 ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die maximalen Mengen aus ${}{\mathcal {M}}$ Basen.

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

Definition

In einem Matroid ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von ${}{\mathcal {M}}$ 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$ ü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 ${}{\mathcal {W}}(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 ${}{\mathcal {W}}(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.

Lemma

Es sei ${}G=(V,E)$ ein Graph mit ${}n$ Knotenpunkten und ${}c$ Zusammenhangskomponenten.

Dann lässt sich jeder Unterwald ${}(W,F)\subseteq (V,E)$ mit weniger als ${}n-c$ Kanten zu einem Unterwald mit ${}n-c$ Kanten ergänzen.

Beweis

Wir zeigen, dass wir den Wald unter der vorgegebenen Bedingung um eine Kante (eventuell unter Hinzunahme von weiteren Knotenpunkten) zu einem größeren Wald ergänzen können. Jede Zusammenhangskomponente des Waldes ${}(W,F)$ liegt ganz in einer Zusammenhangskomponente von ${}G$. Nach Satz 17.22 gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von ${}G$, d.h. wir können annehmen, dass ${}G$ zusammenhängend ist. Es sei

${}(B,H)\subseteq (W,F)\,$

ein Baum von ${}W$ (wenn ${}W$ leer ist, so können wir direkt zu einem einpunktigen Baum übergehen). Dieser besitzt weniger als ${}n-1$ Elemente. Sei ${}v\in V$ ein Punkt, der nicht in ${}B$ vorkommt. Es gibt einen Weg ${}u=u_{1},\ldots ,u_{n}=v$ in ${}G$ mit ${}u\in B$. Dabei findet irgendwo längs des Weges der Übergang von ${}B$ zu nicht ${}B$ statt, d.h. man kann davon ausgehen, dass ${}u_{2}=v\notin B$ ist. Wir nehmen die Kante ${}\{u,v\}$ (und eventuell den Punkt ${}v$) zu ${}W$ hinzu und müssen begründen, dass dies nach wie vor ein Wald ist. Bei ${}v\notin W$ ist

${}(B',H')=(B\cup \{v\},H\cup \{u,v\})\,$

nach Lemma 17.21 ein größerer Baum, da ja ${}v$ ein Blatt von ${}B'$ ist. Bei ${}v\in W$ wird ${}B$ mit einem anderen Baum aus ${}W$ vereinigt, was wieder einen Baum ergibt.

$\Box$

Satz

Zu einem Graphen ${}G=(V,E)$ ist die Waldmenge ${}{\mathcal {W}}(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$ und ${}Z$ Wälder von ${}G$ und Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle {{}} Z} enthalte eine Kante mehr als ${}W$. Es ist zu zeigen, dass man ${}W$ durch eine Kante aus ${}E$ zu einem größeren Wald ergänzen kann. Da aber die Anzahl der Kanten von ${}Z$ durch die Zahl aus Lemma 18.9 beschränkt ist, folgt aus dieser Aussage, dass man ${}W$ vergrößern kann.

$\Box$

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,\theta )$ besteht aus einer Knotenmenge ${}V$, einer Kantenmenge ${}E$ und einer Abbildung

$\theta \colon E\longrightarrow {\mathfrak {P}}_{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 über durch die Abbildung ${}\theta$ die beiden Punkte aus ${}\theta (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 ${}\theta$ 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. 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

Die Spannbäume des vollständigen Graphen ${}K_{4}$.

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\setminus e)+t(G/e)\,.$

Beweis

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\setminus \{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. 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$.

$\Box$

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 18.12 gibt es also ${}8$ Spannbäume.

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