Graph/Laplace-Matrix/Spannbaum/4/Aufgabe/Lösung

Die Adjazenzmatrix gleich

${\begin{pmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix}}$

und die Gradmatrix ist

${\begin{pmatrix}3&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&3\end{pmatrix}},$

somit ist die Laplace-Matrix gleich

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

Wenn man die erste Zeile und die erste Spalte streicht, so erhält man

${\begin{pmatrix}3&-1&-1\\-1&3&-1\\-1&-1&3\end{pmatrix}}.$

Deren Determinante ist

${}3(9-1)+(-3-1)-1(1+3)=24-4-4=16\,$

die Anzahl der Spannbäume ist also ${}16$.

Zur gelösten Aufgabe