1
$\begingroup$

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?

  1. $post(u) < post(v)$
  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$.

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:

  1. 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.
  2. 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$.
  3. 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:

  1. $(u,v)\in G - T$
  2. $pre(A) < pre(D)$
  3. $A$ is not an ancestor of $D$ in $T$.
$\endgroup$
3
  • 1
    $\begingroup$ Your illustration is not a depth-first search tree for this particular graph. Try it, run a depth-first search and see what happens. $\endgroup$ Sep 27, 2010 at 11:35
  • $\begingroup$ @Jukka: Yeah, I discussed that below. @Jake: Please see the discussion which I believe is clarifying. $\endgroup$ Sep 27, 2010 at 11:45
  • $\begingroup$ I've noticed that there are one or more images in your question which are hosted on ImageShack that have been erased and replaced by advertisements and are no longer recoverable. Do you have backup copies of these images you could upload here? Thank you! $\endgroup$
    – user35258
    Aug 25, 2015 at 6:06

1 Answer 1

5
$\begingroup$

First note that #2 and #3 are saying the same thing. Next, notice that if u is an ancestor of v in T, then in a pre-order traversal, we see u before v, and therefore pre(u) < pre(v). On the other hand, since T is a depth-first search tree (as opposed to an arbitrary tree) of the connected undirected graph G, and $(u,v) \in G-T$, we can deduce that pre(u)<pre(v) results in u being an ancestor of v.

The following image, taken from Wikipedia, can help:

Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)

Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

$\endgroup$
10
  • $\begingroup$ Yeah, was able to figure out the first part on my own. The problem with the second part is that I don't see how it would be necessary that $u$ be an ancestor of $v$. Doesn't my counter-example for #2 show that that statement isn't necessarily true for the conditions they've supplied? $\endgroup$
    – Jake
    Sep 27, 2010 at 7:11
  • $\begingroup$ Regarding the image you've attached - take vertices $A$ and $D$. $pre(A) < pre(D)$, but $A$ is not an ancestor of $D$. $\endgroup$
    – Jake
    Sep 27, 2010 at 7:17
  • $\begingroup$ Have you noticed the sentence Let (u,v) be an edge in G that is not in T at the beginning of the question? $\endgroup$ Sep 27, 2010 at 7:17
  • $\begingroup$ Yes, but I'm not clear on how it impacts the question other than specifying that $u$ and $v$ aren't adjacent. Is that the key to this? Can you elaborate a bit more? $\endgroup$
    – Jake
    Sep 27, 2010 at 7:23
  • $\begingroup$ @Jake: I'm very sorry if my explanation isn't clear. Yet I don't know how to clarify it more, since it seems obvious to me. Fortunately, there's a workaround (an intuition, not a proof): Try drawing a graph G as described by the problem, such that in its depth-first tree T, we have $(u,v) \in G-T$ and pre(u)<pre(v), but it violates the u is v's ancestor condition. If you succeed, send the link to the graph's image, and then I will know where the problem lies. Otherwise, you'll get a clear intuition as why it is correct. $\endgroup$ Sep 27, 2010 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.