October 3, 2023
October 3, 2023
October 3, 2023
###### Operating-Systems
October 3, 2023
 Question 26
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)
Question 26 Explanation:
If the graph has all positive and distinct (unique values no duplicates) then Statement-I definitely correct because if we are using either prim’s or kruskal’s algorithm it gives the unique spanning tree.
Let us take an example

Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:

Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
Statement-II: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
Question 26 Explanation:
If the graph has all positive and distinct (unique values no duplicates) then Statement-I definitely correct because if we are using either prim’s or kruskal’s algorithm it gives the unique spanning tree.
Let us take an example

Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:

Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
Statement-II: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.