The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
262 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.

asked in Graph Theory by Boss (41.2k points)
retagged ago by | 262 views

2 Answers

+2 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).$

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

answered ago by Veteran (400k points)
selected ago by
0 votes
FE- (2,4),(1,3),(3,8),(4,8)

BE-(4,5)

CE-(3,7),(4,6)
answered by Active (1.3k 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]}

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
49,434 questions
53,630 answers
186,007 comments
70,899 users