Test by Bikram | Mock GATE | Test 2 | Question: 27

Question

Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$,

Let pre$\left ( v \right )$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$ , and post$\left ( v \right )$ means greater than and equal to  be the number of nodes visited up to and including $v$ during a postorder traversal of $T$.

The lowest common ancestor of vertices $u$ and $v$ in $T$ is a vertex $w$ of $T$ such that $w$ is an ancestor of both $u$ and $v$, and no child of w is an ancestor of both $u$ and $v$.

Let $\left ( u, v \right )$  be an edge in G that is not in T, such that pre$\left ( u \right )$ $<$ pre$\left ( v \right )$ . Which of the following statements about $u$ and $v$ must be true?

1. post$\left ( u \right )$  $<$ post$\left ( v \right )$ 
2. $u$ is an ancestor of $v$ in $T$.
3. If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.

• A. II only
• B. III only
• C. I and II
• D. II and III

Comments

@saurav singh

read the best chosen answer,

what Anusha draw is BFS not DFS and this question is about DFS , also read this http://jeffe.cs.illinois.edu/teaching/algorithms/notes/19-dfs.pdf page 3 

---

what if the original graph was itself the dfs tree,3 option is clearly wrong.

---

Hi @Bikram

Sir

Is it even possible for graph G to have edge u to v. Such  that it is not include in DFS of grapg G. Can you draw one such example?

Answer 1

II) True - 

As we know pre(u) < pre(v) , that means u is explored before v in the dfs

 Given - (u, v) be an edge in G that is not in T ,

so that means there is another path to reach from u to v , like u -> x -> v ( had there been no other path , direct edge from u to v would be selected when performing Dfs)

This satisfies II)

III) is also true based on the above.

So option D.

[ see Anusha's example and apply the above . And dont get confused with Anscestor and Parent, the question says anscestor ]

Comments

Really good explanation. Thanx

---

No.Just take the initial graph as the same dfs tree.

---

Useful: Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/

Answer 2

ans should be C. for sentence I we can understand with any sample tree.

for sentence III w is lowest common ancestor of v. that mean an edge(w,v) is there. now if we take w=u than edge (u,v) will be there.  but it is already given in question that (u,v) is not present in T. so III is false.

Comments

No, Sheshang , you are wrong.

Read above answer .