Projects

Everyone Gets a Turn! – Graph Colorings

Let’s put your knowledge of graph colorings to work! Your task is to plan a field day following these steps.

1. Select between seven and ten activities for your field day. You can look online for ideas.
2. Create a survey asking for the participants to select the three to five events in which they would most like to participate. Survey between seven and ten people.
3. Use the results of your survey to create a graph in which each vertex represents one of the events. A pair of vertices will be adjacent if there is at least one participant who would like to participate in both events.
4. Find a minimum coloring for the graph. Explain how you found it and how you know the chromatic number of the graph.
5. Use your solution to part d to determine the minimum number of timeslots you must use to ensure that everyone has the opportunity to participate in their top three events.
6. Find the complement of the graph you created. Explain what the edges in this graph represent.

A Beautiful Day in the Neighborhood – Euler Circuits

Let’s apply what you have learned to the community in which you live. Using resources such as your county’s property appraiser’s website, create a detailed graph of your neighborhood in which vertices represent turns and intersections. Represent a large enough part of your community to include no fewer than 10 intersections or turns. Then use your graph to answer the following questions.

1. Label the edges of your graph.
2. Determine if your graph is Eulerian. Explain how you know. If it is not, eulerize it.
3. Find an Euler circuit for your graph. Give the sequence of vertices that you found.
4. What does the Euler circuit you found in part c represent for your community?
5. Describe an application for which this Euler circuit might be used.

Dream Vacation – Hamilton Cycles and Paths

Where in the world would you like to travel most: the Eiffel Tower in Paris, a Broadway musical in New York city, a bike tour of Amsterdam, the Tenerife whale and dolphin cruises in the Canary Islands, the Giza Pyramid in Cairo, or maybe the Jokhang Temple in Tibet? Let's plan your dream vacation!

1. Which four destinations are at the top of your bucket list?
2. Draw a complete weighted graph with five vertices representing the four destinations and your home city, and the weights representing the cost of travel between cities.
3. Use a website (such as Travelocity) to find the best airfare between each pair of cities. List the airlines and flight numbers along with the prices. Include cost for ground transportation from the nearest airport if there is no airport at the destination you want to visit.
4. Use the nearest neighbor algorithm to find a Hamilton cycle of low weight beginning and ending in your hometown. What is the weight of this circuit and what does it represent?
5. Use the brute force method to find a Hamilton cycle of lowest weight beginning and ending in your hometown. What is the weight of this circuit? Is it the same or different from the weight of the Hamilton cycle you found in Exercise 4?
6. Suppose that instead of returning home, you planned to move to your favorite location on the list, but you wanted to stop at the other three destinations once along the way. Where would you move? List all Hamilton paths between your hometown and your favorite location.
7. Find the weights of all the Hamilton paths you found in Exercise 6.