Graph Theory Assignment (Complete step by step solution is needed)

The chart below gives the time in hours to fly between cities (site: Prokeriai.com) Use the information to answer the questions below.

	New York	Chicago	Los Angeles	Miami	Dallas
New York (NY)	_______	2 hours 44 mins	5 hours 7 mins	2 hours 47 mins	3 hours 25 mins
Chicago (C)	2 hours 44 mins	-------------	4 hours 24 mins	3 hours 21 mins	2 hours 17 mins
Los Angeles (LA)	5 hours 7 mins	4 hours 24 mins	-------------	5 hours 44 mins	3 hours 20 mins
Miami (M)	2 hours 47 mins	3 hours 21 mins	5 hours 44 mins	--------	2 hours 36 mins
Dallas (D)	3 hours 25 mins	2 hours 17 mins	3 hours 20 mins	2 hours 36 mins	--------------

1.

(a) Draw a graph of the cities. Use the abbreviations given in the chart. (I want the cities to be placed appropriately, look at a map on line if necessary). Connect the cities using weighted edges. Make sure the map is large enough for me to be able to read the weights. Show all edges. This needs to be a complete graph, not just a connected graph. Feel free to attach a separate sheet if you need more space.

(b) How many Hamilton circuits are possible for this graph?

(c) What is the shortest flying time between 2 of the cities?

(d) What is the longest flying time between 2 of the cities?

(e) Find the nearest neighbor circuit starting in NY. List the circuit and give the total flying time. Make sure to give the time in hours and minutes.

(f) Find the nearest neighbor circuit starting in LA. List the circuit and give the total flying time. Make sure to give the time in hours and minutes.

(g) Find the minimal spanning tree for the graph. Draw the tree and give the total weight in hours of the graph.