MadeEasy Subject Test: Algorithms - Minimum Spanning Trees

Question

Comments

@Pranab, If z=8 and x = 11, then It might not included in my MST.

To make sure they are always present in MST, it should be 7 and 10.

---

yes x=10 and z=7 is correct. if you take x=11 it may not be present in the MST

---

but if two edges are equal then possibilities there to include in spanning tree , in that case how many same edges there that many possible minimum spanning possible but result of minimum spanning tree will be same.

Answer 1

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.

Answer 2

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.

Comments

Thanks for confirming the answer.

---

Thanks for confirmation..

---

for x = 11, one of the MST might include AF instead of GF ,i.e edge x

Similarly, for z = 8 ,one of the MST might contain BH instead of BC,i.e edge z

 

I think x must be 10 and z =7 for ensuring x,y,z belonging to MST

Answer 3

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.

Comments

answer shown here is 19 i.e 11+8

And i think is correct as question asked here says MST contains edges so minimum value of x <= 11 and z<= 8

---

You are right!

Answer 4

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.

Comments

Yes, If spanning tree is unique then 17 is correct but in the question it is not mentioned and one more point is we are asked to find maximum value, I agree with @Kapil ..

---

Here, it is asking maximum value, means value upto which spanning tree is not violated i.e, it does not contains a cycle.

10 is sure, 11 can contain AF or FG. At a time, either we use AF or FG i.e, MST can contain either edges .

This is what is the MST requirement .

---

@vijay and @kapil  thanks...i'll update it...

Answer 5

here in MST you have to get (B,H) edge of weight 8.now you can make Z 8 and take that

and highest value of X could be 11

11+8=19

so 19 should be the answer

edit:draw the mst carefully and look for maximum possible weights and variations in edges..

Answer 6

Apply kruskal algorithm

1. sort the edges of G in increasing order by length
2. keep a subgraph S of G,initially empty
3. for each edge e in sorted order
4. If the endpoints of e are disconnected in S add e to S

For given graph, result of kruskal algorithm will be 

Since it is not specified that x and z should be present always in MST, to get maximum sum value of x and z should be minimum of non visited edges from that node.

x=min (11)= 11

y=min(13,14,8)= 8

x+y=11+8=19

NB : If it is specified that x and z should be always present in MST

x=min (11)-1= 10 y=min(13,14,8)-1= 7