Question

A cable company must provide service for 6 houses in a particular neighborhood. They would like to wire the neighborhood in a way to minimize the wiring costs (or distance). What is the minimal length of the network required to span the entire neighborhood? House Distances (yards) 1 to 2 250 1 to 3 400 1 to 4 300 2 to 3 400 2 to 4 400 2 to 5 400 3 to 5 350 3 to 6 450 4 to 5 300 4 to 6 350

Answer 1

1650 yards

Explanation:

Here, we have to find the minimal spanning tree required to span the neighborhood.

We start from house 1. The minimum distance from house 1 to house 2 is 250 yards. Now from 2, we can go to house 3,4 or 5 all having the equal distances of 400 yard from house 2. So we go to from house 2 to house 3. Now from 3, we go to house 5 which is at a minimum distance of 350 yards. Now from house 5 we go to house 4 with 300 yards and then from house 4 we go to house 6 which is at 350 yards from 4.

Thus the network is complete and the total distance covered is

= 250 + 400 + 350 + 300 + 350

= 1650 yards

This is the minimum distance by which the neighborhood can be wired.

And the tree is

`$1\rightarrow2\rightarrow3\rightarrow5\rightarrow4\rightarrow6$`