TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 4

a) Compute the number of walks of length l from i to j in the graph (see image) by computing powers of its adjacency matrix.
b) How could you use the adjacency matrix to compute the number of triangles (i.e., cycles of length three) in a (loopless) graph? Perform the computation for two graphs of your choice on four vertices.

Lösungsvorschlag

a)

The paths of length l can be calculated as the sum of the values in $A(G)^{l}$, with A(G) as the adjacency matrix of a graph G
$A(G)^{1}=\left({\begin{array}{ccc}0&1&0\\1&0&1\\0&1&0\\\end{array}}\right)$ (Walks of length 1: 4)
$A(G)^{2}=A(G)*A(G)=\left({\begin{array}{ccc}1&0&1\\0&2&0\\1&0&1\\\end{array}}\right)$ (Walks of length 2: 6)
$A(G)^{3}=A(G)^{2}*A(G)=\left({\begin{array}{ccc}0&2&0\\2&0&2\\0&2&0\\\end{array}}\right)$ (Walks of length 3: 8)
$A(G)^{4}=A(G)^{3}*A(G)=\left({\begin{array}{ccc}2&0&2\\0&4&0\\2&0&2\\\end{array}}\right)$ (Walks of length 4: 12)
etc.

b)

Cycles are displayed in the diagonale of a power of an adjacency matrix, in this case $A(G)^{3}$.
As each triangle is counted twice for each vertex ("left around" and "right around" in the circle), divide the sum of the values of $A(G)^{3}$ by $3!$.