retagged by
27,093 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

Best answer
51 votes
51 votes
  1. Undirected graph cant have cross edges in DFS forest. (Only directed graphs can have)  ( Hence I is True)
    (If you do not agree just try it with taking examples. You cant draw)
     
  2. Just draw a triangle SAB. Source is S. Vertex A and B are at same level hence distance $1$.  So here $| i - j | = 0$.   (Hence II is false)


Hence answer is (A).

Anyway, II is simple to understand from the above explanation.
Those who did not get I, you may see Theorem $22.10$ in Cormen)

edited by
13 votes
13 votes
Undirected graphs can't contain forward edges and cross edges since in those cases, edge $(v,u)$ would have already been traversed during DFS before we reach $u$ and try to visit $v$.

Let's say $(u,v)$ is an edge in $G$ and level of $u$ in $G$ is i. If we visit $u$ then after traversing every node of level $i$ we need to traverse node $v$. Because vertex $v$ is already in Queue so for next level traversal we need to visit $v$. That means $|d(v) − d(u)| \leq 1$.
edited by
3 votes
3 votes
I think none of these bcoz for bfs it can be zero and a graph can have cross edge
Answer:

Related questions

35 votes
35 votes
9 answers
1
gatecse asked Feb 14, 2018
17,351 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 $...