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

3) Determine the adjacency matrix of the graph below and use it to compute the number of walks of length 3 from 6 to 4. Furthermore, compute the number of cycles of length 3 which contain the vertex 4.

Theory

• Adjacency matrix
• Paths in adjacency matrices (german) $A_{i,j}^k$ gives the number of paths of length $k$ between the vertices $v_i,v_j$
• Matrix multiplication

Solution

$A=\left(\begin{array}{cccccccc}0& 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 0\end{array}\right)A^2=\left(\begin{array}{cccccccc}2& 0& 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 1& 1& 0& 1\\ 0& 0& 2& 0& 1& 1& 1& 0\\ 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 2& 1& 0& 1& 0& 1\\ 1& 1& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 1\end{array}\right)A^3=\left(\begin{array}{cccccccc}1& 2& 0& 0& 0& 0& 0& 2\\ 2& 1& 0& 0& 0& 0& 0& 2\\ 1& 1& 2& 0& 1& 1& 1& 1\\ 0& 2& 3& 2& 1& 1& 1& 1\\ 1& 1& 2& 1& 1& 2& 0& 2\\ 2& 2& 1& 2& 2& 1& 1& 1\\ 1& 1& 0& 0& 1& 1& 0& 2\\ 2& 0& 0& 0& 0& 0& 0& 1\end{array}\right)$

a) $A_{6,4}^3=2$

* $6-7-3-4$
* $6-5-3-4$

b) $A_{4,4}^3=2$

* $4-6-3-4$
* $4-5-4-4$