2
$\begingroup$

I am reading chapter 3 Decomposition of Graphs of Algorithms by Dasgupta, Papadimitriou & Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, back and cross edges. I have pasted the image of the area I am unclear on.

I am assuming that u is the node/vertex we see first and then we see v later. Comparing to the 2nd image showing the definitions on a graph, I am taking u as node A.

What I don't get is the order for the other 2 back and cross edges. What I have is

  • u v u v for back edge.
  • u u v v for cross edge.

Essentially the order is flipped with u and v in what the textbook has. Could someone clarify why this is the case with the image below.

Edge types

Edge definitions

I read this answer but I came out more confused with the explanation.

Surprisingly I was able to correctly identify the pre and post numbers in this figure in the textbook. It is the letters u and v that have me confused.

enter image description here

$\endgroup$
1
  • $\begingroup$ I did both. Sorry for the delay. I also have a follow up on the exercise portion of your answer. $\endgroup$ Mar 2 '21 at 22:55
2
$\begingroup$

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible.

The right assumption consists of two parts.

  • We are given a directed graph that contains $(u,v)$, the edge from $u$ to $v$.
  • We have just completed one depth first search (DFS) on that graph, which has discovered both $u$ and $v$.

Given the assumption above, that table lists the correspondence between the "pre/post ordering for $u$ and $v$", and the "edge type" of $(u,v)$. Please note that I rephrase "pre/post ordering for $(u,v)$" as in the table to "pre/post ordering for $u$ and $v$", since the meaning of "$(u,v)$", the edge from $u$ to $v$ does not fit the former phrase exactly.

  • The first row, "$\stackrel{[}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{]}{u}\ $ Tree/forward" says that $u$'s discovery time and departure time enclose $v$'s discovery time and departure iff $(u,v)$ is a tree edge or a forward edge. $u$ is visited first in this case.
  • The second row, "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{]}{v}\ $ Back" says that $v$'s discovery time and departure time enclose $u$'s discovery time and departure time iff $(u,v)$ is a back edge. $v$ is visited first in this case.
  • The third row, "$\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\ $ Cross" says that $v$'s discovery time and departure time are before $u$'s discovery time and departure time iff $(u,v)$ is a cross edge. $v$ is visited first in this case.

Neither do we assume $u$ is visited first nor do we assume $v$ is visited first. The node that is visited first on each row of that table is, of course, the node that appears first from the left on that row.


Exercise (as given in the book). With the same assumption, "do you see why no other orderings are possible?" For example, why is "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{v}\,\stackrel{]}{u}$" not possible? why is "$\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}$" not possible?

$\endgroup$
5
  • $\begingroup$ Thanks for mentioning the order is not set. I should always consider that the edge begins at $u$ and ends at $v$. Doing so makes the ordering in the table sensible. $\endgroup$ Feb 12 '21 at 18:39
  • $\begingroup$ I think the answer the exercise/your question has two parts. One, there aren't other possibilities of edges in the same connected component of a directed graph. Second, we can't have those orderings unless we are considering the pre and post numbers of different/distinct connected components. Are both parts correct? $\endgroup$ Feb 12 '21 at 18:42
  • $\begingroup$ @heretoinfinity, it looks like you are on the right track. For a directed graph, the notion of "connected component" is usually not defined. For example, it is not defined in the book hereof. Instead, we usually talk about "strongly connected component". $\endgroup$
    – John L.
    Feb 12 '21 at 22:18
  • $\begingroup$ Following up on the exercise and my response. Is there something I am missing? $\endgroup$ Mar 2 '21 at 22:54
  • $\begingroup$ Probably not. You could also take a look at the end of the source of my post, which answers the exercise. $\endgroup$
    – John L.
    Mar 3 '21 at 6:26

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.