The GATE Grind

GATE 2015 CS (CS1) – Question 63

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

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.

[Graph: vertices A, B, C, D, E, F. MST edge weights: B-E = 15, B-C = 2, A-C = 9, E-F = 4, D-F = 6. The three remaining edges are A-B, C-D and D-E, with unknown weights.]

Diagram for GATE 2015 CS (CS1) question 63

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 69

Explanation

The MST has weight $15+2+9+4+6=36$, using edges $B$–$E$ (15), $B$–$C$ (2), $A$–$C$ (9), $E$–$F$ (4) and $D$–$F$ (6). Every non-tree edge must weigh **more** than the heaviest edge on the tree path it closes (otherwise it would replace that edge in an MST). All 8 weights must be distinct integers.

These minimums (10, 16, 7) are distinct from each other and from the tree weights, so they can all be used at once: $10+16+7=33$.

Smallest possible total $=36+33=\mathbf{69}$.

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

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