Ungerichteter Graph/Spannbäume/Kirchhoff/1/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.