MIT Massachusetts Institute of Technology

Taking Walks, Delivering Mail: An Introduction to Graph Theory

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

 


Lesson vetted and approved by CPALMS

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.

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.

The Seven Bridges of Königsberg: Math Forum: Leonhard Euler and the Bridges of Königsberg gives more examples and a few sample problems of Eularian paths and routes
http://mathforum.org/isaac/problems/bridges1.html

Section 6.4 (multiple parts) of the book, Urban Operations Research, available on the web for more examples and details on the algorithm
http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.html

Basic Graph Theory Information: A little basic info and a description of a few graph theory problems from Wikepedia
http://en.wikipedia.org/wiki/Graph_theory

Add A Comment
By submitting this form, you accept the Mollom privacy policy.

This Lesson is in the following clusters: Graph Theory