Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Firstly, I'm not very good at exact graph terminologies.

I am given a graph as an adjacency matrix (it is undirected, unweighted and can be disconnected). I have to find total number of possible linear paths in the graph, i.e., in each path, edges should be unique. No two paths should have the same set of edges. Also vertices should not repeat in a path. I can't figure out the exact terminology for it.

Ex: for 5 vertices A,B,C,D,E: adjacency matrix is

  A  B  C  D  E
A 0  1  1  0  0
B 1  0  1  0  1
C 1  1  0  0  0
D 0  0  0  0  0
E 0  1  0  0  0

Therefore the possible linear paths are:

  • A->B
  • A->C
  • B->C
  • B->E
  • A->B->C
  • A->B->E
  • A->C->B->E

Thus total number of paths = 7. I only have to find total no. of such paths. I need to write a code for it. How can I write it optimally. The no. of vertices can be at max 50.

share|improve this question
2  
This isn't an answer, but note that if your adjacency matrix is $A$, then the entry $(A^n)_{ij}$ is the number of paths from vertex $i$ to vertex $j$ of length $n$. The diagonal entries will tell you how many loops of length $n$ you have, starting at each point (the trace giving you the total number of loops, the sum of all entries giving the total number of paths). What you need is some (recursive?) formula for the number of acyclic paths in terms of the number of paths. I will see if I can come up with anything. –  Aaron Jan 10 '12 at 6:28
2  
I suspect that this is a #P-complete problem, since the problem of counting s-t paths (i.e., paths connecting a fixed pair of endpoints) is #P-complete, as is the problem of counting all length-$n$ cycles (since that number is the permanent of the adjacency matrix). –  mjqxxxx Jan 10 '12 at 16:48
    
By the way, you've missed four paths in your example: $A \to C \to B$, $B \to A \to C$, $C \to A \to B \to E$ and $C \to B \to E$. –  Robert Israel Jan 12 '12 at 17:32
add comment

2 Answers 2

up vote 1 down vote accepted

With up to 50 vertices, the number of paths could be enormous: in a complete graph of 50 vertices (i.e. every vertex joined to every other vertex) there would be $41337038439638629286248290504650886651492243224669378150412649225$ of them: that's $\sum_{k=2}^{50} \frac{50!}{2 (50-k)!}$. Hopefully your graphs will be sparse enough that the number will be much more reasonable. You might try a recursive approach: if $P(i,S)$ is the number of paths starting with vertex $i$ and with all other vertices in set $S$, and $N(i)$ is the set of vertices $j$ such that $(i,j)$ is an edge, then $P(i,S) = \sum_{j \in N(i) \cap S} (1 + P(j,S \backslash \{j\}))$. Note that this will overcount the paths by a factor of 2.

share|improve this answer
    
A bit difficult to understand the underlying concept. Will try it out. Thanks. –  Andrew Jan 10 '12 at 9:17
    
By S∖{j}, you mean set S-{j}, isn't it? Wouldn't this create lots and lots of states. Would it feasible to run the code and get the result in a few seconds? –  Andrew Jan 10 '12 at 9:22
    
It may or may not be feasible, depending on the number of paths. Basically you're counting the paths one by one, so if there aren't too many this should be OK. –  Robert Israel Jan 12 '12 at 6:00
add comment

The number of paths through n points is (n-1)!/2.

share|improve this answer
    
Doesn't the answer depend on the particular graph rather than the size of the graph alone? –  Jonah Sinick Oct 29 '12 at 4:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.