GATE IT 2005 | Question: 14

Question

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

• A. $k$
• B. $k+1$
• C. $n-k-1$
• D. $n-k$

Comments

if a graph has n vertices it has n-1 tree edges. This is the key to this problem,

---

@sushmita if a connected graph has n vertices then it has n-1 tree edges.

---

Is this Correct Approach To solve?

Now given is N vertices and there are K tree edges in DFS traversal of graph.

Now let’s assume we have m connected components in the graph each have Ki tree edges and Ni vertices.

C1        C2        C3 ……………………………………..  Cm    -- connected components

K1         K2         K3 ………………………………………. Km    -- tree edges in each component

N1        N2        N3 ……………………………………….            Nm   -- vertices in each component

Now we know that in each ith component of DFS we will have Ni-1 tree edges (because it’s a tree with Ni vertices).

But we have assumed tree edges in each component is Ki  

Therefore Ki=Ni-1;

Now

C1        C2        C3 ……………………………………..  Cm    -- connected components

N1-1     N2-1     N3-1 ……………………………………….         Nm-1     --  tree edges in each component

And since total tree edges in graph are K edges therefore

N1-1 + N2-1 + N3-1 ………………………………………. + Nm-1 = K

(N1+ N2+ N3 + ………………………………………. + Nm) - m = K

And we know that total vertices = N

Therefore N1+ N2+ N3 + ………………………………………. + Nm = N

N-m=K  

Therefore N-K=m

Therefore connected components are N-K.

Answer 1

In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k

Answer 2

Total there will be N-1 edges in DFS graph of “N” vertices as DFS is acyclic. Since there are “k” edges for trees so we are left with “N-k-1” independent edges . Thus component wise total components are ( N-k-1 ) + 1. This last one is for the tree. Hence total N-k components.

Answer 3

You run DFS / BFS on graph , all the nodes that are connected will form one DFT / BFT.  Non Connected vertices are left. We rerun DFS / BFS on them to get another DFT/BFT. 

DFT/BFT in itself a connected Graph => if there are x nodes then there will be x-1 edges for sure.

Given DFT has k edges => k=x-1  => x=k+1 nodes  k+1 nodes in DFT  => 1 connected component

We do not need to think about the forward backward or cross edges . Why???? Bcoz we have already got the no of nodes and that’s it.

Left vertices – n-(k+1)  => n-k-1  nodes that were not part of DFT => n-k-1 components

Total = 1+ n-k-1 = n-k connected components

Answer 4

https://youtu.be/ZPNwt6SUvr8?t=8961

Comments

Sachin Mittal Sir