Ungerichteter Graph/Spannbäume/Kirchhoff/Fakt/Beweis/Aufgabe/Lösung

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.

Zur gelösten Aufgabe