Index

Discrete Mathematics Project

Graph Theory Activity

Title

What's the Shortest Route? (Dorothy Gieck)

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 small groups 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 to consensus within a small group as to 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 rest of the class.

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.

Instructor Suggestions

1. Set the stage by discussing the "Problem Statement" (see above) with your students.

2. Have students form small groups.

3. Distribute the "What's the shortest route?" activity sheets and allow students to work in their small groups to come up with the appropriate solutions.

4. Circulate between the groups and facilitate the discussions.

5. When the small groups are finished, have a spokesperson for each group share their solution and explain their method and reasoning involved in arriving at their routes.

6. Discuss the students work as it relates to graph theory and circuits.

Materials

"What is the Shortest Route?" activity sheet, overhead projector, overhead pens, transparencies with map on them, for recording results.

Time

Introduction of Problem Statement (5 min.), small group work (25 min.), presentation of small group work and large group discussion (30 min.), extension questions (15 min.).

Mathematics Concepts

Discrete Mathematics Concepts:

Circuits, representation of graphs, critical paths, Euler circuits and paths, Hamiltonian circuits and paths.

Related Mathematics Concepts:

Matrices, Modeling with graphs, Optimizing results

Problem Solving, Communication, Reasoning, Connections

Geometric Techniques (4), Problem Solving Techniques (5), Linking Concepts and Procedures (6)

Curriculum Integration

This activity could be integrated into most any level. Discussion could include discrete mathematics topics related to graph theory, circuits and paths. With a lower level class you might use this activity to communicate methods of coming up with solutions. It would use more class time and become a communication/presentation tool. This activity could be used with a traditional Advanced Algebra or Pre-Calculus class when the topics of matrix operations are examined.

Further Investigation

This activity can be extended by having students pick five other cities, researching the distances and trying their algorithm to see if it works in this new case.