2
$\begingroup$

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.

  • 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.2012-01-10
  • 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).2012-01-10
  • 0
    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$.2012-01-12

2 Answers 2

2

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.

  • 0
    A bit difficult to understand the underlying concept. Will try it out. Thanks.2012-01-10
  • 0
    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?2012-01-10
  • 0
    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.2012-01-12
1

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

  • 1
    Doesn't the answer depend on the particular graph rather than the size of the graph alone?2012-10-29