85 votes 85 votes Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________ Algorithms gatecse-2016-set1 algorithms spanning-tree normal numerical-answers + – Sandeep Singh asked Feb 12, 2016 • edited Nov 16, 2017 by kenzou Sandeep Singh 35.6k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments codeitram commented Jan 22, 2021 reply Follow Share It is not at all rocket science: Here is the solution You pick up four min edges to get MST so you pick edge with weight 1 then 2 as no choice but when picking up 3 you can ask can I avoid this one so that I can pick 4 or above which has greater weight and answer is yes you simply make weight 3 edge as so that cycle is formed, and now will have to pick edge with weight 4 as you have no choice and no additional cycle can be formed as graph is complete 4 0 votes 0 votes Adi27 commented Oct 9, 2021 reply Follow Share @arjun sir graph is complete that is all distinct vertices are connected with unique edge so only one graph structure is possible ? Square shape with diagonal vertices connected No of edges = 4*(4-1)/2 = 6 edges as given in graph 0 votes 0 votes Ray Tomlinson commented Jan 22 i edited by Ray Tomlinson Jan 22 reply Follow Share I think there are only 2 mst possible with min weight 6,7 so answer will be 7this question gets to many view just due to wrong interpretaion of question i.e. what actually asking in question is confusing means should we apply mst algo or not like this confusion . 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes GRAPH CAN BE LIKE THIS ALSO USING CUT Property of MST MST with maximum weight 7 Sandeep Suri answered Jan 31, 2018 Sandeep Suri comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes This question deals with orientation of complete graph Now we have 2 options 1) we place edges having wt 1, 2 at digonals 2) or on sides Because any way those edges are part of spanning tree Iin the first case it is not possible to construct a mst neglecting edge with wt 3 But in second case we can make mst with neglecting 3 by placing such that it forms cyle tocshark answered Jan 14, 2017 tocshark comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes My approach you just make cycle with 3 min weight edge so in this you will get two edges weight 1,2. now 3 is included in cycle so we cant consider it so now remaining 4,5,6 so min is 4 becouse complete graph we consider so ans is 1+2+4 AakanshaF answered Nov 27, 2018 AakanshaF comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Draw a complete graph of 4 vertices. Sort given edges y weight in increasing order. Just like Kruskal's algorithm sort the edges by weight. MST of graph with 4 vertices and 6 edges will have 3 edges. Now in any case we will have to include edges with weights 1 and 2 as they are minimum and Kruskal's algorithm includes minimum weight edge if it does not form a cycle. We can not have a cycle with 2 edges. In Kruskals algorithm, an edge will be rejected if it forms a cycle with the edges already selected. To increase the weight of our MST we will try to reject the edge with weight 3. This can be done by forming a cycle. The graph in pic1 shows this case. This implies, the total weight of this graph will be 1+2+4=7. AakanshaF answered Nov 27, 2018 AakanshaF comment Share Follow See all 0 reply Please log in or register to add a comment.