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

Aussage

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}$ 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle = \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Mit Hilfe des Satzes von Kirchhoff lässt sich die Cayley-Formel beweisen, welche besagt, dass es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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)