Q30

MCQ2 marks, −0.67

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$ . Let $T_B$ be a breadth first search tree of $G$ . Consider the following statements. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II

(A)

No edge of $G$ is a cross edge with respect to $T_D$ . (A cross edge in $G$ is between two nodes neither of which is an ancestor of the other in $T_D$ ).

(B)

For every edge $(u, v)$ of $G$ , if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$ , then $\mid i-j \mid =1$ .

Loading…