Algorithm Questions

Kruskal's

Answer

• 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

Prim's (Graph)

• 
• Legenda: Start with the vertex G

Answer

• GH 5 , EG 7 , HJ 8 , BE 10 , BD 11 , HI 14 , DC 15 , AC 6 , FJ 19 , HK 22
• 5+7+8+10+11+14+15+6+19+22 = 117 , so minimum length = 117

Prim's (Adjacency Matrix)

• 
• Legenda: Here is an Adjacency Matrix for a graph. Find the minimum length of a spanning tree and draw the spanning tree

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
• 

Question

Answer

Travelling Salesperson Problem (UB)

Answers (left to right)

• 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

Travelling Salesperson (LB)

Answer