GATE CS 2018 (Forenoon) — Question 40

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsMCQ2 marks · −2/3 if wrongMedium

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. (I) 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\).) (II) For every edge \((u,v)\) of \(G\), if \(u\) is at depth \(i\) and \(v\) is at depth \(j\) in \(T_B\), then \(|i - j| = 1\). Which of the statements above must necessarily be true?
  1. A
    I only
  2. B
    II only
  3. C
    Both I and II
  4. D
    Neither I nor II
Practise the full 2018-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group