Modeling with Graphs

This Pull Out consists of three activities that focus on Graph Theory. Activity 1 introduces students to a new type of graph that consists of a collection of vertices and edges. Students create graphs that model nonstop airline routes between cities, a road trip to visit family and friends, a neighborhood surrounding the school, and the ancient city of Königsberg. In Activity 2, students use Euler's circuit theorem to determine whether or not it is possible to find a circuit-a path that begins and ends at the same vertex-that uses every edge in a graph exactly once. In Activity 3, students find circuits that visit each vertex in a graph exactly once before returning to the starting vertex. In situations involving costs or distances, students use the brute force algorithm and nearest neighbor algorithm to help find circuits that minimize the cost or distance.

The activities in this pull-out address Mathematical Practices #4 Model with mathematics from the Common Core State Standards for High School Mathematics.

Mathematics prerequisites and discussion: There are no specific mathematical prerequisites for this pull-out. The definitions, theorems, and algorithms needed are contained in the activities.

Materials needed: No materials are needed. Access to the Internet for Traveling Salesmen Problem games is optional.