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

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
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 = n-p
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 = n-p
p = n – k
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!