retagged by
2,938 views
1 votes
1 votes

retagged by

7 Answers

Best answer
6 votes
6 votes

First sort all edges. $IJ (1) = AG (1) < CD(2) < \dots AF(11)$. Now I have not yet put $FG$(x) and $BC$(z)  here, but I want to put these as right most as possible in above sequence, bcoz we want maximum value of x+z.

Now I am putting all vertices and only x and z to start with.

Now I am adding edges one by one (Kruskal's) till any edge forms cycle with x or z

After this point, We are about to add edge DJ but this forms cycle, so we will ignore this. But this DJ do not form any cycle with either x or z, so we cant decide anything about x or z using DJ, but we simply ignore it. Now next edge to be added is BH(8) and this forms cycle with z, so we can not take z more than 8. (Think, Why ?)

Maximum value of z = 8.

Similarly, if we keep on adding then AF(11) is first edge which forms cycle with x hence maximum value of x = 11.

Maximum value of x+z = 11+8 = 19.

selected by
12 votes
12 votes

The MST containing the edges with weights x,y,z will look like:

For the maximum value of x consider this:

The vertex F can be connected to the graph by selecting either edge A-F or edge F-G. Now the weight of A-F is 11. So if x is greater than 11 then instead of selecting the edge F-G we would have selected A-F while constructing MST. So to make sure that the edge with weight 'x' is included in MST, the maximum value of x can be 11, i.e., x<=11.

For maximum value of z:

The vertex can be connected to the graph by edges A-B or B-G or B-H apart from the edge B-C having weight z. But inorder to ensure that the edge with weight 'z' is included in MST, the edge B-C should have maximum weight= the least weight among the other mentioned edges. So B-C can have weight at max=8 or else we would not have selected the edge while constructing the MST in the first place and rather have gone for edge B-H having least weight=8 in that case. So z<=8.

For maximum value of y:

Similarly 'y' can be at max=6 because say 'y'=7 or 8 or any value>6, in that case, we would not have included the edge D-E in the MST and rather have selected edge D-I as it would be the least weighted edge then.

So x<=11, y<=6, z<=8. 

Hence max(x+y+z)= 11+6+8 = 25

Please correct me if I am wrong.

4 votes
4 votes

One possible MST for the given graph.



X can only be included if X<=11. Maximum possible value for X is 11.

Z can only be included if Z<=8. Maximum possible value of Z is 8.

X+Z = 19.

edited by
2 votes
2 votes
For "F" we have two ways AF and FG for X to be selected weight of FG should be minimum..

so AF  = 11 and FG also can be 11

same way for B we have four ways AB,BC,BG,BH

we need to select BC (Z) so its weight should be min(AB,BG,BH)= 8

SO X+Z = 11+8 =19   but check is it not containing cycle na..

easy way is to draw spanning tree using kruskal.
edited by
Answer:

Related questions

0 votes
0 votes
0 answers
2
1 votes
1 votes
0 answers
4