We are given a graph G = (V, E); G could be a directed graph or undirected graph. Let M be the adjacency matrix of G. Let n be the number of vertices so that the matrix M is n ×n matrix. For any matrix A, let us denote the element of i-th row and j-th column of the matrix A by A[i, j]. 1. Consider the square of the adjacency matrix M . For all i and j, show that M 2[i, j] is the number of different paths of length 2 from the i-th vertex to the j-th vertex. It should be explained or proved as clearly as possible. 2. For any positive integer k, show that M k[i, j] is the number of different paths of length k from the i-th vertex to the j-th vertex. You may use induction on k to prove it. 3. Assume that we are given a positive integer k. Design an algorithm to find the number of different paths of length k from the i-th vertex to j-th vertex for all pairs of (i, j). The time complexity of your algorithm should be O(n3 log k). You can get partial credits if you design an algorithm of O(n3k).
We are given a graph G = (V, E); G could be a directed graph or undirected graph. Let M be
the adjacency matrix of G. Let n be the number of vertices so that the matrix M is n ×n matrix. For any
matrix A, let us denote the element of i-th row and j-th column of the matrix A by A[i, j].
1. Consider the square of the adjacency matrix M . For all i and j, show that M 2[i, j] is the number of
different paths of length 2 from the i-th vertex to the j-th vertex. It should be explained or proved as
clearly as possible.
2. For any positive integer k, show that M k[i, j] is the number of different paths of length k from the i-th vertex to the j-th vertex. You may use induction on k to prove it.
3. Assume that we are given a positive integer k. Design an
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
