Skip to content
GATETECH
Official PYQ · 2010Q51Minimum Spanning TreesMCQ1 mark

GATE CS 2010 Q51 — Minimum Spanning Trees

Explain with AI

Consider a complete undirected graph with vertex set {0,1,2,3,4}\{0, 1, 2, 3, 4\}. Entry WijW_{ij} in the matrix WW below is the weight of the edge {i,j}\{i, j\}

W=(018141012498120731470249320)W=\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}

What is the minimum possible weight of a path PP from vertex 11 to vertex 22 in this graph such that PP contains at most 33 edges?

Choose one option
View worked solution

Answer: B

We need to find the minimum weight of a path PP from vertex 11 to vertex 22 containing at most 33 edges. The vertices are indexed as 0,1,2,3,40, 1, 2, 3, 4.

Let's evaluate the possible paths from vertex 11 to vertex 22 based on the number of edges:

  1. 1-edge path:
    • 1→21 \to 2: weight =W1,2=12= W_{1,2} = 12
  2. 2-edge paths:
    • 1→0→21 \to 0 \to 2: weight =W1,0+W0,2=1+8=9= W_{1,0} + W_{0,2} = 1 + 8 = 9
    • 1→3→21 \to 3 \to 2: weight =W1,3+W3,2=4+7=11= W_{1,3} + W_{3,2} = 4 + 7 = 11
    • 1→4→21 \to 4 \to 2: weight =W1,4+W4,2=9+3=12= W_{1,4} + W_{4,2} = 9 + 3 = 12
  3. 3-edge paths:
    • 1→0→3→21 \to 0 \to 3 \to 2: weight =W1,0+W0,3+W3,2=1+1+7=9= W_{1,0} + W_{0,3} + W_{3,2} = 1 + 1 + 7 = 9
    • 1→0→4→21 \to 0 \to 4 \to 2: weight =W1,0+W0,4+W4,2=1+4+3=8= W_{1,0} + W_{0,4} + W_{4,2} = 1 + 4 + 3 = 8
    • 1→3→4→21 \to 3 \to 4 \to 2: weight =W1,3+W3,4+W4,2=4+2+3=9= W_{1,3} + W_{3,4} + W_{4,2} = 4 + 2 + 3 = 9

The minimum weight among all paths with at most 33 edges is 88, achieved by the path 1→0→4→21 \to 0 \to 4 \to 2.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Minimum Spanning Trees questions