Title
The Show Must Go On (Liz Sansone)
Goals
Students will explore the concept of graph theory as it relates to trees and the Hamiltonian circuit.
Abstract
Students are asked to form groups and design both a graph and a tree illustrating the distances between given houses and then apply the traveling salesperson problem (TSP).and Hamiltonian circuit. Each group is then asked to present and explain their method to the class.
Problem Statement
Discuss with your students that we have all been in situations when we are pressed for time and we must find the shortest way to get everything accomplishes. This activity will allow students to explore a graph theory situation and employ discrete mathematics in devising a method that will locate the shortest path..
Instructor Suggestions
1) Discuss "Problem Statement" from above with your students.
2) Decide on a method to have students form small groups
3) Distribute "The Show Must Go On" activity sheet, also distribute a transparency and a marker to each group, one person needs to illustrate the groups' approach..
4) When the small groups are finished, have a spokesperson for each group share their method using the transparency that they prepared.
5) Discuss the students' work as it relates to group theory
Materials
"The Show Must Go On" activity sheet, transparencies, markers.
Time
Introduction (5 min.) small group work (20 min.), presentation of small group work and large group discussion (20 min.).
Mathematics Concepts
Discrete Mathematics Concepts
Group Theory, Hamiltonian circuit, the traveling salesperson problem, circuits, trees, nearest neighbor algorithm, heuristic method, weighted graph
Related Mathematics Concepts
Edges, vertices, adjacency,
NCTM Standards Addressed
Problem Solving, Communication, Reasoning, Connections, Algebra, Geometry, Discrete Math.
Colorado Model Content Standards Addressed
Algebraic Techniques (2), Problem Solving Techniques (5), Linking Concepts and Procedures (6)
Curriculum Integration
This activity could be integrated into a traditional or Integrated Algebra and/or Geometry class as the topics of modeling, vertices, edges, graphs, circuits
Further Investigation
Extend the problem by having the club leader go to the school to post signs after the last member's house instead of returning home(minimum spanning tree problem)
Variations/Comments
Have club leader only need to go to 2 of the 6 and then delegate the communication..
References/Resources
Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete mathematics through applications. New York: W.H. Freeman and Company.