-3
$\begingroup$

A path is simple if no vertices are repeated. How many simple paths exist between two vertices in a complete graph?

One way is listing all simple paths using depth-first search. but I think it should be more simple to find the number of all simple paths between 2 nodes in a complete graph.

Here is the same problem but mine is for a complete graph: Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Improve this question
$\endgroup$
9
  • $\begingroup$ $countOfAllpathInClique(n)=\sum_{k=2}^n \binom{n}{k} \frac{k!}{2} = \Omega(2^n)$ $countPathBetween2vertices=countOfAllpathInClique(n-2)+2*(n-1)-1$ because we can assume we have a (n-2)clique + 2 other vertices. so after we computed the all path of (n-2)clique we should add 2*(n-1) new edge and one of them is not new. I'm not sure about the correctness of this. $\endgroup$
    – Ali
    Sep 1, 2014 at 6:35
  • $\begingroup$ Your question already contains what you claim to be an answer so I'm not sure what you're asking. $\endgroup$
    – David Richerby
    Sep 1, 2014 at 7:28
  • $\begingroup$ I'm Asking : How many simple paths between two vertices in n-clique? $\endgroup$
    – Ali
    Sep 1, 2014 at 8:58
  • 1
    $\begingroup$ How is this different from "how many s-t-paths are there in the complete graph"? Also, what have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Sep 1, 2014 at 10:59
  • $\begingroup$ I won't to compute the complexity of my algorithm,so i need the size of simple paths between two vertices. $\endgroup$
    – Ali
    Sep 1, 2014 at 13:51

1 Answer 1

Reset to default
0
$\begingroup$

$c(1)=0,$

$c(n)=(n-2)*c(n-1)+1$

suppose we have c(n-1) path in (n-1)-Complete Graph. when we add one more vertices, we add $(n-2)*c(n-1)$ new path and one for directed path.

the result is same as real:

  1. 0
  2. 1
  3. 2
  4. 5
  5. 16

  6. 65

    ===============================EDITED

    $c(n)=\sum_{i=0}^{n-2} \frac{(n-2)!}{i!}=(n-2)!*\sum_{i=0}^{n-2}\frac{1}{i!}$

    .

    This shows that's about $(2\text{≈}3)*(n-2)!$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This doesn't seem to answer the question. OK, you have a recurrence but what's the solution of that recurrence? $\endgroup$
    – David Richerby
    Sep 1, 2014 at 7:27
  • $\begingroup$ Thanks for you comment, I added the real value of the recurrence function. $\endgroup$
    – Ali
    Sep 1, 2014 at 9:49

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