Discrete Mathematics Projects CHECKER TOURNAMENT Goals (1) Students will explore the concept of graph theory as it relates to scheduling. (2) Students will derive a schedule to meet all the criteria of the tournament. (3) Students will explain and justify how they determined a schedule to meet the needs of the tournament. Abstract This activity focuses on applying graph theory to derive a schedule to meet the criteria of a tournament. Students will devise a schedule so that all the criteria of the tournament are met. Students will create a Power Point presentation explaining and justifying their schedule and/or methods to the instructor. This activity could be used to introduce graph theory such as to develop a schedule. Discussion of the problem could extend to exploring how to determine the tournament winner or ranking schedule. Problem Statement Scheduling for tournaments can be very intricate due to special circumstances and criteria that needs to be met. Students are to develop a schedule that meets the criteria of the checker tournament and its players and is easy for everyone to see who plays whom each day. This activity will allow students to explore and apply graph theory. Instructions Make a schedule for the following tournament. The schedule should meet tournament criteria listed below and should make it easy for everyone to know who plays whom each day. Explore possible schedules and determine a process or method to produce the most efficient schedule that meets all of the criteria. Students will present and explain their processes, methods, and schedules to the instructor. TOURNAMENT CRITERIA: Mike, Tammy, Rob, and Tina decide to have a checker tournament at school. They want to be sure that each of them gets a chance to play everyone once. They have asked you to make a schedule for their tournament that meets the following criteria: The tournament will last for one week. They can play only from Monday to Friday. The tournament will occur during lunch time since there is enough time during lunch to play one game of checkers. They have two checker sets, therefore, two games can occur at the same time. Mike cannot play checkers on the days he has other meetings which are on Mondays and Wednesdays. Each player must play every other player once. How Many Colors? Goals 1. Students will explore the concept of map coloring. 2. Students will work in order to arrive at the smallest number of colors needed and decide if that number is correct. They will also be able to explain, and justify, how they arrived at this solution. Abstract This activity, which is set in the context of having students find the minimum number of colors needed to color a map is related to graph theory and map coloring problems. Students are asked to come with a method for coloring maps. This method will then be shared with the instructor. Problem Statement In reading maps, it is helpful to be able to distinguish countries or states by means of their colors. States that touch one another should not have the same color as it would be hard to find their boundaries. When coloring maps, it is optimal to use as few colors as possible. How does one determine how many different colors are needed to color any map? Students will be asked to devise methods for determining how many colors are needed to color any given map. Instructions Does there exist a method for coloring maps with the least amount of different colors? No two adjacent or touching state can have the same colors. One possible coloring would be to choose eleven different colors and give each state its own color. This is definitely not the minimum amount of colors that could be used. Your job is to devise a method of coloring this map of these eleven states so that you use the minimum number of colors and that no adjacent states use the same color. When you think you have a method that works, write down the steps involved in using your method so that another student can understand your steps and color the map by your method. Use your set of steps to try your coloring algorithm on the second map below. If it does not work, go back to the original map and steps and modify your method. Try your method on the second map until it works on that one too. When you are convinced that your method works, exchange your instruction list with the instructor in a Power Point presentation. Discuss your method thoroughly. What's the Shortest Route? Goals 1. Students will explore the concepts of circuits and paths as it relates to the shortest route between cities. 2. Students will work in order to arrive at the shortest route solution and be able to explain, and justify, how they arrived at this solution. Abstract This activity, which is set in the context of having students find the shortest route between cities is related to graph theory, circuits and paths. Students are asked to come with a method for traveling between cities in a way that allows them to visit each city using the fewest miles. These methods and solutions are then shared with the instructor. Problem Statement Finding the shortest route between cities is an important task for most businesses that require their employees to travel to various cities. Shortest routes usually save time and money and keep the travelers from returning to cities too often. In this activity, the students will be asked to determine the shortest route between several cities. They will also be asked to justify their method for coming up with the shortest route. Instructions Suppose a salesperson wishes to travel to each city in the map below exactly once, starting and ending in New York, and using only the roads shown. The numbers on the roads indicate distances (in miles) between cities. Find the shortest route that the salesperson could use. Look for a method that will work every time you try a problem like this. Are you convinced that your route is the shortest? Why? Create a Power Point presentation to trace your route and give supporting evidence of why you think your route is the shortest. Score Comments: Grade