###### Data-Structures

October 3, 2023###### Operating-Systems

October 3, 2023# GATE 2017 [Set-1]

Question 26 |

Let

(I) Minimum Spanning Tree of

(II) Shortest path between any two vertices of

Which of the above statements is/are necessarily true?

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

(I) only | |

(II) only | |

both (I) and (II) | |

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.

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.

Correct Answer: A

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.

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.

Subscribe

Login

0 Comments