1
$\begingroup$

Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.

How can I find the total number of paths in the graph that do not share any edge with the (unique) path from $a$ to $b$ and have only one vertex in common with it?

For example, suppose I have following graph : enter image description here

and am given $a=4$, $b=5$. Then there are six paths satisfying the above condition: $(1,1)$, $(1,3)$, $(2,2)$, $(2,6)$, $(4,4)$, $(5,5)$ where $(x,y)$ is the path from $x$ to $y$.

$\endgroup$
  • 1
    $\begingroup$ "the total number of paths in the graph that do not share any edge with the given path" Which path? With itself? $\endgroup$ – dkaeae Jun 11 at 7:03
  • $\begingroup$ do not share any edge with given path i.e the path from vertex a to b . you can go through the example that will clarify it more. $\endgroup$ – tanishq sharma Jun 11 at 7:12
  • 1
    $\begingroup$ You should probably make it clearer that, because the graph is acyclic (i.e., a forest), if a path exists from $a$ to $b$ (i.e., they are in the same component and, hence, in the same tree), then it is unique. $\endgroup$ – dkaeae Jun 11 at 7:14
  • $\begingroup$ I am failing to understand your doubt ,i will try to explain it once again . it is true that path from a to b will be unique , but we have to find pair of vertices (x,y) whose path does not share any edge with path (a,b) ,because if they do so then common vertices will be more than 1 . hence paths (x,y) which do not share any edge with (a,b) will have 0 or 1 vertices common with the path (a,b) , We have find the number pairs with 1 common vertex $\endgroup$ – tanishq sharma Jun 11 at 7:43
  • $\begingroup$ Your example is not clear. If you are given the actual path from $a$ to $b$ you should mention it clearly in the question, and write it in the example. Also note that not any acyclic graph has only one path between two vertices. $\endgroup$ – lox Jun 11 at 8:34
3
$\begingroup$

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes.

Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. You want to compute the number of different paths passing through $a$. There are two possibilities:

  • either $a$ has only one neighbour: then the possible paths are the $N$ paths ($a$, $i$) with $i \in N$
  • either $a$ has several neighbours: then count the number of vertices in the subtree of each of these neighbours. The number of possible paths is the sum of the cross-products more the $N$ paths having $a$ as start.

Note that $T$ may have between $n$ and $n^2$ paths through $a$.

To answer your question, just sum all the trees' number of paths.

EDIT: small examples

If the tree has 4 vertices called $a,b,c,d$, connected linearly like that $a-b-c-d$ with $a$ being the vertex of the given path. Then $a$ has only 1 neighboor and the possible paths are all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d)$]

If the tree has 5 vertices $a $(of the given path)$, b, c, d, e$ connected like that:

    b-a-c-d
      |
      e

Then $a$ has 3 neighboors leading to the 3 subtrees: $b, c-d$ and $e$. The possible paths are:

  • all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d), (a,e)$]
  • the cross-products between $b$ and $c-d$: [$(b, c), (b, d)$]
  • the cross-products between $e$ and $c-d$: [$(e, c), (e, d)$]
  • the cross-products between $b$ and $e$: [$(b, e)$]

total 10 paths.

$\endgroup$
  • $\begingroup$ can you please give me more information about the line ' The number of possible paths is the sum of the cross-products more the N paths having a as start ' and specifically ' cross-products more the N paths ' $\endgroup$ – tanishq sharma Jun 11 at 20:11
  • $\begingroup$ @tanishq sharma I added an example in my answer. "cross-products" is probably not the best word to describe this. It is just the analogy with multiplication, in my example $b*e*(c+d)$. $\endgroup$ – Vince Jun 13 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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