Let G = (V, E) be any connected undirected edge-weighted graph. The weights of…
2025
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
I) Minimum Spanning Tree of G is always unique.
II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
- A.
I only
- B.
II only
- C.
Both I and II
- D.
Neither I nor II
Attempted by 114 students.
Show answer & explanation
Correct answer: A
Concept:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Example:
Graph G(V, E)
G(V, V – 1) → minimum spanning tree
If edge weights are distinct then there exist unique MST.
Hence Statement I is correct.When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique.
Shortest path can be different even if the edge weights are unique.Example:
Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.
Hence statement II is incorrect.