edited by
17,519 views
65 votes
65 votes

In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is

  1. $k$
  2. $k+1$
  3. $n-k-1$
  4. $n-k$
edited by

11 Answers

Best answer
111 votes
111 votes

Tree edges are those edges which appear in the final DFS forest. For example in case of connected graph (i.e. resulting DFS forest containing only one tree), if we run DFS over it, edges belonging to the resulting DFS tree are called tree edges.

Let us assume the graph has $x$ number of connected (or strongly connected in case of a directed graph) components. And assume 1st component has $K_1$ tree edges, 2nd component has $K_2$ tree edges and xth component has $K_x$ tree edges.

Such that  $K_1 + K_2 + K_3 + \ldots + K_x = K $ ( = total)

Or in other way we can imagine like, the final DFS forest has $x$ trees and those trees are having $K_1$ , $K_2$ , $K_3, \ldots, K_x$ edges respectively.

Now we know that a tree having $K_x$ edges contains $K_x + 1$ nodes. Similarly a tree having $K_1$ edges contains $K_1 + 1$ nodes, etc. and so on.

So, summation of nodes in each tree $= n$

$(K_1 + 1) + (K_2 + 1) + (K_3 + 1) + \ldots+ (K_x + 1) = n \\ \ \ \ \ \implies (K_1+K_2+K_3+\ldots+K_x) + x = n \\ \ \ \ \ \implies x = n - K$ 

Correct Answer: $D$

edited by
32 votes
32 votes
Answer D => n-k

Why ?

If Graph is connected , while doing DFS we will visit some spanning Tree of Graph. So no of edges will be n-1 &

No of components => n - (n-1) => 1

 

If Graph is not connected in that case when we do the DFS on those disconnected graph,

For every disconnected component with say x vertices, we will get x-1 Tree edge. When we sum up all vertices we will get total no of vertices. When we sum up all edges in spanning tree of each component, we will get => Total no of vertices - Total No of connected component ( Due to for each connected component we are getting tree of no of vertices in that connnected component - 1)

So Total connected component => D) n-k
23 votes
23 votes

This is simply Modified Version of Below Statement.

If G is a forest with n vertices and p components, then G has n-p edges(k).

In this question we are applying Depth First Traversal on each component of graph (G may be Connected or Disconnected)which will give forest of spanning trees.

 k=n-p 

So p=n-k

Option D is Ans

edited by
13 votes
13 votes
If graph is connected graph with single component, then the number of edges in DFS tree will be n-1.

So n-1 edge means 1 component.

Now remove one edge from dfs tree(having n-1 edges), then number of edges will be n-2, this will create a new component. So, n-2 edges means 2 components.

Number of components = No. of Vertices in a graph - No of edges in DFS tree.

n-(n-1 edges) = 1 component.

n-(n-2 edges) = 2 component.

n-(k edges) = n-k components

So answer is D.
edited by
Answer:

Related questions