I was given problem 6.7 out of the book "Networks: An Introduction" as a question. The problem is defined as follows:
Consider the set of all paths from node $s$ to node $t$ on an undirected network with adjacency matrix A. Let us give each path a weight equal to $\alpha^r$, where $r$ is the length of the path.
a) Show that the sum of the weights of all the paths from $s$ to $t$ is given by $Z_{st}$ which is the $st$ element of the matrix $Z = (I - \alpha A)^ {-1}$, where $I$ is the identity matrix
b) What condition must $\alpha$ satisfy for the sum to converge?
Where do I even start on this problem? Since the graph is undirected, I know that A must be a symmetric matrix. Other than that I don't quite know what more information there is to go on.
Asked By : vonludi
Answered By : aelguindy
A few hints:
- Find out what the entries of $A^2$ mean. How about $A^k$? (Start by a very small adjacency matrix, multiply it with itself and try to think what each entry means).
- Lookup and understand the Taylor expansion of $f(x) = 1/(1-x)$.
- Realize that the sum of weights of all paths from $s$ to $t$ is the sum of weights of paths of length 0, 1, 2, ...
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65010
0 comments:
Post a Comment
Let us know your responses and feedback