#65 ETS Practice -- Search tree of graph

[Aniviel]

Hi all. I'm looking at #65 in the latest ETS practice exam; it reads:

65. Let T be a depth-first search tree of a connected undirected graph G. For each vertex v of T, let
pre(v) be the number of nodes visited up to and including v during a preorder traversal of T , and
post(v) 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 (u,v) be an edge in G that is not in T, such that pre(u) < pre(v).
Which of the following statements about u and v must be true?
I. post(u) < post(v)
II. u is an ancestor of v in T.
III. If w is the lowest common ancestor of u and v in T, then w = u.

(A) I only (B) II only (C) III only (D) I and II (E) II and III

The correct answer is

SPOILER: E

and I just don't understand why condition II is necessarily true. I'm thinking I can construct a simple counterexample where node n is the parent of u and v, with u being the left child and v being the right child. A preorder traversal visits the nodes in order: n,u,v, making pre(u) < pre(v). There is no edge between u and v in the tree, but this tree could be derived from a complete graph of the three nodes, with the starting point for the search being node n, allowing the edge (u,v) to exist in G but not in T. What am I missing?

Thanks!
-Stacy

P.S. Are the questions generally increasing in difficulty as you go through the exam, or did I just lose my mojo for the second half of this test?

[Enigma211]

Case-I can proved to be false.
Case-II: I believe that your example proves it false.

I am not even sure, case-III is true either. Consider a tree
Root=W
left(w)=x; right(w)=u
left(u)=y;right(u)=z
left(z)=a;right(z)=v

In this case u = grandparent of v. Pre(u)<Pre(v); w= the lowest common ancestor and u!=w

Thoughts ?

[zorthian]

Originally Posted by Aniviel

Hi all. I'm looking at #65 in the latest ETS practice exam; it reads:



The correct answer is

SPOILER: E

and I just don't understand why condition II is necessarily true. I'm thinking I can construct a simple counterexample where node n is the parent of u and v, with u being the left child and v being the right child. A preorder traversal visits the nodes in order: n,u,v, making pre(u) < pre(v). There is no edge between u and v in the tree, but this tree could be derived from a complete graph of the three nodes, with the starting point for the search being node n, allowing the edge (u,v) to exist in G but not in T. What am I missing?

Thanks!
-Stacy

P.S. Are the questions generally increasing in difficulty as you go through the exam, or did I just lose my mojo for the second half of this test?

In the complete graph of three nodes that you mention,
V = { n,u,v} & G = { nu, nv, uv }, the DFS tree of this graph will have the edges {nu, uv} i.e 'v' will be reached via 'u' and not via 'n'. Since this DFS tree has the edge 'uv', it does not satisfy the condition stated in the problem.

Intuitively: The fact that (uv) is an edge in the graph, but does not appear in the tree implies that 'v' was visited through some child of 'u' ( 'u' was visited before 'v', since we are told that pre('u') < pre(v) ).

Condition III follows from II.

Best,
Zorth.