###### Algorithms

October 12, 2023###### Algorithms

October 12, 2023# Algorithms

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