Subscribe to the weekly news from TrueShelf

## Graphs, Matrices and Walks

1. Let $G$ be a directed graph (possibly with self-loops) with vertices $v_1, \dots , v_n$. Let $M$ be the adjacency matrix of $G$. Prove that $M_{ij}^k$ (i.e., that $[i][j]^{th}$ entry of $M^k$) is equal to the number of length-$k$ walks from $v_i$ to $v_j$.

2. Using the above result, design an $O(n^{\omega})$ time algorithm to count the number of triangles (cycles of length 3) in a given directed graph. Here, $O(n^{\omega})$ is the running time of multiplying two matrices.

Source: folklore

0

0

0

0

0

0

0

0
0

0