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. Example 6.2-1 Midwest TV Cable Company is providing cable service to five new housing developments. Figure 6.5 depicts possible TV connections to the five areas, with cable miles affixed on each arc. The goal is to determine the most economical cable network. 6.3 Shortest-Route Problem 221 3 (miles) 10 FIGURE 6.5 Cable connections for Midwest TV Company The algorithm starts at node 1 (actually, any other node can be a starting point), which gives C Figure 6.6. The thin arcs provide all the candidate links between C and C. The thick arcs are the permanent links of the connected set C, and the dashed are is 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, and 5 in the unconnected set Cj. Hence, link (1,2) is made permanent and j" 2, which yields C, = {1,2}. C (3, 4, 5, 6}. The solution is given by the minimal spanning tree shown in iteration 6 of Figure 6.6. The resulting minimum cable miles needed to provide the desired cable service are 1 + 3 + 4+3+$16 miles. (1} and C (2, 3. 4, 5, 6). The iterations of the algorithm are summarized ih !! Remarks, In theory, a minimal spanning tree can be formulated and solved as a linear program. However, LP is not a practical option because numerous constraints must be added to exclude all cycles, resulting in a huge LP.even for small networks