6.2 Minimal Spanning Tree Algorithm 241 Midwest TV Cable Company is in the process of providing cable service to five new housing development areas.Figure 6.6 depicts possible TV linkages among the five areas. The cable miles are shown on cach arc. Determine the most conomical cable network. 2 5 3 The algorithm starts at node 1 (any other node will do as well), which gives 9. G = (1), = (2,3,4, 5,6} 7 The iterations of the algorithm are summarized in Figure 6.7. The thin arcs provide all the candi- date links between C and C. The thick branches represent the permanent links between the nodes of the connected set C,and the dashed branch represents the new (permanent)link added at each iteration. For example, in iteration 1, branch (1,2) is the shortest link (= 1 mile) among all the candidate branches from node 1 to nodes 2, 3, 4, 5, and 6 of the unconnected set Cj. Hence, link (1,2) is made permanent and j' = 2, which yields Iteration 1 Iteration 2 CA 3 4 Iteration 3 Iteration 4 G = {1,2), C; = (3,4,5,6) 2 5 3 5 The solution is given by the minimal spanning tree shown in iteration 6 of Figure 6.7. The resulting minimum cable miles needed to provide the desired cable service are 1+ 3 + 4 + 3 + 5 = 16 miles. Alternate links 10 Iteration 5 Iteration 6 (Minima! spanning tree) TORA Moment E 6.7 on iterations for Midwest TV Company LEM SET 6.2A You can use TORA to generate the iterations of the minimal spanning tre. From Main menu, select Network models = Minimal spanning tree. Next, from SOLVE/ MODIFY menu, select Solve problem = G to output screen. In the output screen, select a Starting node then use Next itertion or All iterations to generate the succes- sive iterations. You can restart the iterations by selecting a new Starting Nod. File toraEx6.2-1.txt gives TORA's data for Example 6.2-1. Solve Example 6.2-1 starting at node 5 (instead of node 1), and show that the algorithm produces the same solution. Determine the minimal spanning tree of the network of Example 6.2-1 under each of the following separate conditions: (a) Nodes 5 and 6 are linked by a 2-mile cable. b) Nodes 2 and 5 cannot be linked. c) Nodes 2 and 6 are linked by a 4-mile cable. 242 Chapter 6 Network Models SE 2000 1300 800 NY 200 DO 1100 1000 CH DE 2000 LA 2600 780 900 1300 1400 FIGURE 6.8 Network for Problem 3, Set 6.2a (d) The cable between nodes 1 and 2 is 8 miles long. (e) Nodes 3 and 5 are linked by a 2-mile cable. (f) Node 2 cannot be linked directly to nodes 3 and 5. 3. In intermodal transportation, loaded truck trailers are shipped between railroad terminals on special flatbed carts. Figure 6.8 shows the location of the main railroad terminals in the United States and the existing railroad tracks. The objective is to decide which tracks should be revitalized" to handle the intermodal traffic. In particular, the Los Angeles (LA) terminal must be linked directly to Chicago (CH) to accommodate expected heavy traffic. Other than that, all the remaining terminals can be linked, directly or indirectly, such that the total length (in miles) of the selected tracks is minimized. Determine the seg- ments of the railroad tracks that must be included in the revitalization program. 4. Figure 6.9 gives the mileage of the feasible links connecting nine offshore natural gas wellheads with an inshore delivery point. Because wellhead 1 is the closest to shore, it is equipped with sufficient pumping and storage capacity to pump the output of the remain- ing eight wells to the delivery point. Determine the minimum pipeline network that links the wellheads to the delivery point.