Aptitude Overflow
+8 votes
1.1k views

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$

 

asked in Algorithms by (19.4k points)  
recategorized by | 1.1k views
Please someone answer it with explanation.

5 Answers

+14 votes
Best answer

Tree edges are those edges which appear in the final DFS forest. For example in case of connected graph (i.e. resulting dfs forest containg 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 Ktree edges, 2nd component has Ktree edges and xth component has Ktree edges.

Such that K+ K2 + K3 + ........ + Kx = K ( = total)

Or in other way we can imagine like, the final DFS forest has x trees and those trees are having K, K, K3 , .... Kx edges respectively.

Now we know that a tree having Kedges contains Kx + 1 nodes. Similarly a tree having K1 edges contains K+ 1 nodes, etc. and so on.

So, Summation of nodes in each tree = n

$(K_1 + 1) + (K_2 + 1) + (K_3 + 1) + ................ + (K_x + 1) = n \\ \ \ \ \ => (K_1+K_2+K_3+......+K_x) + x = n \\ \ \ \ \ => x = n - K$ 

answered by (50.5k points)  
selected by
@arjun sir,

Where to study connected components from in CLRS book ?
+12 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
answered by (41.9k points)  
can u plz explain it pictorially ...
Actually I think the explanation is very simple

In a graph G with n vertices, k edges are marked as tree edges so here here in the tree edges in the k edges  there are total (k+1) no of vertices as we know that no of vertices= no of edges +1 and also in this graph there are rest n-(k+1) no of vertices as total vertices in the graph is n so for this rest n-k-1 no of vertices there are total n-k-1 no of connected components are possible so total no of connected compnonents are (n-k-1)+1 here +1 is addes because this is for tree edge as in the DFS all tree edges are connected so no of connected components are 1 so ans is n-k.
why +1 is added can you please explain elaborately with an exmple
Can u please explain what are tree edges and how they are linked in this question? I read from various sources but could not understand... MAy be a picture will be more helpful.. Thanks
+3 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

answered by (17k points)  
edited by
awesome
+1 vote
and by taking a random example take A B C D(fully connected) E, F(both disconnected) how many vertices? 6. Edges in any minumum spanning tree of ABCD=3? yes. and we have 3 components. so akash's answer is right!
answered by (2.8k points)  
0 votes
Answer: D
answered by (34.5k points)  

Related questions

2,455 questions
849 answers
346 comments
15,474 users