retagged by
27,075 views
47 votes
47 votes

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.

  1. 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$).
  2. 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$.

Which of the statements above must necessarily be true?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II
retagged by

7 Answers

3 votes
3 votes
There are four types of edges can yield in DFS. These are tree, forward, back, and cross edges. In undirected connected graph, forward and back edges are the same thing. A cross edge in a graph is an edge that goes from a vertex v to another vertex u such that u is neither an ancestor nor descendant of v. Therefore, cross edge is not possible in undirected graph.
So, statement (I) is correct.

For statement (II) take counterexample of complete graph of three vertices, i.e., K3 with ABC, where A is source and B and C are in same level. Also,there is an edge between vertices B and C, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false.
0 votes
0 votes
Let $G$ be a simple undirected graph with two vertices $a$, $b$ and an edge ($a$, $b$). Clearly $T_D$ of this graph would be ($a$, $b$). From the given definition of cross edges, ($a$, $b$) is also a cross edge because $a$ or $b$, neither is an ancestor of the other in $T_D$. Therefore statement (I) must not necessarily be true.

Consider the following graph $G(V,E)$.

V={$a, b, c$}, E= {($a,b$), ($b,c$), ($a,c$)}

One of the breadth first search tree, $T_B$ = {($a,b$), ($a,c$)}

For edge ($b,c$) of $G$, $b$ and c vertices both are at the same depth in $T_B$. Depth difference for vertices $b$ and $c$ in $T_B$ equals to 0.  Therefore statement (II) must not necessarily be true.

Hence correct answer is (D).
Answer:

Related questions

35 votes
35 votes
9 answers
1
gatecse asked Feb 14, 2018
17,335 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...