MAT 100 Final Part II Section A: Answer both questions. Show all work. (32 pts 1. The costs of one-way flights between several U.S. cities are shown in the table below: $64 St. Louis Kansas City Ok. City Des Moines Little Rock St. Louis $55 $70 $445 Kansas City $55 $64 $195 $83 Ok. City $70 $64 $405 $96 Des Moines $445 $195 $405 $352 Little Rock $64 $83 $96 $352 a) Represent this traveling salesman problem with a complete graph showing the costs on the appropriate edges. [4pts) b) Using the Nearest Neighbor algorithm, estimate the minimum cost for a trip that starts in Des Moines, travels to all the other cities once, and then returns to Des Moines. Give the cost of the route found. [4pts) c) Randomly select another route from Des Moines to the other cities and compute the cost of this route. Compare this cost to the cost found in part (b). [4pts) d) Find two different spanning trees for the graph (4pts) MAS