Number of Walks of Length n¶
Using the adjacency matrix of a graph and defined matrix operations, we can provide an algorithm to determine the number of walks of length n. To understand this section, it is necessary to be familiar with the operation of matrix multiplication (a well-known operation) and have good intuition about it. You can search for matrix multiplication on the internet to familiarize yourself with it.
Consider two graphs with n vertices. For example, let's call the blue graph with adjacency matrix A and the red graph with adjacency matrix B. We want to find the number of walks between two vertices i and j that have two edges, where the first edge is blue and the second edge is red. We denote this number by \(C_{i,j}\). Clearly, to calculate this value we can consider all possible intermediate vertices (a vertex like k) then multiply the blue edges from i to k by the red edges from k to j, and sum the results over all possible k. Mathematically:
With careful attention, we can see that matrix C is equal to the matrix product of A and B.
The power of a matrix is defined similarly to the power of numbers, such that \(A^n\) means multiplying A by itself n times.
According to the theorem we demonstrated above, it can be concluded that the number of walks of length n from i to j is equal to the (i,j) entry in \(A^n\).
To prove this: For each walk of length n-1, place a red edge, and for each edge of the graph, place a blue edge. Clearly, every walk of length n corresponds to a walk with one red edge and one blue edge. Since \(A^n = A^{n-1}A\), the statement can be proven by induction.
Algorithm and Complexity¶
Therefore, to solve the problem, it is sufficient to compute matrix powers in reasonable time. Since matrix multiplication is associative (i.e., \((AB)C = A(BC)\)), the order of exponentiation does not matter. For even exponents:
And for odd exponents:
If we compute matrix multiplication using the naive algorithm with \(O(n^3)\) complexity, we can recursively compute \(A^k\) by first calculating \(A^{\lfloor\frac{k}{2}\rfloor}\) and then using the above relations. The time complexity of this recursive algorithm is:
This algorithm is called the fast exponentiation algorithm, which can be used whenever we need to repeatedly apply an associative operation to an element. For example, the same algorithm can be used for number exponentiation.
Generalization¶
The algorithm we examined here is not only used for computing the number of walks of fixed length, but can also be used to derive other properties of fixed-length walks (such as the largest walk or the walk with the minimum edge weight). For example, suppose we want to find a walk of length k between two vertices where the sum of edge weights is maximized. If we want to solve this problem for a graph with red and blue edges, considering walks that alternate between one red edge and one blue edge, the solution can be obtained as follows:
We can define matrix C as the combination of matrices A and B. Upon closer inspection, we can see that the combination operation is associative, similar to matrix multiplication. To prove this, consider a graph with red, blue, and green edges, and derive the maximum-weight red-blue-green walk using two different approaches. Thus, similar to before, we can define matrix powers and use induction to prove that \(A^k_{i,j}\) represents the maximum-weight walk of length k between vertices i and j, and that there exists an \(O(n^3lg(k))\) algorithm to compute this matrix.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
