GO Classes 2024 | IIITH Mock Test 2 | Question: 64

Answer 1

Please watch this video after 47:16 – https://youtu.be/UbGDzdW7UjY?list=PLIPZ2_p3RNHjUCHdJp-_soSSmhgmO4i0T&t=2836

This video will clarify very important concept regarding finiding missing edge cost in MST.

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯

Temporarily we have removed all the light colored edges (except z).

It is easy to see that every vertex is connected except D. 
In the next step Kruskal’s will be choosing one of the edge to connect D. 
One of the edge among $120, 100$ or $z$ will become MST edge and all edges are non MST edges.

Now applying the method discussed in above video.

• $130$ and $140$ makes  cycle with $x$ hence $x \leq 130$ and $x \leq 140$
• $130$ and $80$ makes cycle with $y$ hence $y \leq 130$ and $y \leq 80$

Let us determine $z$ now – 

Out of three choices among $120, 110$ and $z,$ Kruskal’s will choose one of them depending on value of $z.$

Kruskal’s algorithm works step by step by traversing edges in their increasing cost value.

Algo has not selected $z$ yet, it means $z$ is greater than equal to all thick edges.

$z \geq max(90, x, y)$.

$\mathrm{x}$ and $\mathrm{y}$ can take any small values too hence  $z \geq 90$.

To maximize $x+y-z, x$ and $y$ should have maximum value and $z$ should have minimum value. Answer is $130+80-90=120.$

Comments

Algo has not selected z yet, it means z is greater than equal to all thick edges.

so how can we say x and y as 130 and 80

---

@GO Classes  @Sachin Mittal 1 sir I have doubt regarding value of x. 

Since we have already selected edge x in intermediate step for MST. But we didn’t yet select HD=110(and also HD didn’t bring any cycle). 

So if we are choosing x before edge  HD it means x must have weight less than or equal to 110

Value of y and z is correct.

So according to me:

x+y-z= 110+80-90 =100

Sir please see if I am doing wrong any where?

 

 

 

---

We need to maximize x + y - z so for that we should choose "x" as high as possible

---

I don't think this is correct. We are using Kruskal. So under no circumstance will x get added to mst before the 110 weight edge (unless it was forming a cycle but in this case it's not). So x <= 110 not 130. so x+y-z  max value = 110+80-max(x,y)=110+80-110=80