Bonus Problem

$(0\mathrm{.}15pts)$

The Premiere Bank soon will be hooking up computer terminals at each of its branch

offices to the computer at its main office using special phone lines with

telecommunications devices. The phone line from a branch office need not be connected

directly to the main office. It can be connected indirectly by being connected to another

branch office that is connected $($directly or indirectly$)$ to the main office. The only

requirement is that every branch office be connected by some route to the main office. The

charge for the special phone lines is $$100$ times the number of miles involved, where the

distance $($in miles$)$ between every pair of offices is as follows:

Management wishes to determine which pairs of offices should be directly connected by

special phone lines in order to connect every branch office $($directly or indirectly$)$ to the

main office at a minimum total cost.

$($a$)$ Describe how this problem fits the network description of the minimum spanning

tree problem.

$($b$)$ Use the heuristic algorithm described in lecture to solve this problem.