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
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