Follow Us :

Graph Algorithm 6

0. Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements:
I. No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD).
II. For every edge (u, v) of G, if u is at depth i and u is at depth j in TB, then |i – j | = 1.
Which of the statements above must necessarily be true?

  • Option : A
  • Explanation :
    Statement (i) is true.
    (i) No edges of G is a cross edge with respect to TD.
Cancel reply
Cancel reply