# Question: The Premiere Bank soon will be hooking up computer terminals

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 algorithm described in Sec. 10.4 to solve the problem.

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 algorithm described in Sec. 10.4 to solve the problem.

## Answer to relevant Questions

For the network shown below, use the augmenting path algorithm described in Sec. 10.5 to find the flow pattern giving the maximum flow from the source to the sink, given that the arc capacity from node i to node j is the ...Consider the maximum flow problem shown below, where the source is node A, the sink is node F, and the arc capacities are the numbers shown next to these directed arcs. (a) Use the augmenting path algorithm described in Sec. ...The Audiofile Company produces boomboxes. However, management has decided to subcontract out the production of the speakers needed for the boomboxes. Three vendors are available to supply the speakers. Their price for each ...Consider the minimum cost flow problem shown below, where the bi values are given by the nodes, the cij values are given by the arcs, and the finite uij values are given in parentheses by the arcs. Obtain an initial BF ...Use the algorithm described in Sec. 10.3 to find the shortest path through each of the following networks, where the numbers represent actual distances between the corresponding nodes. (a) (b)Post your question