116 views
1 1 vote

Let $T$ be a depth-first search tree of a undirected graph. Let $(x,y)$ be an edge of $G$ that is not an edge of $T$, then one of $x$ or $y$ is an ancestor of the other.

  1. True
     
  2. False

1 Answer

0 0 votes

Consider a non-tree edge $(x,y)$ in an undirected graph.

Suppose $x$ is discovered first.

When DFS explores $x$, there are two possibilities.

If $y$ is still unvisited when $(x,y)$ is examined, then DFS would visit $y$ through this edge.

In that case, $(x,y)$ would become a tree edge.

But the question says that $(x,y)$ is not a tree edge.

Therefore, when the edge is examined, $y$ must already have been discovered.

In an undirected DFS, this means that one endpoint lies on the active DFS path of the other. 

Hence one is an ancestor of the other.

So every non-tree edge in an undirected DFS is a back edge connecting a descendant to an ancestor.


$\therefore$ Answer: A


Note : This is also why an undirected DFS has only tree edges and back edges, not cross or forward edges.

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
108
108 views
GO Classes asked Aug 18
108 views
Run DFS on a directed graph $G$ computing visit times $pre(v)$ and $post(v)$ for each vertex $v$.An edge $(u,v)$ is a back edge if and only if $pre(v)<pre(u)<post(u)<post...
1 1 vote
1 1 answer
96
96 views
GO Classes asked Aug 18
96 views
In DFS, if $(u,v)$ is an edge which connects two node such that they do not have any ancestor and a descendant relationship between them, than the edge is calledTree edge...
1 1 vote
1 1 answer
135
135 views
GO Classes asked Aug 18
135 views
Suppose that during an execution of depth-first search in a digraph $G$, $\texttt{dfs(v)}$ is called as a recursive subcall after $\texttt{dfs(w)}$ is called, but before ...