recategorized by
3,736 views
29 votes
29 votes

Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$. Let $u_{3}$ be the leaf that is farthest from $u_{2}$, and, in general, let $u_{i+1}$ be a leaf of $T$ that is farthest from $u_{i}$ (if there are many choices for $u_{i+1}$, pick one arbitrarily). The algorithm stops when some $u_{i}$ is visited again. What can u say about the distance between $u_{i}$ and $u_{i+1}$, as $i = 1, 2,...?$

  1. For some trees, the distance strictly reduces in each step.
  2. For some trees, the distance increases initially and then decreases.
  3. For all trees, the path connecting $u_{2}$ and $u_{3}$ is a longest path in the tree.
  4. For some trees, the distance reduces initially, but then stays constant.
  5. For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.
recategorized by

8 Answers

13 votes
13 votes

$\text{Option A: True}$ 

Distance is strictly reducing at each step.

 

$\text{Option B: True}$ 

Distance increasing initially from $U_1$ to $U_2$ to $U_3$ and decreasing from $U_3$ to $U_4$

 

$\text{Option D: True}$ 

Distance decreased and then remained constant.

 

$\text{Option E: True}$  

Thus for same tree, distance between last two vertices is different based on $U_1$. It is $4$ in first case and $3$ in second case.

 

$\text{Option C: False}$  

See the example for option $(A).$ The path connecting $U_2$ to $U_3$ is of length $4$. But it is not the longest path. The longest path is the one connecting $U_1$ and $U_2$ i.e., of length $5.$

 

 

edited by
2 votes
2 votes
answer is c. as it seems to be.

and actually thats the standard method of calculating the longest distance in a tree.
1 votes
1 votes
The problem is based on diameter of the tree, the diameter of the tree is is defined as a longest path or route between any two nodes in a tree. So there may be many pairs( u , v ) which have length equals to the diameter of the tree , once you find any node which is one end of the diameter then the node which present at maximum distance to it is another end of the diameter , and if you calculating this again and again , till you encounter the visited leaf again , then each and every time , you will go to new end of the diameter and each time you get the same distance. It means if you start with any leaf node u1 then it is not necessary that this node is one end of the diameter, now u2 is the node which is at maximum distance to it.. then definitely u2 node is one end of the diameter and u3 is maximum distance node to it (u2 - u3 ) is the diameter. and now if you proceed further, you will get the the same distance again and again till the last node....

So for some tree  it will give  x , y , y , y , y , y ..... where

x < y ( means initial starting node is not the end of diameter )

Otherwise  it will  give  y , y , y , y , y...  ( y = diameter ).

Option C is the correct answer.
Answer:

Related questions

8 votes
8 votes
2 answers
2
makhdoom ghaya asked Oct 30, 2015
1,780 views
Consider the differential equation $dx/dt= \left(1 - x\right)\left(2 - x\right)\left(3 - x\right)$. Which of its equilibria is unstable?$x=0$$x=1$$x=2$$x=3$None of the ab...