retagged by
601 views
1 votes
1 votes

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. 

retagged by

1 Answer

2 votes
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.

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
3 answers
3
iarnav asked Apr 29, 2018
1,504 views
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST?Question2 ) Prim's algorithm works with negative weighted edges?