*************************************************************************************

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.