###### UGC NET CS 2017 Jan- paper-3

October 14, 2023###### NTA-UGC-NET 2021 Dec & 2022 June Paper-2

October 14, 2023# Algorithms

Question 26 |

Consider a simple undirected weighted graph G , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

The edge with the second smallest weight is always part of any minimum spanning tree of G . | |

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . | |

| |

G can have multiple minimum spanning trees. |

Question 26 Explanation:

Let assume the graph and minimum spanning tree of the corresponding graph.

Option-A: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.

The second smallest weight is always in MST because it will not form a cycle.

Option-B: TRUE: Graph G is having more than 4 vertices. Suppose 3rd smallest element is forming a cycle then it takes 4th smallest element. So, the given statement is TRUE.

Option-C: TRUE: As per the example graph, it is always correct.

Option-D: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.

Option-A: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.

The second smallest weight is always in MST because it will not form a cycle.

Option-B: TRUE: Graph G is having more than 4 vertices. Suppose 3rd smallest element is forming a cycle then it takes 4th smallest element. So, the given statement is TRUE.

Option-C: TRUE: As per the example graph, it is always correct.

Option-D: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.

Correct Answer: C

Question 26 Explanation:

Let assume the graph and minimum spanning tree of the corresponding graph.

Option-A: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.

The second smallest weight is always in MST because it will not form a cycle.

Option-B: TRUE: Graph G is having more than 4 vertices. Suppose 3rd smallest element is forming a cycle then it takes 4th smallest element. So, the given statement is TRUE.

Option-C: TRUE: As per the example graph, it is always correct.

Option-D: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.

Option-A: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.

The second smallest weight is always in MST because it will not form a cycle.

Option-B: TRUE: Graph G is having more than 4 vertices. Suppose 3rd smallest element is forming a cycle then it takes 4th smallest element. So, the given statement is TRUE.

Option-C: TRUE: As per the example graph, it is always correct.

Option-D: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.

Subscribe

Login

0 Comments