Satz von Kirchhoff

mathematischer Satz

Der Satz von Kirchhoff (auch Satz von Kirchhoff-Trent, oder Matrix-Gerüst-Satz) ist ein Satz aus dem mathematischen Gebiet der Graphentheorie, welcher nach Gustav Kirchhoff benannt ist. Der Satz besagt, dass die Anzahl der Spannbäume eines Graphen als Determinante einer aus dem Graphen gewonnenen Matrix berechnet werden kann. Daraus folgt insbesondere, dass diese Anzahl in polynomieller Zeit berechnet werden kann.

Der Satz sagt aus, dass die Anzahl der Spannbäume eines Graphen gleich einem diagonalen Kofaktor seiner Laplace-Matrix ist. Hierbei wird angenommen, dass der Graph zusammenhängend ist und keine Schleifen enthält. Die Laplace-Matrix eines Graphen erhält man, indem man von der Valenzmatrix (Diagonalmatrix der Knotengrade) die Adjazenzmatrix subtrahiert. Ein diagonaler Kofaktor ist die Determinante einer Untermatrix, die man durch das Streichen einer Zeile und einer Spalte mit derselben Nummer erhält. Alle diagonalen Kofaktoren der Laplacematrix liefern den gleichen Wert.

Die diagonalen Kofaktoren der Laplace-Matrix lassen sich über ihre Eigenwerte ausdrücken. Man erhält dadurch als äquivalente Formulierung, dass die Anzahl der Spannbäume eines Graphen gleich

 

ist, wobei   die Eigenwerte der Laplace-Matrix des Graphen sind und   gilt.

Beispiel

Bearbeiten
 
Ein Graph mit 4 Knoten und allen seinen 8 Spannbäumen.

Wir betrachten den vollständigen Graphen mit 4 Knoten, in dem 1 Kante entfernt wurde (wie im Bild rechts). Die Laplace-Matrix L des Graphen ergibt sich aus der Differenz von Valenzmatrix und Adjazenzmatrix wie folgt:

 

Die Anzahl der Spannbäume ergibt sich nun, indem man eine beliebige Zeile und entsprechende Spalte von L löscht und dann von dieser Matrix die Determinante bestimmt. Beim Löschen der ersten Zeile und Spalte erhält man:

Anzahl der Spannbäume  

Verallgemeinerungen

Bearbeiten

Der Satz von Kirchhoff lässt sich auf gewichtete Graphen   mit Kantengewichtsfunktion w verallgemeinern. Die Laplace-Matrix L ergibt sich in diesem Fall aus der gewichteten Adjazenzmatrix multipliziert mit −1, in der die Diagonalelemente so angepasst wurden, dass sich die Einträge in jeder Zeile zu Null aufaddieren. Sei S die Menge der Spannbäume in G, dann ist jeder diagonale Kofaktor von L gleich

 .

Diese Formel lässt sich am Beispiel von Graphen mit Mehrfachkanten gut verstehen. Dazu werden die mehrfachen Kanten in G gelöscht und die Gewichtsfunktion w wird so gewählt, dass sie die ursprüngliche Multiplizität der Kanten angibt. Jeder Spannbaum T im so gewichteten Graphen korrespondiert zu   Spannbäumen im ursprünglichen Graphen G. Demnach ist jeder diagonale Kofaktor der Laplace-Matrix des gewichteten Graphen gleich der Anzahl der Spannbäume von G.

Anwendungen

Bearbeiten

Mit Hilfe des Satzes von Kirchhoff lässt sich die Cayley-Formel beweisen, welche besagt, dass es   beschriftete Bäume mit n Knoten gibt. Beschriftet bedeutet hierbei, dass die Ecken durchnummeriert sind. Zum Beispiel sind die acht Bäume im Beispiel oben alle verschieden, wenn man sie beschriftet (wie dort geschehen); lässt man aber die Beschriftung weg, gibt es nur zwei verschiedene Bäume. Die Anzahl aller beschrifteten Bäume mit n Knoten ist gleich der Anzahl der Spannbäume des vollständigen Graphen mit n Knoten, also nach dem Satz von Kirchhoff gleich dem Produkt aller Eigenwerte der Matrix

 

die nicht Null sind, geteilt durch n. Die Matrix   besitzt einen Eigenwert 0, da der Rang der Matrix n-1 beträgt. Des Weiteren sind alle Vektoren, die an einer Stelle eine 1, an der folgenden Stelle eine −1 und sonst nur Nullen besitzen, Eigenvektoren mit den dazugehörigen Eigenwerten n. Da diese n-1 Vektoren linear unabhängig sind, sind die verbleibenden n-1 Eigenwerte demnach n. Es folgt, dass der vollständige Graph mit n Knoten   Spannbäume besitzt.

Literatur

Bearbeiten
  • Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag Wien New York, Wien 1996, ISBN 978-3-211-82774-1.
  • Lutz Volkmann: Graphen und Digraphen. Eine Einführung in die Graphentheorie, Springer Verlag Wien New York, Wien 1996, ISBN 978-3-211-82267-8.
Bearbeiten