Algorithms
October 12, 2023Algorithms
October 12, 2023Algorithms
|
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
|
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 = 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 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
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
Subscribe
Login
0 Comments