edited by
12,317 views
45 votes
45 votes

Let $G=\left ( V,E \right )$ be $any$ connected, undirected, edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements:

  1. Minimum Spanning Tree of $G$ is always unique.
  2. Shortest path between any two vertices of $G$ is always unique.

Which of the above statements is/are necessarily true?

  1. I only
  2. II only
  3. both I and II
  4. neither I nor II
edited by

5 Answers

Best answer
76 votes
76 votes

Answer is A.

  • MST is not unique only when edges are not distinct. Here the edges are distinct. Be careful for the keyword DISTINCT.
     
  • Shortest Path can be different even if the edges are distinct. Example is shown below. Shortest path from A to C is not unique here.

pic

edited by
12 votes
12 votes
Only 1 is true because if you take an example of 3 vertices with weights as 1,2 &3 ..

A---1------B

B------2--------C

C--------3---------A

 

 

1.   Minimum spanning tree would weigh 1+2=3 (only one mst possible with AB & BC)

2.   whereas  it wouldn't have a unique shortest path between two of them.

1+2=3 possible (AB +BC) & only 3 possible (CA)  ~ two possibilities

Correct me if I am wrong!
8 votes
8 votes
Option 1 is CORRECT as Weights are Distinct hence only 1 minimum spanning tree is possible

(Think it this way..you are applying KRUSKAL algorithm...now each time min heap will return you Unique minimum weight edge so only 1 tree possible)

Option 2 INCORRECT as below

   A      (1)       B

  (2)               (4)

  C       (3)       D

here path 1(A--B--D) has weight=5

path 2(A--C--D) has weight 5

So answer is OPTION (A)
Answer:

Related questions

25 votes
25 votes
7 answers
3
khushtak asked Feb 14, 2017
6,938 views
Consider the following table:$$\begin{array}{|l|}\hline \textbf {Algorithms} & \textbf{Design Paradigms } & \\\hline \text{P. Kruskal} & \text{i. Divide and Conquer} \...