Student Procedures

Activity

You and your team are a group of planners for a new airline. You wish to provide service to all cities, but wishing to save money, you want to have as few different routes as possible, and you want those routes to be as short as possible. Using what you have learned about weighted graphs, trees, and shortest paths, find the optimal way to connect all five cities using the fewest, shortest flights.

Procedures

Design a table in Microsoft Excel (or other spreadsheet tool) with the following columns: City A, City B, City C, City D, and City E. Repeat these entries as rows, but also leave a space to enter the code you will look up. The resulting table should look something like this:

	City A	City B	City C	City D	City E
City A Code:_______
City B Code:_______
City C Code:_______
City D Code:_______
City E Code:_______

Go to: http://en.wikipedia.org/wiki/List_of_airports_in_the_United_States
Search through the different states, and locate 5 airports, and write down their “ICAO Code” for each. Edit your table to reflect the 5 new cities you found (i.e. replace City A with Charlotte, and put KCLT for the Code)
Once you have your five codes, visit http://www.landings.com/_landings/pages/search/search_dist_apt.html and use the form there to find the distance between any two airports. Record the data in your table as follows: the cell below City A and to the right of City B represents the distance from City A to City B. Complete the table.
Use data from table to create a weighted graph on the five vertices using a graphics editing tool (such as MS Paint) or Geometer's SketchPad. For an example of a weighted graph, click the link above. The weights (labels along the edges) should be the distances, and the vertices should be the airports.
Using all the information you have collected, figure out the optimal way to connect all airports using the conditions given in the activity.
Complete a group write-up that answers the following questions:
- Show and explain how you came up with your solution. Do you think this method would always work for solving this type of problem?
- What are some properties of your solution graph? Does it contain cycles? Could it contain cycles?
- Is finding the shortest path connecting all these airports really the best way to do things? What problems do you think this might cause for the airport
Each individual in the group should write a brief letter to the head of the airline explaining their solutions, why it works, and how you came up with it, all in layman's terms.

Brain Teaser

Supposed the chart below represents the cost per mile to travel between any two cities via the airline. Does this change your proposed routes? If so, what is the new set of routes and how do you know?

	City A	City B	City C	City D	City E
City A Code:_______	0	$1	$2	$3	$4
City B Code:_______	$1	0	$5	$6	$7
City C Code:_______	$2	$5	0	$8	$9
City D Code:_______	$3	$6	$8	0	$10
City E Code:_______	$4	$7	$9	$10	0