retagged by
1,920 views

1 Answer

0 votes
0 votes

To find MST of a given graph using Kruskal’s algorithm we can follow $2$ steps process:

  1. Sort all the edges in increasing order of their weights.
  2. select the smallest edges and check if it forms a cycle with the spanning tree formed so far. if the cycle is not formed then include this edge, else discard it.

Step 1) Sort the edges of the given graph in increasing order of weight. so correct order is :$(2,3,4,5,6,7,8)$

Step 2) Draw the MST by selecting sorted edges one by one.

 We know that for $n$ vertices, the number of edges should be $(n-1)$ in MST. so for a given graph having $5$ vertices should have $4$ edges in MST.

  • we can select an edge having a weight $2$
  • we can also select an edge having a weight $3$
  • we can select edge having wight $4$
  • we can’t select an edge having a weight  $5$ because it forms a cycle.
  • next, we can select an edge having a weight $6$

our MST is done here. we can not take the edge with the weight of $7,8$ because it forms a cycle.

MST is as follow:

So Total cost of the minimum spanning tree is $(2+3+4+6)=15$

Option $(B)$ is correct.

Note: Similar type of question asked in Gate 2021

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,865 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$