(3,8), (4,8) are cross edges as their discovery and finishing times are of form {d[u],f[u]} {d[v],f[v]}

2 votes

Provide short answers to the following questions:

In the graph shown above, the depth-first spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.

4 votes

Best answer

- A
**tree edge (T)**is an edge in a DFS-tree. - A
**back edge (B)**connects a vertex to an ancestor in a DFS-tree. (Includes a self-loop and this indicates the presence of a cycle) - A
**forward edge (F)**is a non-tree edge that connects a vertex to a descendent in a DFS-tree. - A
**cross edge (C)**is any other edge in graph $G.$ It either connects vertices in two different DFS tree or two vertices in the same DFS tree neither of which is the ancestor of the other.

For the given question,

- Forward Edges: $1 \to 3, 2 \to 4$
- Back Edges: $4 \to 5$
- Cross Edges: $3 \to 7, 4 \to 6, 3\to 8, 4\to 8$

These are marked in the below graph. Below each node, its discovery time is marked. An edge $(u,v)$ becomes a forward edge only if $d(u) < d(v).$

PS:

- An edge $(u, v)$ is a cross edge if and only if $d[v] < f[v] < d[u] < f[u].$ $(v$ is discovered and finished before $u$ is discovered$)$
- An edge $(u, v)$ is a back edge if and only if $d[v] < d[u] < f[u] < f[v].$ $(v$ is discovered first and before it finishes $u$ is discovered and finished$)$

Reference: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm