Quelltext der Seite Satz von Kirchhoff

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

== Aussage ==
Der Satz sagt aus, dass die Anzahl der Spannbäume eines Graphen gleich einem diagonalen [[Minor (Mathematik)#Kofaktoren|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 [[Grad (Graphentheorie)|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 [[Eigenwert]]e ausdrücken. Man erhält dadurch als äquivalente Formulierung, dass die Anzahl der Spannbäume eines Graphen gleich
:<math>\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}</math>
ist, wobei <math> \lambda_1,\ldots,\lambda_{n}</math> die Eigenwerte der Laplace-Matrix des Graphen sind und <math>\lambda_n=0</math> gilt.

== Beispiel ==
[[Datei:Graph with all  its spanning trees.svg|mini|Ein Graph mit 4 Knoten und allen seinen 8 Spannbäumen.]]
Wir betrachten den [[Vollständiger Graph|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:

: <math>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).
</math>

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

== Verallgemeinerungen ==
Der Satz von Kirchhoff lässt sich auf [[Gewichteter Graph|gewichtete Graphen]] <math>G=(V,E,w)</math> 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  
:<math>\displaystyle \sum_{T \in S}\, \prod_{e\in T} w(e)</math>.

Diese Formel lässt sich am Beispiel von Graphen mit [[Multigraph|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 <math>\textstyle \prod_{e\in T} w(e)</math> 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 <math>n^{n-2}</math> beschriftete [[Baum (Graphentheorie)|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
:<math>
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},
</math>
die nicht Null sind, geteilt durch ''n''. Die Matrix <math>L_n</math> besitzt einen Eigenwert 0, da der [[Rang einer Matrix|Rang]] der Matrix ''n''-1 beträgt. Des Weiteren sind alle [[Vektor]]en, die an einer Stelle eine 1, an der folgenden Stelle eine −1 und sonst nur Nullen besitzen, [[Eigenvektor]]en mit den dazugehörigen Eigenwerten ''n''. Da diese ''n''-1 Vektoren [[Lineare Unabhängigkeit|linear unabhängig]] sind, sind die verbleibenden ''n-1'' Eigenwerte demnach ''n''. Es folgt, dass der vollständige Graph mit ''n'' Knoten <math>n^{n-2}</math> 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 ==
* [https://www.math.uni-hamburg.de/home/kriesell/agt.pdf Algebraische Graphentheorie] (abgerufen am 29. Oktober 2015)
* [https://i11www.iti.kit.edu/_media/teaching/sommer2008/graphdrawing/matrixgeruest.pdf Beispiel zum Matrix-Gerüst-Satz] (abgerufen am 29. Oktober 2015)


[[Kategorie:Satz (Graphentheorie)|Kirchhoff, Satz von]]
[[Kategorie:Gustav Robert Kirchhoff]]