Register

Made easy workbook

• edited by
784 views
0 0 votes

Q. 55 Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x, y$ and $z$

What is the maximum value of $x+y+z$ ?

1 Answer

0 0 votes
Edge weight '1' was repeated. Therefore weights are not unique.

MST contains x,y,z - that doesn't mean, every MST contain x,y,z. Therefore may be some MST doesn't contain x,y and z.

If an Edge is coming in MST then its Less than or Equal to  the All edge weights in the Cycle .

To Solve this one

 $Y\le6$ , $X\le11$, $Z\le8$  So maximum value will be $6+11+8=25$

So, here ans must be $25$.
• edited by
Voting & Accepting an answer helps improve the community
← Previous · Made easy test serie...Next → · MCM question
← Previous in category · Made easy test serie...Next in category → · MCM question
Position:
Show:

Related questions

0 0 votes
1 1 answer
628
628 views
shweta sah asked Jun 21, 2018
628 views
Made easy workbook
Q. 9 State whether the following statements are false.If $e$ is a minimum edge weight in a connected weighted graph, it must be among the edges of at least one minimum sp...
1 1 vote
1 answers 1 answer
988
988 views
aashish1406 asked Aug 8, 2023
988 views
Made Easy Test Series 2024
pls give all possible sequences possible for prims algo Consider the undirected graph below:Using Prim's algorithm to construct a minimum spanning tree starting with node...
0 0 votes
2 answers 2 answers
3.5k
3.5k views
noob_coder asked Mar 10, 2019
3,452 views
Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each verte...
0 0 votes
0 0 answers
435
435 views
Huzaifa0111 asked Aug 27, 2023
435 views
Made Easy Workbook
Q. 8 For insertion sort on 3 elements consider the following decision treeEach internal node is labelled by indices of array elements from their original positions. Each ...