The Gateway to Computer Science Excellence
+45 votes
10.7k views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3,  4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
in Algorithms by Loyal (7.2k points)
edited by | 10.7k views
+5
The question is  asked such a way that you have make the weight maximum in a MST.No matter how you draw the graph you can't make the weight more that 7,It may be 6 or 7 but they asked about maximum possible weight that the MST have.So 7 is the maximum, You can' make it more than that because that will not be MST.
+7
abc Caption

0
You took a given graph- but the question does not restrict to just one possible graph. For that graph you are correct.
0
you have tried for only one possibility. there will be many ways to draw it but no matter how you draw you will get the maximum possible weight of the minimum spanning tree is 7.
+4
My approach

you just make cycle with 3 min weight edge

so in this you will get two edges weight 1,2.

now 3 is included in cycle so we cant consider it

so now remaining 4,5,6

so min is 4 becouse complete graph we consider

so ans is 1+2+4
0
Here the question needs us to construct a graph with 4 vertices and 6 edges of given weights, such that the MST weight of the constructed graph is maximum. In order to maximize MST weight, we should try to sacrifice lower weight edges to form cycles.

14 Answers

+75 votes
Best answer
Many people here have not understood the question itself. Consider a complete graph of $4$ vertices. We have a total of $6$ edges of given weights but we do not have the exact graph. Many different graphs are possible each having a different structure. Consider these $2$ graphs, both of them are different. We do not know the exact structure of the graph, so what the question wants is to find the MST of all such structures and out of these tell the weight of the MST having maximum weight. The point about the MST of a graph with unique edge weights is valid for a given structure of the graph. With the same set of edge weights more than $1$ graph is possible and all of them can have different MSTs.

My solution: Draw a complete graph of $4$ vertices. Sort given edges $y$ weight in increasing order. Just like Kruskal's algorithm sort the edges by weight. MST of graph with $4$ vertices and $6$ edges will have $3$ edges. Now in any case we will have to include edges with weights $1$ and 2 as they are minimum and Kruskal's algorithm includes minimum weight edge if it does not form a cycle. We can not have a cycle with $2$ edges. In Kruskals algorithm, an edge will be rejected if it forms a cycle with the edges already selected. To increase the weight of our MST we will try to reject the edge with weight $3.$ This can be done by forming a cycle. The graph in pic1 shows this case. This implies, the total weight of this graph will be $1+2+4 = 7.$
by Active (3.6k points)
selected by
+1
nice answer with proper explanation.
+1
we want maximum weight of mst then after taking 1 , 2 why are we not  taking 6 ??

plz help me
+3
@prateek, Question is asking about maximum weight of minimum MST.

that's why we have to take care of weight should be as minimum as possible and along with maximum value.
0
okk i got now thanks
+1
@Akash.dinker12 how can u specifically say that maximum weight should be 7?????
0
it is possible because first of all we want mst along with max.weight ,so we have to take edge weight 1 , 2 and after that we have no other choice so we have to take 4 edge weight that mst will be max weight which follow the property, we can't take any other edge that will not be mst then
0
if you really have understood the logic try to explain the logic writing 2 or 3 more lines so that a layman can also understand it , remembering what difficulties you faced while you were not getting the answer.. cause your answer to this question still did not clear the matter at all...im still in the same position where i was , after reading the previous answers...
+1
Dude, images are broken. :(
0
why we are not using  1+2+5 = 8?

as it  also forms a spanning tree

and wht is the meaning of max possible weight in min. spanning tree .(MST)min spanning tree, is itself contains irreducible cost. HOW COULD BE IT MAXIMUM?
+52 votes

Graph $G$ can be like this:

by (165 points)
edited by
+7
If the minimum of 3 value of the graph makes a cycle , just take next value to make MST
+2
Yes, that's correct. We have to find the maximum weight, but it still has to be a Minimum spanning tree. Therefore you can't take 6 weight in the MST. Just take the next lightest weight.
0
why 6 cant be the ans??? adding 1 2 and 3 by different MST
+1
@Soumya Sharma 1

bcoz it is asking for maximum weight of MST. 1,2,3 forms a MST but it's weight is not maximum.
0
why not 5,6? why 3 is avioded and 4 is only considered?
0
@Sunny Mukharjee Because that won't result in a MST.
0
yeah got it bro :-) thanks :-)
+17

Again cut and cycle property asked.

Since for a graph of 4 vertices, a spanning tree would have 3 edges,

there is no doubt that edge with weights 1 and 2 would definitely be included in MST because with 2 edges you cannot form a cycle.

Now, we are left to choose one edge with weights remaining as 3,4,5 and 6.

We want to make the weight of MST maximum.

Assign 3 such that it forms a cycle and hence it is rejected.

And now for the imagine graph as a cut and edges 4,5,6 passing the cut.

The lightest edge passing the cut is now 4 and hence included in MST of this graph.

Hence, maximum possible weight is 1+2+4=7.

0

@ayush Sir can you pls help me somehow with this question...

https://gateoverflow.in/3813/gate2005-it-52

actually i am not understanding the "cutset" term and the relation of the question with that ....

if possible pls help 

+1
It's simple. Imagine you have a graph with a bridge.Now no matter what the weight of this bridge is, this bridge will be included in MST of G.

Similarly, the question says you have graph and it's MST has maximum weight edge.

I think you know definition of cut set of G.

Now the cut property says you can decompose the graph into two set of vertices such that the edges crossing the cut would have one endpoint in set 1 of vertices and another end in other set of vertices.

Now your graph can be imagined as joint made between two subcomponents and this joint is represented by the edges crossing the cut.

so lightest edge of this cut is included in mst of G.

For more details refer theorem 23.1 of coremen.
0
Thank You so much for your help Sir... finally got it :-)
0
good explanation
0

@

cut property ==> Lightest weight edge in cut set is always included in MST

In a graph cut edge with MIN weight is always included in MST

In a graph cut edge with MAX weight always excluded in MST

are this statement right ?? please correct me if wrong..this topic is very confusing for me :(

+1

@jatin -khachane 1-Your third statement is wrong.Consider a pendant edge and to this edge I assign a very heavy weight.You have to take this into MST without which your MST would be disconnected.

0
What we do if edges weight are

1,2,3,4,5,6,7,8,9 and 10.

than find maximum possible weight that a minimum weight spanning tree of G have..???
0

@Vikas123

then we have to include minimum 4 edges to make a spanning tree and we put edges 1 ,2 and 3 in a cycle. so 3 will be rejected.

=> 1 + 2 + 4 + 5 = 12

+28 votes
ans is 7.

it is said maximum weight pssbl.

draw a triangle. 3 sides weight 1 2 3. and 4th point is in center. join it with tringle vertices.. got more 3 sides. new side weight 4 5 6. now draw mst. take 1 take 2. cant take 3, so take 4. 1+2+4=7
by Active (3.8k points)
edited by
+1
yes!!
0
are u sure coz i think its 6 (1+2+3 )

how can a graph with 7 as its weight be a minimum spanning tree when there is a spanning tree with weight 6 ??
–1
ya true if we use a kruskal algorithm and edges labelled with 1,2,3 doesnot form a loop then answer will be 6 and if by the above method solved the answer can be 7 8 9 10 and so on ......the answer has ambiguity here
+2

@Vaibhav, answer can't be more than 7 here..

–1
use prim algo it will be 8 also
0
No, use any algorithm answer comes to be 7 ONLY.
+1
U should hav drawn the image of ur answer ...
0
explain why...dont only state
0

@puja.See this...

+16 votes

Corrections or suggestions are welcomed.

by Junior (697 points)
+1
Nice ans.

( Actually While I was writing the ans ; I found that U already written the same what i supposed to write.Thanks anyway)
0
how ??? by applying SOME STRATEGY? chose 2,3?????
0

as in 2,3 (we need to select smaller one so 2 has been selected)

NOTE:-just take all possible maximum and out of all possible maximum pick minimum

0
@tanaya.... perfect one..thanks... finally it is clear
0
The best answer for this question
+11 votes
The question is asked such a way that you have make the weight maximum in a MST.No matter how you draw the graph you can't make the weight more that 7,It may be 6 or 7 but they asked about maximum possible weight that the MST have.So 7 is the maximum, You can' make it more than that because that will not be MST.
by (133 points)
+2
How can we prove that weight will not more than 7
+10 votes

This question ask as how many possible way of drawing the above as to find MST in which maximum possible weight, so in which we can draw only in two ways. in first way MST is 1+2+3=6 and other 1+2+4=7 no other ways can draw. so max possible weight that MST is 7.

by (187 points)
+5 votes
As other have explained with diagrams, the correct answer is 7. The explanation is as follows:

Keep in mind the Kruskal's algorithm for generating MST of a graph. It will pick edges in increasing order, and include them in MST if it does not form a cycle. So it will first pick edge of weight 1, then edge of weight 2 (2 edges cannot form a cycle). Now it will pick edge of weight 3 if it does not form a cycle, but since we want to maximize the weight, we will label edges of a triangle(cycle) with edge weights 1,2,3 respectively so that we cannot pick edge with weight 3 in our MST because it will then form a cycle. Therefore we have a configuration where the MST has 3 edges with weight - 1,2,4 and hence total weight = 7
by (87 points)
+3 votes

The minimum spanning tree for a distinct edge weighted graph is unique .

And as the minimum spanning tree is unique the only possible weight is 6 ( selecting the lowest possible weights 1,2,3 ) 

by Junior (693 points)
+2

In this situation ans can not be (1+2+3) = 6

Answer:

Related questions

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
50,651 questions
56,214 answers
194,173 comments
95,428 users