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

Choosing $x$ equal to the weights of the competing edges in the relevant cycles (so that ties occur everywhere possible) maximises the number of equally cheap spanning trees. Counting the ties gives 4 minimum weight spanning trees (the official key).