The GATE Grind

GATE 2022 AR — Planning – Question 62

Urban Land Use and Transportation · Process and principles of traffic engineering · 2 marks · Multiple select

In the six-node network, link values are minutes. Which edge sets form a minimum spanning tree?

Diagram for GATE 2022 AR — Planning question 62
  1. PQ, QR, QT, TS, SU
  2. PR, QR, RT, TU, SU
  3. PQ, QR, RT, TS, SU
  4. PQ, QR, RS, ST, TU

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) PQ, QR, QT, TS, SU; (C) PQ, QR, RT, TS, SU

Explanation

Select the three weight 2 edges PQ, QR, SU. To join all components without a cycle, add TS=3 and either QT=3 or RT=3. Each tree has five edges and total 2+2+2+3+3=12. Thus A, C are tied minimum trees. B totals 14 and D 17.