UGC NET CS 2017 Jan paper3
October 14, 2023NTAUGCNET 2021 Dec & 2022 June Paper2
October 14, 2023Algorithms
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.
OptionA: 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.
OptionB: 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.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
OptionA: 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.
OptionB: 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.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: 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.
OptionA: 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.
OptionB: 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.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
OptionA: 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.
OptionB: 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.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
Subscribe
Login
0 Comments