TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 11

Use the matrix tree theorem to compute the number of spanning forests of the graph below!

Solution

Step 1: Compute the number of spanning trees for component 1 (left).

$A_{1}={\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}},D_{1}={\begin{pmatrix}2&0&0\\0&2&0\\0&0&2\end{pmatrix}}=>D_{1}-A_{1}={\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix}}$

Remove any row and any column and calculate the determinant. I remove row 1 and column 1.

$|det{\begin{pmatrix}2&-1\\-1&2\end{pmatrix}}|=2\cdot 2-(-1)\cdot (-1)=4-1=3$

Step 2: Compute the number of spanning trees for component 2 (right).

$A_{2}={\begin{pmatrix}0&0&0&1&1\\0&0&0&0&1\\0&0&0&1&1\\1&0&1&0&1\\1&1&1&1&0\end{pmatrix}},D_{2}={\begin{pmatrix}2&0&0&0&0\\0&1&0&0&0\\0&0&2&0&0\\0&0&0&3&0\\0&0&0&0&4\end{pmatrix}}=>D_{2}-A_{2}={\begin{pmatrix}2&0&0&-1&-1\\0&1&0&0&-1\\0&0&2&-1&-1\\-1&0&-1&3&-1\\-1&-1&-1&-1&4\end{pmatrix}}$

Remove any row and any column and calculate the determinant. I remove row 5 and column 5 because it contains a lot of non-zero values. (Many zeros make it easier to calculate)

$|det{\begin{pmatrix}2&0&0&-1\\0&1&0&0\\0&0&2&-1\\-1&0&-1&3\end{pmatrix}}|$

I use the Laplace expansion along the second row to solve his. The second row has only 1 non-zero value and so it's fearly easy to calculate:

$(-1)^{3}\cdot 0\cdot |det{\begin{pmatrix}0&0&-1\\0&2&-1\\0&-1&3\end{pmatrix}}|+(-1)^{4}\cdot 1\cdot |det{\begin{pmatrix}2&0&-1\\0&2&-1\\-1&-1&3\end{pmatrix}}|+(-1)^{5}\cdot 0\cdot |det...|+(-1)^{6}\cdot 0\cdot |det...|$


$=1\cdot |det{\begin{pmatrix}2&0&-1\\0&2&-1\\-1&-1&3\end{pmatrix}}|$


$=12+0+0-2-0-2=8$

Step 3: Multiply the results to get the total number of possible spanning forests: $8\cdot 3=24$