DE 6
AC 8
AD 10
FG 11
BE 12
CF 16
6+8+10+11+12+16 = 63 , so minimum length = 63
Note the graph should be drawn again in the order of the above for maximum marks and highlighted on the original
Caption: : Here is an Adjacency Matrix for a graph. Find the minimum length of a spanning tree and draw the spanning tree
Slide 6
Answer
Select A first and circle it (note down a number 1 next to it as well)
Cross out row A
Select minimum value below that circled value (so 100).
100 is in row F, so circle F and note down a number 2 near it
Cross out row F
Select minimum value below that circled value and the previous circled value(s) (so 80)
Repeat for all rows: 100 + 80 + 80 + 180 + 230 = 670
Minimum length = 670
1. PS 17 , SU 23 , UQ 35 , QR 30 , RT 27 , TP 44 , sum = 176. Therefore cycle PSVQRTP = 176 (upper bound)
2. Cycle = AEBDCA, total = 70+35+65+85+30 = 285
3. Shortest route from A to D = 9 and shortest route from B to D is 5 ; AB 4 , BC 2 , CD 3 , DA 9 , sum =18. This cycle is ABCDA, but the actual route is ABCDCBA (as DA is actually DCBA as DA isn't really there)
4. Fill in matrix (note that if there is no direct route, the shortest possible journey for that route is chosen) , cycle = ABEDCA , total = 23 , actual route = ABEDCDA
