The table below gives the distances in kilometres between seven localities, A, B, C, D, E,...

Transcribed Image Text:

The table below gives the distances in kilometres between seven localities, A, B, C, D, E, F, G. Find a minimum weight spanning tree joining these localities and give its weight. A B C D EFG A B C D E F - 9 8 12 10 2 10 - 3 15 7 12 13 10 5 7 9 10 13 3 14 12 9 (8 marks) Suppose the above distances satisfy the triangle inequality. A trav- elling salesman wants to visit each of these seven localities once, returning to his starting point, and covering the shortest distance possible. Obtain a spanning cycle for the salesman which is guaranteed not to exceed twice the optimal solution. Give the weight of the cycle. (9 marks) It has been decided to partition the above localities into three clusters such that localities within clusters are as close as possible but the clusters are as distant from each other as possible. Use your spanning tree to suggest partitioning this way into three clusters. (9 marks) The table below gives the distances in kilometres between seven localities, A, B, C, D, E, F, G. Find a minimum weight spanning tree joining these localities and give its weight. A B C D EFG A B C D E F - 9 8 12 10 2 10 - 3 15 7 12 13 10 5 7 9 10 13 3 14 12 9 (8 marks) Suppose the above distances satisfy the triangle inequality. A trav- elling salesman wants to visit each of these seven localities once, returning to his starting point, and covering the shortest distance possible. Obtain a spanning cycle for the salesman which is guaranteed not to exceed twice the optimal solution. Give the weight of the cycle. (9 marks) It has been decided to partition the above localities into three clusters such that localities within clusters are as close as possible but the clusters are as distant from each other as possible. Use your spanning tree to suggest partitioning this way into three clusters. (9 marks)

Answer rating: 100% (QA)

To solve this problem we will follow these steps 1 Find the minimum weight spanning tree MWST joinin... View the full answer