Algorithms
October 12, 2023Algorithms
October 12, 2023GATE 2005-IT
| Question 14 |
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
| k | |
| k + 1 | |
| n – k – 1 | |
| n – k |
Question 14 Explanation:
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 connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n – k
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n – k
Correct Answer: D
Question 14 Explanation:
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 connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n – k
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n – k