###### GATE 2011

October 26, 2023###### NTA-UGC-NET 2021 Dec & 2022 June Paper-2

October 26, 2023# GATE 2011

Question 52 |

An undirected graph G(V, E) contains n (n > 2) nodes named v_{1}, v_{2}, ….v_{n}. Two nodes v_{i} , v_{j} are connected if and only if 0 < |i – j| ≤ 2. Each edge (v_{i}, v_{j}) is assigned a weight i + j. A sample graph with n = 4 is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

1/12(11n ^{2}-5n) | |

n ^{2} – n + 1 | |

6n – 11 | |

2n + 1 |

Question 52 Explanation:

Let take example of 5 vertices,

Cost of MST,

= 3+4+6+8 = 21

Only option (B) satisfies it.

Cost of MST,

= 3+4+6+8 = 21

Only option (B) satisfies it.

Correct Answer: B

Question 52 Explanation:

Let take example of 5 vertices,

Cost of MST,

= 3+4+6+8 = 21

Only option (B) satisfies it.

Cost of MST,

= 3+4+6+8 = 21

Only option (B) satisfies it.

Subscribe

Login

0 Comments