The Gateway to Computer Science Excellence
+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.

in Graph Theory by Boss (30.7k points)
retagged by | 368 views

2 Answers

+4 votes
Best answer
  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).$


  • 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 (430k points)
selected by
0 votes
FE- (2,4),(1,3),(3,8),(4,8)


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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,692 users