World's most popular travel blog for travel bloggers.

[Solved]: Proof: Sum of weights of paths in a network

, , No Comments
Problem Detail: 

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback