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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
