Ungerichteter Graph/Laplace-Matrix/Satz von Kirchhoff/Textabschnitt

Definition

Zu einem Multigraphen ${}G$ versteht man unter der Laplace-Matrix ${}L$ die Differenz

${}L=D-A\,$

aus Gradmatrix ${}D$ und Adjazenzmatrix ${}A$.

Mit Hilfe der Laplace-Matrix kann man die Anzahl von Spannbäumen berechnen, wozu wir zuerst ein Beispiel geben.

Beispiel

Wir betrachten den Diamantgraphen mit den Knoten ${}a,b,c,d$, bei dem ${}\{1,4\}$ die einzige Nichtkante ist. Die Adjazenzmatrix ist ${}A={\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{pmatrix}}$, die Gradmatrix ist ${}D={\begin{pmatrix}2&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&2\end{pmatrix}}$ und die Laplace-Matrix ist

${}L={\begin{pmatrix}2&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&2\end{pmatrix}}-{\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{pmatrix}}={\begin{pmatrix}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{pmatrix}}\,.$

Die Determinante der Streichungsmatrix zur ersten Zeile und ersten Spalte ist

${}\det {\begin{pmatrix}3&-1&-1\\-1&3&-1\\-1&-1&2\end{pmatrix}}=8\,.$

Diese Zahl stimmt mit der Anzahl der Spannbäume des Diamantgraphen, die in Beispiel berechnet wurde, überein.

Der folgende Satz heißt Satz von Kirchhoff und formuliert einen direkten Zusammenhang zwischen der Anzahl der Spannbäume und der Determinante von Streichungsmatrizen der Laplace-Matrix.

Satz

Es sei ${}G$ ein Multigraph und sei ${}L$ die Laplace-Matrix zu ${}G$. Es sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes.

Dann ist die Anzahl der Spannbäume von ${}G$ gleich der Determinante von ${}L'$.

Beweis

Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist ${}1$. Bei zwei Knoten und ${}m$ verbindenden Kanten gibt es ${}m$ Spannbäume. Die Adjazenzmatrix ist ${}{\begin{pmatrix}0&m\\m&0\end{pmatrix}}$ und die Gradmatrix ist ${}{\begin{pmatrix}m&0\\0&m\end{pmatrix}}$. Daher ist die Laplace-Matrix gleich ${}{\begin{pmatrix}m&-m\\-m&m\end{pmatrix}}$. Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante ${}m$. Es sei nun die Aussage für alle Multigraphen mit höchstens ${}n-1$ Knoten bewiesen, und sei eine Multigraph ${}G$ mit ${}n$ Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl ${}m$ der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon ist die Nullmatrix mit Determinante ${}0$. Es sei also die Aussage auch für alle Graphen mit ${}n$ Knoten und mit weniger als ${}m$ Kanten bewiesen, und ${}G$ habe ${}n$ Knoten und ${}m$ Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen ${}1$ und ${}2$ kontrahiert, wovon es ${}a_{12}\geq 1$ gibt. Die Laplace-Matrix von ${}G$ sei

${\begin{pmatrix}d_{1}&-a_{12}&-a_{13}&\ldots &-a_{1n}\\-a_{12}&d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Laplace-Matrix von ${}G\setminus \{e\}$ ist

${\begin{pmatrix}d_{1}-1&-a_{12}+1&-a_{13}&\ldots &-a_{1n}\\-a_{12}+1&d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

und die Laplace-Matrix zur Kontraktion ${}G/e$ ist die ${}(n-1)\times (n-1)$-Matrix

${\begin{pmatrix}d_{1}+d_{2}-2a_{12}&-a_{13}-a_{23}&\ldots &-a_{1n}-a_{2n}\\-a_{13}-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{1n}-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach

${\begin{pmatrix}d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}},$

${\begin{pmatrix}d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

${\begin{pmatrix}d_{3}&\ldots &-a_{3n}\\\vdots &\ddots &\vdots \\-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Entwicklung nach der ersten Spalte (für die beiden ersten Matrizen) zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit Fakt aus den beiden Induktionsvoraussetzungen.

$\Box$