You don't need to draw all potential arcs - there are too many. You will draw arcs as the algorithm generates them: Start with Main Office and draw on paper a node for Main. In the data table, cross out the column Main, mark Main Office row, and find closest branch by comparing the distances in the first row. The closest branch is B.2 at a distance of 70. So, on the paper, draw a node for B.2 and connect it to Main. Again, cross out the column of B.2 and mark the row of Branch 2. Until all columns are crossed-out, repeat. General Step: Find the closest node (column) to any of the marked nodes (rows). Let the closest node be j to a marked node i. Every time you find the next closest node (say j, the solved node), draw node j on paper, draw the link (i to j), mark row j (Branch j), and cross-out the column for (solved) node j in the distance matrix. Nodes associated with crossed-out distance columns are not considered when finding the closest node.

10.4-3. 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 Page 416 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: Distance between Pairs of Offices Main B.1 B.2 B.3 3.4 3.5 190 70 100 115 110 $40 Main office Branch 1 Branch 2 Branch 3 Branch 4 Branch 5 86818 B 100 190 70 115 270 160 270 215 120 175 160 50 220 BO 310 215 50 140 120 220 175 80 310 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 lits the network description of the minimum spanning tree problem (b) Use the algorithm described in Sec. 10.4 to solve the