in Graph Theory
306 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

in Graph Theory
306 views

3 Comments

answer will be 14
2
2
I'm getting 12
0
0
min will be 10 max 34
0
0

Subscribe to GO Classes for GATE CSE 2022

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

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true