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 pullout 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 pullout.
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.
