2
$\begingroup$

Suppose we are given a tree $T=(V,E)$ where $|V|=10$. Now, one of the vertices is goal and we want to find it. The structure of the tree is given as input, but which vertex is the goal is unknown. In each time step, we can visit a arbitrary vertex $v$ and find out which edge of $v$ is nearest to goal.

What is the number of times we visit nodes to identify which node is the goal? If we visit $v$ and find out its neighbor $u$ is goal, we don't need to visit $u$.

I read this link, but the answer is $3$, how we get the answer $3$? This question come from an interace exam of university and it's not homework.

$\endgroup$
2
  • $\begingroup$ What are the operations that we are allowed to perform on the graph? What are the inputs to the algorithm? What is known? The task doesn't seem very clear. $\endgroup$
    – D.W.
    Nov 27 '21 at 22:53
  • $\begingroup$ I have edited the question based on comments from others. In the future I hope you can provide these details when you initially ask. $\endgroup$
    – D.W.
    Nov 28 '21 at 5:53
1
$\begingroup$

Give a tree and a node $u$ in it. Consider $u$ as the root of the tree. If there is no more than $n/2$ nodes in every subtree (except the whole tree), we will call $u$ a center of that tree. A tree can have multiple centers.

Fact: A tree has at least one center.
Proof: Select an arbitrary node $u_1$. If $u_1$ is a center, we are done. Otherwise, suppose the subtree at $u_2$ of the tree rooted at $u_1$ has more than $n/2$ nodes. Now we consider $u_2$. If $u_2$ is a center, we done. Otherwise, repeat the process. Since the number of nodes in the most popular subtree is strictly decreasing, in the end, we will find a center.


As in the question, suppose we are given a tree $T=(V,E)$ that $|V|=10$.

  • Pick $v_1$, an arbitrary center of $T$. If $v_1$ or one of its neighbors is the goal, we have found the goal with $1$ visit.
  • Otherwise, let $u_1$ be the root of $T$. We know which edge that is incident to $v_1$ is nearest to goal. In other words, we know which subtree contains the goal. Let that subtree be $T_1$, which has no more than $10/2=5$ nodes.
    • Pick $v_2$, an arbitrary center of $T_1$. If $v_2$ or one of its neighbors is the goal, we have found the goal with $2$ visits.
    • Otherwise, let $u_2$ be the root of $T_1$. We know which edge in $T_1$ that is incident to $v_2$ is nearest to goal. In other words, we know which subtree of $T_1$ contains the goal. Let that subtree be $T_2$, which has no more than $5/2=2.5$ nodes, i.e., which has at most $2$ nodes.
      • Pick $v_3$, an arbitrary node in $T_2$. The goal is either $v_3$ or the other node in $T_2$ that is connected to $v_3$ if it exists. So we have found the goal with $3$ visits.

In summary, $10\ \rightarrow\ 10//2=5\ \rightarrow\ 5//2 = 2$.


Exercise. Explain that it is enough for $3$ visits to find the goal if $|V|=12$.

$\endgroup$
4
  • $\begingroup$ oops, I should prove that 2 visits will not guarantee to find the goal. Well, if the tree is a path, 3 visits will be needed in worst case since the goal might be any one of 4 potential nodes after 1 visit, which may not be resolved always after another visit. $\endgroup$
    – John L.
    Nov 27 '21 at 12:49
  • $\begingroup$ If we can do the operation "pick a center and visit it", why can't we do the operation "pick the goal and visit it"? The question doesn't seem very well-defined. $\endgroup$
    – D.W.
    Nov 27 '21 at 22:53
  • $\begingroup$ We do not know which node is the goal, although we do know the structure of the tree. And whenever we pick/explore a node, we can "find out which edge of v is nearest to goal" (and whether the current node is the goal). $\endgroup$
    – John L.
    Nov 28 '21 at 2:49
  • 1
    $\begingroup$ Ahh, thank you for the explanation. (I wish that had been stated in the question.) $\endgroup$
    – D.W.
    Nov 28 '21 at 5:51

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.