The Gateway to Computer Science Excellence
+1 vote

I have this doubt that if the maximum value of x is to be found so that it is included in MST, then will it be 3 or 4? 

Because if it is 3 then there is no doubt that it would be included in the MST but if it is 4 then also it may get included. But we cannot be certain about it's inclusion in MST, so which one should I consider? 

If the opposite was asked i.e. the minimum value of x so that it never gets included in MST then it is 5. 

in Algorithms by Boss (22.7k points) | 114 views
min value of x if x not included in MST then it should be 5 and the max value of x so it should be included is ambiguous.
In one question of a test series they took x's value equal to the edge which was largest among all in the cycle. This is not the same question. I just wanted to know about the concept.

1 Answer

+2 votes

Concept is simple.

I would advise you to refer coremen on it because it has nice theorem based upon how kruskal and prim algorithm select an edge for MST.

Now coming to your question,

Here cut property of MST can be applied which states for any cut of the graph G=(V,E) such that there is an edge e which crosses the cut (S,V-S) (means having one endpoint in S and other in V-S) and for set A of edges that respect the cut(respect the cut means the these are the set of edges which are already included in your MST and now your cut is such that set of edges in A don't cross the cut) and if e is the lightest edge crossing the cut, then e is included in MST of G.

If you make X<4, then the edge AD would be selected in MST.

If you make X=4, there would be choice that you either select AD or CD, in case you can have 2 spanning trees.

If X>4, then edge CD would be selected for MST.

So, maximum values of X so that it can be included in MST shall be 4.

by Boss (27.2k points)
But in the question it is given that maximum weight such that it is included means we have to be sure enough that it will be in mst, so maximum edge weight should be 3. Please correct me if I am wrong
Yes Rajat here based on the language of the question, the answer can change.

If the question says Edge X MUST be included then it must be 3.

And if the question says Edge X can be included then it must be 4.

I have given the  answer to the latter one.
Ok sir
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,666 questions
56,170 answers
94,047 users