1
$\begingroup$

How could you prove:
An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the DFS tree. Question

So far I have understood that it does in fact imply that so I need to prove this. I have thought of doing it by contradiction but not exactly sure how I would go about doing that.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! If this exercise comes from an accessible source, please add a url or reference in the question. (Yeah, I know it might come from CLRS. But I could be wrong.) Please show how far you have got and where you got stuck and raise some specific question abou it, instead of just asking the community to do some exercise that is, I assume, designed for you to do. All above will motivate and help people help you faster and better. $\endgroup$ – Apass.Jack Nov 5 '18 at 13:35
  • $\begingroup$ @Apass.Jack Thanks a lot for the guidance, that's quite helpful to keep in mind. I have edited my question to include the details that you requested. $\endgroup$ – danigo991 Nov 5 '18 at 16:17
0
$\begingroup$

You conclusion is correct.

Here is (the sketch of) a proof.

  • If pre($u$) < pre($v$), the search must discover and finish $v$ before it finishes $u$, since $v$ is on $u$’s adjacency list. That is, post($v$) < post($u$) and $v$ is in the subtree rooted at $u$.

  • If pre($v$) < pre($u$), the search must discover and finish $u$ before it finishes $v$, since $u$ is on $v$’s adjacency list. That is, post($u$) < post($v$) and $u$ is in the subtree rooted at $v$.

$\endgroup$

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.