279 views

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.

retagged | 279 views

1. tree edge (T) is an edge in a DFS-tree.
2. 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)
3. forward edge (F) is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
4. 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$)$
by Veteran (416k points)
selected
FE- (2,4),(1,3),(3,8),(4,8)

BE-(4,5)

CE-(3,7),(4,6)
by Active (1.2k points)
+1
(3,8), (4,8) are cross edges as their discovery and finishing times are of form {d[u],f[u]} {d[v],f[v]}

+1 vote
1
2