719 views
2 votes
2 votes

 Let G be a complete undirected graph on 5 vertices 10 edges,  with weights being  1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have.  Then the value of x will be_____


 the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out  in understanding the procedure

1 Answer

0 votes
0 votes

Using kruskal's algorithm we can make MST considering the fact that we need maximum length. So for getting max. Length MST we have to choose max length edge.

1 - No other option, it must be in MST.

2- It must be in MST

3. As a cycle will be created so we can ignore 3.

4- It must be in MST.

5- cycle could be there. 

6- cycle could be there.

7- It must be in MST.

 

Refer. Image. 

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
3
sandip kushvah asked Dec 30, 2015
859 views
Let G be a simple undirected complete and weighted graph with vertex set V={0,1,2..99}.Weight of edge (u,v) is |u-v| where 0<=u,v<=99 and u not equal to v.Weight of the c...