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