Question

Travel to SLCC’s Campuses

Below is a map of some of SLCC’s locations followed by the distances between campuses.
Taylorsville to South City: 8 miles Jordan to Miller: 5 miles
Taylorsville to West Valley: 6.3 miles South City to West Valley: 11.2 miles
Taylorsville to Herriman: 15.8 miles South City to Herriman: 24 miles
Taylorsville to Miller: 9.3 miles South City to Miller: 12.3 miles
Taylorsville to Jordan: 9 miles Herriman to West Valley: 14 miles
Jordan to South City: 16 miles Herriman to Miller: 11 miles
Jordan to West Valley: 10.5 miles Miller to West Valley: 15 miles
Jordan to Herriman: 8.5 miles
1. (15 points) On a separate paper draw and label a graph of the map (do not include Meadowbrook).
The locations are the vertices – use T for Taylorsville, J for Jordan, S for South City, W for West Valley, M
for Miller, and H for Herriman. The weights of the edges are the distances, in miles, between campuses.
Answer the questions on the next page:
2. (10 points) Apply the Nearest Neighbor Algorithm to your graph. Write your answer as a list of
vertices, starting and ending at the Taylorsville Campus, and give the total miles.
3. (10 points) Apply the Sorted Edges Algorithm to the graph. Write your answer as a list of vertices,
starting and ending at the Jordan Campus, and give the total miles.
4. (10 points) Find the minimum cost (lowest miles) spanning tree using Kruskal’s Algorithm. What is
the total miles? Draw the graph.
5. (5 points)
a. Given your answers above, if you had to travel to all six locations and return to where you started,
which method would you use? Why?
b. Even though Kruskal’s Algorithm produces the fewest total miles, why would you not use it if you
had to return to where you started?

Answer 1

Travel to SLCC’s CampusesBelow is a map of six of SLCC’s locations followed by the distances between campuses. West Valley CenterMeadowbrookTaylorsvilleTaylorsville to South City:8 miles Jordan to Miller:5 milesTaylorsville to West Valley:7 miles south City to West Valley:11 milesTaylorsville to Meadowbrook:3.6 miles south City to Meadowbrook: 4.5 milesTaylorsville to Miller:9.3 milesSouth City to Miller:12.3 milesTaylorsville to Jordan:9 milesMeadowbrook to West Valley:8 milesJordan to South City:16 miles Meadowbrook to Miller:9.6 miles Jordan to West Valley:10.5 milesMiller to West Valley:15 miles Jordan to Meadowbrook:12 miles(15 points) On a separate paper draw and label a graph of the map. The locations are the vertices –used for Taylorsville, J for Jordan, S for South City, W for West Valley, M for Miller, and B

Explanation: