Ungerichteter Graph/Laplace-Matrix/Satz von Kirchhoff/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Zu einem Multigraphen versteht man unter der Laplace-Matrix die Differenz

aus Gradmatrix und Adjazenzmatrix .

Mit Hilfe der Laplace-Matrix kann man die Anzahl von Spannbäumen berechnen, wozu wir zuerst ein Beispiel geben.


Beispiel  

Graph with all its spanning trees.svg

Wir betrachten den Diamantgraphen mit den Knoten , bei dem die einzige Nichtkante ist. Die Adjazenzmatrix ist , die Gradmatrix ist und die Laplace-Matrix ist

Die Determinante der Streichungsmatrix zur ersten Zeile und ersten Spalte ist

Diese Zahl stimmt mit der Anzahl der Spannbäume des Diamantgraphen, die in Beispiel berechnet wurde, überein.


Der folgende Satz heißt Satz von Kirchhoff und formuliert einen direkten Zusammenhang zwischen der Anzahl der Spannbäume und der Determinante von Streichungsmatrizen der Laplace-Matrix.



Satz  

Es sei ein Multigraph und sei die Laplace-Matrix zu . Es sei die Streichungsmatrix von bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von gleich der Determinante von .

Beweis  

Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist . Bei zwei Knoten und verbindenden Kanten gibt es Spannbäume. Die Adjazenzmatrix ist und die Gradmatrix ist . Daher ist die Laplace-Matrix gleich . Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante . Sei nun die Aussage für alle Multigraphen mit höchstens Knoten bewiesen, und sei eine Multigraph mit Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon ist die Nullmatrix mit Determinante . Sei also die Aussage auch für alle Graphen mit Knoten und mit weniger als Kanten bewiesen, und habe Knoten und Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen und kontrahiert, wovon es gibt. Die Laplace-Matrix von sei

Die Laplace-Matrix von ist

und die Laplace-Matrix zur Kontraktion ist die -Matrix

Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach

Entwicklung nach der ersten Spalte (für die beiden ersten Matrizen) zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit Fakt aus den beiden Induktionsvoraussetzungen.