The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on here?
Question:
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 to 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 of $u$ and $v$ must be true?
- $post(u) < post(v)$
- $u$ is an ancestor of $v$ in $T$.
- If $w$ is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$.
I'm not going to post the answer just yet. If you're interested, it's available in the PDF:
http://www.ets.org/Media/Tests/GRE/pdf/CompSci.pdf
I think that none of these can be true, based on the following:
- If $u$ is an ancestor of $v$ and $v$ is a leaf, then this would be false because leaves are counted first by postorder traversal.
- If $u$ is a left sibling of $v$, then $u$ is counted first by preorder traversal, but $u$ is clearly not an ancestor of $v$.
- This statement is equivalent to #2, and could be false by the same argument.
I think it goes without saying that the test answers say I'm wrong about this. Am I missing something here? Can anyone provide an explanation as to why I'm wrong, as well as how to arrive at the correct answer?
Thanks!
EDIT:
Per Sadeq's request, I've included a counter example to #2/#3:
Counter Example http://img39.imageshack.us/img39/6410/counterexample.png
The graph $G$ is shown in the image. If we remove the edge between $A$ and $D$, then we get the tree $T$. Now we have the following:
- $(u,v)\in G - T$
- $pre(A) < pre(D)$
- $A$ is not an ancestor of $D$ in $T$.