0
$\begingroup$

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles.

What are other useful algorithms that use these labels?

$\endgroup$
1
$\begingroup$

Think of the following problem: Given a directed graph $G = (V,E)$, determine whether there is a pair of vertices $u, v$, s.t $u\neq v$ and $\mathit{and}$ there are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Hint: use the edge labels given by the $DFS$.

Solution:

If and only if there are any "cross" or "forward" arcs in the tree given by a $DFS$ tour on $G$, then a pair of vertices $u, v$ exists s.t are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Proof:

1. Suppose no "Cross" or "Forward" Arcs exist. Then the tree given by the $DFS$ is a directed tree, with some "Backwards" arcs. A tree by definition has only one path between every pair of vertices, and below it is shown backwards arcs only add new simple paths.

Consider the backward arc $(u,v)$:
$\bullet$ for all the ancestors of $v$, it only adds non simple paths.
$\bullet $ for all the descendants of $v$ and ancestors of $u$, denoted by $w$ (vertices between $u$ and $v$ on the tree), it adds one simple path from $w$ to any vertex below (including) $v$ and above (excluding) $w$. All these paths are new because the tree is directed, and all other paths are non-simple, because they contain a cycle.
$\bullet $ for descendants of $u$, it makes no difference.

2.
$\bullet$ Suppose a "Cross" arc exists between $(u,v)$. Then $u$ cannot be the root of the tree (the proof is trivial and omitted). Which means the following simple paths exist: $r \rightarrow v$, $r \rightarrow u$, $r \rightarrow u \rightarrow v$
$\bullet$ Suppose a "Forward" arc exists between $(u,v)$. Then $v$ is a descendant of $u$, but not a child of $u$, therefore there are at least two simple paths from $u$ to $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.