[Math] Total number of linear paths from any vertex to any other in an undirected graph

graph theory

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.

Best Answer

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.

Related Question