The GATE Grind

GATE 2018 CS – Question 57

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

Consider the following undirected graph G (the edge weights are shown in the figure, with one edge of unknown weight $x$):

Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of $x$ is ________.

Diagram for GATE 2018 CS question 57

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 4

Explanation

Name the top, upper-left, lower-left, lower-right and upper-right vertices A,B,C,D,E. The weight-1 edge AC and weight-3 edge AD are cheaper than the alternatives needed to connect their components, so both occur in every minimum spanning tree.

Vertex B can attach through AB or BC, both of weight 4, giving two choices. Vertex E can attach through AE of weight x or DE of weight 5. Setting **x=5** makes these two alternatives equally cheap, without creating a cheaper replacement for AC or AD.

The choices are independent, giving $2\times2=\boxed4$ minimum spanning trees, each of weight 13. If x differs from 5, E has only one cheapest attachment, reducing the count.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →