3
$\begingroup$

Given an undirected connected graph with $N$ nodes and $N-1$ edges, a path $P_1P_2\cdots P_i$ is defined as follows:

  1. Nodes $P_j$ and $P_{j+1}$ are connected by an edge for each $\left({1}\right) <= \left({j}\right) <= \left({i}\right)$;

  2. The weight of a $Pth$ node is given as $P_k$;

  3. The number of indices $j$ with $\left({1}\right) < \left({j}\right) < \left({i}\right)$ such that $\left(P_{k_{j-1}}\right) < \left(P_{k_{j}}\right)$ and $\left(P_{k_{j}}\right) > \left(P_{k_{j+1}}\right)$ is at least Min and at most Max for some given Min and Max;

  4. Any node should not be repeated in that sequence ;

How many such paths are there?

$\endgroup$
  • $\begingroup$ Please use MathJax when formatting your question. See math.stackexchange.com/help/notation $\endgroup$ – user259242 Nov 5 '16 at 3:18
  • $\begingroup$ @user259242 Sorry,I will make sure to use it. $\endgroup$ – sammy Nov 5 '16 at 3:43
  • 1
    $\begingroup$ Your graph is a tree. I think that the answer depends on the graph shape, weights of its vertices, and given values of $Min$ and $Max$. $\endgroup$ – Alex Ravsky Nov 7 '16 at 9:01
  • $\begingroup$ Can someone please explain the second condition in detail? $\endgroup$ – Shin Kim Nov 7 '16 at 9:32
  • $\begingroup$ @AlexRavsky I fixed the question. Please check it out again. And the shape ,weight of it's vertices and value of $Min$ and $Max$ are given. $\endgroup$ – sammy Nov 7 '16 at 18:46
1
$\begingroup$

Without specific conditions imposed on the shape of the graph $G$, weights $w(v)$ of its nodes $v$, the given values $Min$ and $Max$ I can propose a straightforward algorithm, which has a complexity polynomial with the respect to the number of nodes of the graph $G$.

Let $v$ and $u$ be arbitrary nodes of the graph $G$. Let the number of peaks $p(v,u)$ be the number of indices $j$, ($1<j<i$) such that $w(v_{j-1})< w(v_{j})< w(v_{j+1})$, where $v=v_0,v_1\dots, v_{i-1}, v_{k}=u$ is the unique simple path between these nodes.

First of all we do a preprocessing which calculates the number of peaks $p(v,u)$ on the simple path between each pair $v$ and $u$ of nodes of the graph $G$ and the first node $n(v,u)$ on these path. This can be done recursively as follows. Let $v$ be a leaf of the graph $G$. Calculate the number of peaks and the first node on the simple path between each pair of nodes of the induced graph $G - v$. Let $u$ be a unique neighbor of the node $v$. Put $n(v,u)=u$, $n(u,v)=v$, and for each node $u’\ne u$ of the graph $G- v$ put $n(u’,v)=n(u’,u)$, $n(v,u’)=u$, and $$p(u’,v)=\cases{p(u’,u)+1, \mbox{if $w(v)<w(u)>w(n(v,u’))$},\\ p(u’,u), \mbox{otherwise}}.$$

Now the quantity which you are asking for is the number $N$ of pair $\{v,u\}$ of nodes of the graph $G$ such that

$$Min\le p(v,u)\le Max.$$

| cite | improve this answer | |
$\endgroup$

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.