Consider the following Adjacency matrix corresponding to some weighted Graph…

2017

Consider the following Adjacency matrix corresponding to some weighted Graph ‘G’.

image.png

What is the weight of the minimum spanning tree for the graph ‘G’?

Answer: B. 9 — The correct option is B. Using Kruskal's algorithm, sort edges by weight: (3,4) weight 1, (1,5) weight 2, (2,5) weight 2, (2,3) weight 4. Selecting these…

  1. A.

    8

  2. B.

    9

  3. C.

    10

  4. D.

    11

Attempted by 190 students.

Show answer & explanation

Correct answer: B

The correct option is B.

Using Kruskal's algorithm, sort edges by weight: (3,4) weight 1, (1,5) weight 2, (2,5) weight 2, (2,3) weight 4. Selecting these edges covers all 5 vertices without creating a cycle. Total Minimum Spanning Tree (MST) weight = 1 + 2 + 2 + 4 = 9.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…