3. The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt roads that makes each grove accessible from every other grove. The distance (in miles) between every pair of groves is as follows:
| Distance between Pairs of Groves | ||||||||
| Grove | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | - | 1.3 | 2.1 | 0.9 | 0.7 | 1.8 | 2.0 | 1.5 |
| 2 | 1.3 | - | 0.9 | 1.8 | 1.2 | 2.6 | 2.3 | 1.1 |
| 3 | 2.1 | 0.9 | - | 2.6 | 1.7 | 2.5 | 1.9 | 1.0 |
| 4 | 0.9 | 1.8 | 2.6 | - | 0.7 | 1.6 | 1.5 | 0.9 |
| 5 | 0.7 | 1.2 | 1.7 | 0.7 | - | 0.9 | 1.1 | 0.8 |
| 6 | 1.8 | 2.6 | 2.5 | 1.6 | 0.9 | - | 0.6 | 1.0 |
| 7 | 2.0 | 2.3 | 1.9 | 1.5 | 1.1 | 0.6 | - | 0.5 |
| 8 | 1.5 | 1.1 | 1.0 | 0.9 | 0.8 | 1.0 | 0.5 | - |
Management now wants to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.
a. Describe how this problem fits the network description of a minimum spanning tree problem.
This is because, we can find the possible distance of minimum spanning tree which connect the groves by using Kruskal's Algorithm.
b. Use the suitable algorithm to solve the problem.
n=8
n-1=7
Minimum spanning tree = 0.5+0.6+0.9+0.7+2.6+0.9+1.3
= 7.5
