Taking Walks, Delivering Mail: An Introduction to Graph Theory

Taking Walks, Delivering Mail: An Introduction to Graph Theory
English

Instructors

Karima R. Nigmatulina
Operations Research Center
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139 USA

Lesson Feedback

Introduction

This learning video presents an introduction to graph theory through two fun, puzzle-like problems: “The Seven Bridges of Königsberg” and “The Chinese Postman Problem”. Any high school student in a college-preparatory math class should be able to participate in this lesson. Materials needed include: pen and paper for the students; if possible, printed-out copies of the graphs and image that are used in the module; and a blackboard or equivalent. During this video lesson, students will learn graph theory by finding a route through a city/town/village without crossing the same path twice. They will also learn to determine the length of the shortest route that covers all the roads in a city/town/village. To achieve these two learning objectives, they will use nodes and arcs to create a graph and represent a real problem. This video lesson cannot be completed in one usual class period of approximately 55 minutes. It is suggested that the lesson be presented over two class sessions.

Online Animations: visit our interactive Chinese Postman Flash Simulation to practice using this algorithm with examples from the handout and more! Click here.

Instructor Biography

When she made this BLOSSOMS video, Karima R. Nigmatulina was a Ph.D. student at the Operations Research Center at MIT and was interested in the applications of mathematics in public policy and social sector issues. Today, she remains interested in these areas as she is a member of the research staff of Intellectual Ventures Lab of Bellevue, Washington, where she works on Epidemiological Modeling.

Additional Online Resources

6.4 ROUTING PROBLEMS
Section 6.4 (multiple parts) of the book, Urban Operations Research, available on the web for more examples and details on the algorithm

Wikepedia: Graph theory
Basic Graph Theory Information: A little basic info and a description of a few graph theory problems from Wikepedia