P 1 - Minimum Spanning Tree
Premiere Bank will be connecting computer terminals at each one of its branch offices to the
computer at its main office using a land cable system. 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
distance (in miles) between every pair of offices is shown below.
(a) Describe how this problem fits the framework of the minimum spanning tree problem.
A minimum spanning tree is a spanning tree with minimum total weight. The conditions
given in this Problem 1 well fit in the MST's setting to find the minimum distance that
can connect the main office and the 5 branches with no loop/cycle within the tree paths.
(b) Draw an undirected graph for this problem.