edited by
18,399 views
63 votes
63 votes

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true?

  1. $\{u, v\}$ must be an edge in $G$, and $u$ is a descendant of $v$ in $T$
  2. $\{u, v\}$ must be an edge in $G$, and $v$ is a descendant of $u$ in $T$
  3. If $\{u, v\}$ is not an edge in $G$ then $u$ is a leaf in $T$
  4. If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
edited by

4 Answers

Best answer
80 votes
80 votes

Let this be the DFS order of the tree, then,

$u= D$ and $v = F$

So, we conclude that

  1. It is not necessary that there is an edge between them.
  2. If there is no edge then $u$ must be leaf i.e. $D$ is leaf here.
  3. It is not always possible that $u$ and $v$ have same parent. But they have same ancestor.

Correct Answer: $C$

edited by
16 votes
16 votes
C is the correct answer..because it may happen that we read vertex u(leaf node) and hit a dead end and backtracking to vertex y(say) then searching for possibilites we read v ..so it is nt the case that u,v must have any descendant relationship .. You can try with random graphs and arrive at the same conclusion
8 votes
8 votes

OptionA is wrong.

Option B.>{u,v} must be an edge; this statement made it false . else it may correct.

Now consider below img

Here as per question v is immediately visited after u.

If part is satisfied for option C & D in above img of resultant Depth first tree traversal

But then part is satisfied for option C only.

So C is the correct ans.

0 votes
0 votes

 


In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.

Answer:

Related questions

79 votes
79 votes
10 answers
2
Kathleen asked Sep 14, 2014
22,582 views
Consider the following functions$f(n) = 3n^{\sqrt{n}}$$g(n) = 2^{\sqrt{n}{\log_{2}n}}$$h(n) = n!$Which of the following is true?$h(n)$ is $O(f(n))$$h(n)$ is $O(g(n))$$g(n...
15 votes
15 votes
3 answers
4
Kathleen asked Sep 14, 2014
7,915 views
Consider the syntax directed translation scheme $\textsf{(SDTS)}$ given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluat...