Re: (graph theory: path problem)how to tell how many path are there from s to t in a graph?

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/12/04 

Date: Mon, 12 Apr 2004 12:32:51 -0600

By the way:

On 12 Apr 2004, Alfred Kerns wrote:

> The problem is there will be some repetitions in that some nodes will
> be traversed twice or more times...

  It is common knowledge that the "number of k-length-paths" between i and
j found by the matrix A^k are not simple paths (i.e. vertices can and will
be repeated.)
  This is not exactly an undesirable result. For instance, as I mentioned
in the last post, the diagonal entries of A^2 are the degree of each
vertex, so the trace (sum of diagonal) tr(A^2) = 2*edges. Similarly, the
diagonal entries of A^3 will only be nonzero in the case that there exists
a triangle in the graph, so this gives a Matrix-Multiplication-Time
algorithm to find a clique of size 3 (or to even determine whether there
exists one) instead of the straightforward O(n^3) time method of checking
every set of 3 vertices.
  Also, instad of keeping n^2 entries of a matrix for a graph, is one only
keeps the eigenvalues of the adjacency (called the "spectrum" of a graph,
as has only O(n) members), one can retrieve the number of vertices of the
graph, the number of edges, the number of triangles, and some other
properties (as the sum of the eigenvalues is equal to the trace of the
matrix, and the sum of the k^th powers of the eigenvalues is equal to the
trace of the k-th power of the adjacency matrix.)

> In the third matrix, it says the number of length-3 path from 1 to 2
> is 4, but actually there is only 1 such path...

  You started with a 4-clique... why would you say there is only one
3-path? If the vertices are 1,2,3,4 and you are counting the number of
3-paths from 1 to 4, you have
1-2-3-4
1-3-2-4
And counting non-simple paths, you get:
1-4-2-4
1-4-3-4

And since you kept wiping out the diagonal entries (i.e. you wiped out the
paths that return to the start vertex), you lost out on the paths
1-2-1-4
1-3-1-4

J

Relevant Pages

  • Quantum Gravity 170.98: Eigenvalue Symmetry About 0 in Graph Theory
    ... Take a look at Wikipedia's "Graph theory," which defines adjacency ... A Laplacian matrix is defined as degree matrix - adjacency ... Next consider "Integer symmetric matrices having all their eigenvalues ...
    (sci.physics)
  • Re: Drawing graphs by hand
    ... All of the actual graph layout algorithms ... > so I was wondering if anybody has good rules of thumb for drawing ... You can get some hint of how to arrange a somewhat larger graph by ... associated with the smallest non-zero eigenvalues can be used ...
    (sci.math)
  • Re: Changes in Eigenvalues related to graphs
    ... to a graph affects eigenvalues of matrices associated with graph -such ... of the symmetric adjacency matrix by one, ... Eigenvalues of the adjacency matrix of tetrahedral graphs (English) ...
    (sci.math.num-analysis)
  • Re: (graph theory: path problem)how to tell how many path are there from s to t in a graph?
    ... > diagonal entries of A^3 will only be nonzero in the case that there exists ... > graph, the number of edges, the number of triangles, and some other ... > properties (as the sum of the eigenvalues is equal to the trace of the ... and the sum of the k^th powers of the eigenvalues is equal to the ...
    (comp.theory)
  • Re: Matrices query ?
    ... You know the sum of A's diagonal entries, ... amounts to the sum of A's eigenvalues. ... do you know the determinant ...
    (sci.math)