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.

+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.

0

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,834 questions

57,838 answers

199,509 comments

108,337 users