GATE CSE 2017 Set 1 | Question: 26

Question

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?

• A. I only
• B. II only
• C. both I and II
• D. neither I nor II

Comments

second one does not hold true every time.

Answer 1

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.

Comments

nice explanation ...

---

But the graph given in the question is said to be undirected...

---

It wont change anything, make it undirected. The reasoning still holds.

---

Yes,  it would not make any difference even if it was directed, anyway I edited the image.

Answer 2

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!

Comments

However your solution is true but aprroch could ve wrong because according to algorithm if there is two path between two varticea are same than it selects path with minimum no. of vertices!

 

is this from set-1??

---

yes set I

Answer 3

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)

Comments

Heaps are not used in kruskal but in prims. Disjoint sets are used in kruskal.

Answer 4

onli 1st is true