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=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right),D_1=\left(\begin{array}{ccc}2& 0& 0\\ 0& 2& 0\\ 0& 0& 2\end{array}\right)=>D_1-A_1=\left(\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right)$

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

$|det\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)|=2\cdot 2-(-1)\cdot (-1)=4-1=3$

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

$A_2=\left(\begin{array}{ccccc}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{array}\right),D_2=\left(\begin{array}{ccccc}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{array}\right)=>D_2-A_2=\left(\begin{array}{ccccc}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{array}\right)$

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\left(\begin{array}{cccc}2& 0& 0& -1\\ 0& 1& 0& 0\\ 0& 0& 2& -1\\ -1& 0& -1& 3\end{array}\right)|$

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\left(\begin{array}{ccc}0& 0& -1\\ 0& 2& -1\\ 0& -1& 3\end{array}\right)|+(-1{)}^4\cdot 1\cdot |det\left(\begin{array}{ccc}2& 0& -1\\ 0& 2& -1\\ -1& -1& 3\end{array}\right)|+(-1{)}^5\cdot 0\cdot |det\mathrm{...}|+(-1{)}^6\cdot 0\cdot |det\mathrm{...}|$


$=1\cdot |det\left(\begin{array}{ccc}2& 0& -1\\ 0& 2& -1\\ -1& -1& 3\end{array}\right)|$


$=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$