Satz von Kirchhoff

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.

Aussage

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

${\frac {1}{n}}\lambda _{1}\lambda _{2}\cdots \lambda _{n-1}$

ist, wobei $\lambda _{1},\ldots ,\lambda _{n}$ die Eigenwerte der Laplace-Matrix des Graphen sind und $\lambda _{n}=0$ gilt.

Beispiel

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:

$L=\left({\begin{array}{rrrr}2&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&2\end{array}}\right)-\left({\begin{array}{rrrr}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{array}}\right)=\left({\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right).$

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 $=\det \left({\begin{array}{rrr}3&-1&-1\\-1&3&-1\\-1&-1&2\end{array}}\right)=8.$

Verallgemeinerungen

Der Satz von Kirchhoff lässt sich auf gewichtete Graphen $G=(V,E,w)$ 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

$\displaystyle \sum _{T\in S}\,\prod _{e\in T}w(e)$.

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 $\textstyle \prod _{e\in T}w(e)$ 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

Mit Hilfe des Satzes von Kirchhoff lässt sich die Cayley-Formel beweisen, welche besagt, dass es $n^{n-2}$ 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

$L_{n}:={\begin{pmatrix}n-1&-1&\cdots &-1\\-1&n-1&\cdots &-1\\\vdots &\vdots &\ddots &\vdots \\-1&-1&\cdots &n-1\\\end{pmatrix}},$

die nicht Null sind, geteilt durch n. Die Matrix $L_{n}$ 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 $n^{n-2}$ Spannbäume besitzt.

Literatur

• 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.

Weblinks

• Algebraische Graphentheorie (abgerufen am 29. Oktober 2015)
• Beispiel zum Matrix-Gerüst-Satz (abgerufen am 29. Oktober 2015)