Ungerichteter Graph/Spannbäume/Kirchhoff/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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 . Bei zwei Knoten und verbindenden Kanten gibt es Spannbäume. Die Adjazenzmatrix ist und die Gradmatrix ist . Daher ist die Laplace-Matrix gleich . Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante . Sei nun die Aussage für alle Multigraphen mit höchstens Knoten bewiesen, und sei eine Multigraph mit Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl 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 . Sei also die Aussage auch für alle Graphen mit Knoten und mit weniger als Kanten bewiesen, und habe Knoten und Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen und kontrahiert, wovon es gibt. Die Laplace-Matrix von sei

Die Laplace-Matrix von ist

und die Laplace-Matrix zur Kontraktion ist die -Matrix

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

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.