Algorithms
February 13, 2024Question 14329 – Algorithms
February 13, 2024Question 14316 – Algorithms
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S2:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
Correct Answer: A
Question 40 Explanation:
Statement-1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement.
Example:
Statement-2: TRUE: Using the kruskal’s (or) prim’s algorithm we get a unique MST when there is a unique edge weight.
Example:
Based on the above graph, we get the MST is
S1is false and S2is true.
S1is true and S2is false.
Both S1 and S2are false.
Both S1 and S2are true.