recategorized by
2,655 views
12 votes
12 votes

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

recategorized by

4 Answers

Best answer
11 votes
11 votes
  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

selected by
0 votes
0 votes
FE- (2,4),(1,3),(3,8),(4,8)

BE-(4,5)

CE-(3,7),(4,6)
0 votes
0 votes
edge from ancestor to descendant-→ forward edge

edge from descendant to ancestor-→ backward edge

edge from neither ancestor nor descendant-→ cross edge
0 votes
0 votes

Just run the DFS on given graph and take those edges which marked as “T”.

now you will get this tree and in this tree make the remaining edges that were not marked as” T”.

After drawing those edges it is easily inferred,

Forward edge: Not a tree edge and it is from ancestor to descendant.

here it is 2->4 and 1 → 3

Backward edge: Not a tree edge and it is from descendant to ancestor.

here it is  4 → 5

Cross edge: edges between those vertices that don’t have a relation of ancestor and descendant.

here it is 4 → 6;  4 → 8; 3 → 7; 3 → 8

 

 

{ In diagram, F → Forward  B → Backward C → Cross} 

 

Related questions

53 votes
53 votes
4 answers
1
26 votes
26 votes
1 answer
2
Kathleen asked Oct 9, 2014
5,107 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...
16 votes
16 votes
1 answer
3
Kathleen asked Oct 8, 2014
5,039 views
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).