3
$\begingroup$

The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge according to whether $(u,v)$ or $(v,u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

Problem: What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?


The classification scheme is defined on page 609:

We can define four edge types in terms of the depth-first forest $G_{\pi}$ produced by a depth-first search on $G$:

  1. Tree edges are edges in the depth-first forest $G_{\pi}$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
  2. Back edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
  3. Forward edges are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
  4. Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

Added Example:

Consider the figure below.

dfs-undirected

Suppose that a DFS starts from node $u$ and travels along $(u,x)$ first and then $(x,v)$. Both $(u,x)$ and $(x,v)$ are tree edges.

What about the edge $(v, u)$? It should be a back edge according to the classification scheme in the textbook. How is $(v,u)$ classified as back edge according to the classification in the exercise?

Is $(v,u)$ a tree edge while $(u,v)$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $(u,v)$ and $(v,u)$ refer to the same edge.

$\endgroup$
  • 1
    $\begingroup$ The ordering refers to the order "tree edges, back edges, forward edges, cross edges". $\endgroup$ – Yuval Filmus Oct 21 '18 at 8:21
  • $\begingroup$ @YuvalFilmus Thanks. However, I am still confused. I have added an example to explain my confusion. Could you please have a look at it? $\endgroup$ – hengxin Oct 22 '18 at 5:41
2
$\begingroup$

I have reviewed section 22.3, "Depth-first search" a couple of times.

"What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $1 \prec 2 \prec 3 \prec 4$. In other words, tree edges precedes back edges, which precedes forward edges, which precede cross edges.


What is supposed to prove?

Suppose we have done a depth-first search $S$ on an undirected graph $G$ that has produced the depth-first forest $G_\pi$ as describe in the textbook.

An edge $e=\{u,v\}=\{v,u\}$ can be represented by either the directed edge $(u,v)$ or the directed edge $(v,u)$. Note that $(u,v)\not=(v,u)$. There are two ways to define the type of $e$ with respect to the search $S$.

  1. The earliest type of edge (according to that ordering) as which either $(u,v)$ or $(v,u)$ can be classified, then $e$ is classified as that kind of edge.
  2. If $(u,v)$ is discovered earlier than $(v,u)$, then e is the same type of edge as $(u,v)$. If $(v,u)$ is discovered earlier than $(u,v)$, then $e$ is the same type of edge as $(v,u)$.

That exercise asks readers to prove the above two definitions are equivalent. That is, $e$ is defined as type X by the first definition if and only if $e$ is defined as type X by the second definition, given any edge $e$ and any type $X$.

(Thanks to theorem 22.10, the first definition is the same as the following definition, the third definition. If either $(u,v)$ or $(v,u)$ is classified as a tree edge, then $e$ is a tree edge. Otherwise, either $(u,v)$ or $(v,u)$ is classified as a back edge and $e$ is a back edge. It is almost trivial to see the third definition is the same as the second definition)

(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)


Let us take a look at the example given in the question.

Here is the relevant part of the trace of running DFS-VISIT $(G,u)$.

  1. $u.d = 1$
  2. $x.\pi = u$
  3. $x.d = 2$
  4. $v.\pi = x $
  5. $v.d = 3$
  6. Now we discover edge $(v,u)$, which connects $v$ to $u$, which is an ancestor of $v$ since $v.\pi=x$ and $x.\pi = u$. That is, $(v,u)$ is a back edge. This is the first time edge $e$ is discovered. So $e$ is a back edge according to second definition.
  7. $v.f = 4$
  8. $x.f = 5$
  9. Now we discover edge $(u,v)$, which connects $u$ to its descendant $v$. This edge $(u,v)$ is classified as a forward edge. Since $(v,u)$ is classified as a back edge, a type of edges that precedes a forward edge, $e$ is a back edge according to the first definition.
  10. $u.f = 6$

We just saw that $e$ is classified as the same type of edge according to either definition. That exercise asks readers to prove that is not a coincidence.

$\endgroup$
  • $\begingroup$ Thanks. However, I am still confused. I have added an example to explain my confusion. Could you please have a look at it? $\endgroup$ – hengxin Oct 22 '18 at 5:40
  • $\begingroup$ :) I am waiting (both on the Internet and in my university). $\endgroup$ – hengxin Oct 22 '18 at 6:01
  • $\begingroup$ OK. Now I think I understand it. I have misunderstood the statement in the exercise as "classifying $(u,v)$ as a tree edge if $(u,v)$ is encountered before $(v,u)$, otherwise classifying it a back edge". To make sure: Each edge $\{u,v\}$ will be encountered twice in a DFS. The definition in the text uses the first "type" according to the ordering, and that in the exercise uses the type the first "time" the edge is classified. Is this right? $\endgroup$ – hengxin Oct 22 '18 at 12:40
  • $\begingroup$ Great thanks for your efforts (Please wait for my reviews for your other answers to my questions). $\endgroup$ – hengxin Oct 22 '18 at 12:45
  • $\begingroup$ Yes, that is correct. Either the earlier "type" or the first "time". That is, the first time always goes together with the earlier type. $\endgroup$ – John L. Oct 22 '18 at 12:54

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.