Algorithms
October 12, 2023Algorithms
October 12, 2023Algorithms
Question 45

In a depthfirst 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 45 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 = np
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 = np
p = n – k
Correct Answer: D
Question 45 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 = np
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 = np
p = n – k
Subscribe
Login
0 Comments