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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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
4x4 grid spanning tree.svg

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 eines Graphen heißt aufspannender Baum von , wenn ein Baum mit der vollen Knotenmenge ist.

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



Satz  

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 ein zusammenhängender Graph mit Kanten. Wenn ein Baum ist, sind wir fertig. Sei also kein Baum. Dann gibt es einen Kreis

mit in . Wir betrachten den Graphen mit der gleichen Knotenmenge und der neuen Kantenmenge

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen und über das verbleibende „Kreissegment“ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in , und dieser ist auch ein aufspannender Baum von .


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 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 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 heißt eine Teilmenge

ein Matroid, wenn folgende Bedingungen erfüllt sind.

  1. Es ist .
  2. Aus und folgt .
  3. Wenn mit

    so gibt es ein derart, dass .

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


Beispiel  

Es sei ein -Vektorraum und sei , , eine Familie von Vektoren in zu einer endlichen Indexmenge . Wir setzen

und behaupten, dass es sich dabei um ein Matroid handelt. Die Eigenschaften ergeben sich aus Lemma 23.8 (Mathematik für Anwender (Osnabrück 2019-2020))  (1,2) und aus folgender Überlegung: Wenn die Teilfamilien , und , zu jeweils linear unabhängig sind, und ein Element mehr als besitzt, so gilt für die erzeugten Untervektorräume aus Dimensionsgründen

Daher gibt es auch ein , , mit . Doch dann ist die erweiterte Familie ebenfalls linear unabhängig.


Wegen dieses Beispiels nennt man die Mengen aus , 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 nennt man die maximalen Mengen aus Basen.

Ein ist also genau dann eine Basis, wenn keine Teilmenge mit zu gehört. Aufgrund der Austauscheigenschaft besitzt jede Basis in einem Matroid die gleiche Anzahl.


Definition  

In einem Matroid auf einer Menge nennt man die gemeinsame Anzahl der Elmente 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 eines Graphen heißt aufspannender Wald von , wenn ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von übereinstimmen.

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

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



Lemma  

Es sei ein Graph mit Knotenpunkten und Zusammenhangskomponenten.

Dann lässt sich jeder Unterwald mit weniger als Kanten zu einem Unterwald mit 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 liegt ganz in einer Zusammenhangskomponente von . Nach Satz 17.22 gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von , d.h. wir können annehmen, dass zusammenhängend ist. Es sei

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

nach Lemma 17.21 ein größerer Baum, da ja ein Blatt von ist. Bei wird mit einem anderen Baum aus vereinigt, was wieder einen Baum ergibt.




Satz  

Zu einem Graphen ist die Waldmenge (mit der vollen Knotenmenge)

ein Matroid auf .

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 ist ein Wald, bestehend aus den einpunktigen Bäumen. Ein Untergraph eines Waldes ist wieder ein Wald. Es seien nun und Wälder von und enthalte eine Kante mehr als . Es ist zu zeigen, dass man durch eine Kante aus zu einem größeren Wald ergänzen kann. Da aber die Anzahl der Kanten von durch die Zahl aus Lemma 18.9 beschränkt ist, folgt aus dieser Aussage, dass man vergrößern kann.


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.

Dipole graph.svg



Definition  

Ein Multigraph besteht aus einer Knotenmenge , einer Kantenmenge und einer Abbildung

Genauer spricht man von einem ungerichteten Multigraphen ohne Schleifen. In der Definition ist zunächst eine abstrakte Kantenmenge, wobei erst über durch die Abbildung die beiden Punkte aus miteinander „verbindet“. Einen Multigraphen kann man einfach skizzieren, indem man 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.

Shannon multigraph 5.svg

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 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 verstehen wir im Kontext von Multigraphen denjenigen Graphen, der entsteht, wenn die beiden Endpunkte von miteinander identifiziert werden und jede Kante des Ausgangsgraphen im Kontraktionsgraphen übernommen wird, entstehende Schleifen aber weggelassen werden. Insbesondere werden sämtliche Kanten, die mit Anfangs- und Endpunkt teilen, ebenfalls kontrahiert. Dabei kann aus einem einfachen Graphen ein Multigraph entstehen. Diese Kontraktion wird wieder mit bezeichnet.



Zur Anzahl von aufspannenden Bäumen
Die Spannbäume des vollständigen Graphen .



Lemma  

Es sei ein schleifenfreier Multigraph und eine Kante von .

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

Beweis  

Sei . Ein Spannbaum in enthält entweder diese Kante oder nicht. Wir zeigen, dass es im ersten Fall eine Bijektion zu den Spannbäumen der Kontraktion und im zweiten Fall eine Bijektion zu den Spannbäumen von gibt. Dies ist im zweiten Fall unmittelbar klar. Betrachten wir also die Spannbäume in , in denen vorkommt. Wenn man diese Kante herausnimmt, so erhält man einen Spannbaum von , da ja die Endpunkte von miteinander identifiziert werden. Sei umgekehrt ein Spannbaum von gegeben. Dieser durchläuft jeden Punkt von , also auch den Kontraktionspunkt . Indem man die Kante an dieser Stelle einbaut, erhält man einen Spannbaum von .


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  

Deletion-contraction.svg

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



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)