Q35

MCQ2 marks, −0.67

Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search $\text{(BFS)}$ tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

(A)

There are no back-edges in $G$ with respect to the tree $T$

(B)

There are no cross-edges in $G$ with respect to the tree $T$

(C)

There are no forward-edge in $G$ with respect to the tree $T$

(D)

The only edges in $G$ are the edges in $T$

Loading…