Satz von Kirchhoff

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 beschrifteten Spannbäume eines Graphen in polynomieller Zeit über die Determinante einer aus dem Graphen gewonnenen Matrix berechnet werden kann.

Aussage[Bearbeiten]

Die Anzahl der Spannbäume eines Graphen entspricht einem Kofaktor seiner Laplace-Matrix. Die Laplace-Matrix eines Graphen erhält man, indem man von der Valenzmatrix (Diagonalmatrix der Knotengrade) die Adjazenzmatrix subtrahiert. Ein Kofaktor ist die Determinante einer Untermatrix, die man durch das Streichen einer Zeile und einer Spalte erhält. Alle Kofaktoren der Laplacematrix liefern den gleichen Wert.

Die 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-1} die Eigenwerte der Laplace-Matrix des Graphen sind, die nicht Null sind.

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:

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 die erste Zeile und Spalte von L löscht und dann von dieser Matrix die Determinante bestimmt. Man erhält:

Anzahl der Spannbäume  =
\det \left(\begin{array}{rrr}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 2
\end{array}\right)=8.

Verallgemeinerungen[Bearbeiten]

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 entspricht jeder Kofaktor von L

\displaystyle \sum_{T \in S}\, \prod_{e\in T} w(e).

Mit dieser Methode lassen sich Spannbäume in Graphen mit Mehrfachkanten bestimmen. 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 Multigraphen. Demnach entspricht der Kofaktor der Laplace-Matrix des gewichteten Graphen der Anzahl der Spannbäume des Multigraphen.

Anwendungen[Bearbeiten]

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. Die Anzahl aller Bäume mit n Knoten entspricht der Anzahl der Spannbäume des vollständigen Graphen mit n Knoten, also nach dem Satz von Kirchhoff, 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.