6.2 Minimal Spanning Tree Algorithm 241 Midwest TV Cable Company is in the process of providing...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
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 iteråtion 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. 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 iteråtion 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.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these mathematics questions
-
Determine the minimal spanning tree for the network in Problem 9.
-
Show that the algorithm from Exercise 24 has worst-case time complexity O(log n) in terms of the number of comparisons.
-
Please answer the questions below under problem set 6.2A. Under number page 2 and continues to 3 below. If its unclear, you can also check out the book, operations Research: An introduction , 8th...
-
Matrix squaring. Write a program like Markov that computes page ranks by repeatedly squaring the matrix, thus computing the sequence p, p 2 , p 4 , p 8 , p 16 , and so forth. Verify that all of the...
-
Let A be an n ( n matrix and ( a scalar. Show that the set W consisting of all vectors x in Rn such that Ax = (x is a subspace of Rn.
-
What are the trade winds?
-
What is the difference between a predator and a situational (accidental) fraudster?
-
Lashkova Company had accounts receivable of $100,000 on January 1, 2014. The only transactions that affected accounts receivable during 2014 were net credit sales of $1,000,000, cash collections of...
-
1. A car has tires that have an outer diameter of 31 inches. If the wheels are turning with an angular velocity of 12 rad/s, how far in miles will the car travel in 2 hours? Enter your result rounded...
-
Download the nasdaq-by-year-historical-annual-returns dataset in Excel from Connect or Additional Student Resources.8 Note the annual stock market returns to investment in the NASDAQ stock market...
-
UMPI Co. purchased land costing $2,550,000 as a future factory site. UMPI paid $240,000 to tear down two buildings on the land. Some Amish folks came along and paid them from the scrap lumber. They...
-
The first section of the Statement of Cash Flows, Operating Cash Flows, typically begins with Net Income, adds back non-cash expenses such as Depreciation and then also takes into account how Working...
-
Using the date below, contruct an income statement. Last year, Sun Skateboards had $ 2 0 0 , 0 0 0 in revenues. The company had $ 7 0 , 0 0 0 in COGS and $ 3 0 , 0 0 0 was SG&A . It was in the 2 1 %...
-
In "Introduction to Disciplined Agile Delivery," Carlos the Coach notices that Danny the Developer often comes late to daily scrum meetings and doesn't seem very engaged. What happens to finally...
-
5. Consider the following facts about a residential real estate investment: First year Potential Gross Income Operating Expense Ratio Vacancy Ratio Asking price Acquisition Costs (4% of price) $...
-
The release burndown chart indicates that it will take 5 more two-week sprints to finish the project, assuming no change in the team's productivity. This means the project will end later than the...
-
1. What could be the reasons for the price increase in offline retail stores? 2. From the information given in the case, can one conclude that there was a differential price response from the online...
-
The unadjusted trial balance of Secretarial Services is as follows: SECRETARIAL SERVICES Unadjusted Trial Balance as at 31 December 2017 Account Debit Credit Cash at bank Office supplies Prepaid...
-
The manager of the greeting card section of Mazeys department store is considering her order for a particular line of Christmas cards. The cost of each box of cards is $3; each box will be sold for...
-
The Senate consists of 100 senators, of whom 34 are Republicans and 66 are Democrats. A bill to increase defense appropriations is before the Senate. Thirty-five percent of the Democrats and 70% of...
-
Aaron Zeitel is a high school senior deciding which college to attend in the fall. He has narrowed his choices to three liberal arts schools: Arrington, Barton, and Claiborne. His criteria for...
-
Let \(X_{1}, \ldots, X_{n}\) be a set of independent and identically distributed random variables from a distribution \(F\) that has parameter \(\theta\). Let \(\hat{\theta}_{n}\) be an unbiased...
-
Consider a sequence of random variables \(\left\{X_{n}ight\}_{n=1}^{\infty}\) where \(X_{n}\) has probability distribution function \[f_{n}(x)= \begin{cases}{[\log (n+1)]^{-1}} & x=n \\ 1-[\log...
-
Consider an arbitrary probability measure space \((\Omega, \mathcal{F}, P)\) and let \(X_{r}\) be the collection of all possible random variables \(X\) that map \(\Omega\) to \(\mathbb{R}\) subject...
Study smarter with the SolutionInn App