Textbook; Operation Research 9th Edition, By Hamdy Taha Chapter 6.2 Minimal Span

Question

Textbook; Operation Research 9th Edition, By Hamdy Taha
Chapter 6.2 Minimal Spanning Tree Algorithm.
3. Exercise 3, Problem Set 6.2A, p. 215. Solve applying both Prim's and Kruskal's algorithms. Please Do it step by step so I could understand how to do it.

al transportation, loaded truck trailers are shipped between railroad termi- nals 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 segments 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 remaining eight wells to the delivery point. Determine the minimum pipeline network that links the wellheads to the delivery point. 5. In Figure 6.9 of Problem 4, suppose that the wellheads can be divided into two groups depending on gas pressure: a high-pressure group that includes wells 2,3,4, and 6, and a low-pressure group that includes wells 5,7,8, and 9. Because of pressure difference, it is not possible to link the wellheads from the two groups. At the same time, both groups FIGURE 6.8 Network for Problem 3, Set 6.2a SE 2000 1300 1100 800 1000 CH 200 DE DO 2000 LA 2600 780 900 1400 1300

Explanation / Answer

a)

b)

Prim'sAlgorithm In Prim's algorithm we select an arbitrary node to start Let us start with SE From SE there are 3 paths, to LA,DE, and CH Since, Prim's is a greedy algorithm we select the path with the minimum distance S.No. Segments included Visited Nodes Miles 1 SE to LA SE , LA 1100 2 LA to CH SE, LA, CH 2000 (the question specifies that LA must be connected to CH) 3 CH to DA SE, LA, CH, DA 900 (again selecting the minimum distance (900 miles) from visited nodes) 4 DA to DE SE, LA, CH, DA, DE 780 (minimum distance of 780 miles form DA) 5 CH to NY SE, LA, CH, DA, DE, NY 800 ( because only 2 nodes are left unvisited, NY and DC, and connecting these two nodes from the visited nodes, the min dis is 800 from CH) 6 NY to DC SE, LA, CH, DA, DE, NY, DC 200 (min distance = 200 miles form NY) Total miles = 5780 (as all the nodes are visited, the algorithm stops)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.