MIT BLOSSOMS - Taking Walks, Delivering Mail: An Introduction to Graph Theory

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.
Resource ID#: 18126 Type: Video/Audio/Animation
Rate It!
Feedback?

Please sign in to access this resource

Teacher
Click here to sign in
as a FL public educator

Not a Florida public school educator?

Access this resource
on CPALMS.com

Open Resource Page Open Resource Page


Direct Link: http://blossoms.mit.edu/videos/lessons/taking_walks_delivering_mail_introduction_graph_theory

General Information

Subject(s): Mathematics
Grade Level(s): 9, 10, 11, 12
Intended Audience: Educators educators
Suggested Technology: Computer for Presenter, LCD Projector, Speakers/Headphones, Adobe Flash Player, Adobe Acrobat Reader
Instructional Time: 1 Hour(s) 30 Minute(s)
Keywords: graph theory, The Seven Bridges of Königsberg, Eulerian tour, The Chinese Postman Problem, shortest path, Dijkstra algorithm
Instructional Component Type(s): Video/Audio/Animation,  Lesson Plan,  Worksheet,  Problem-Solving Task, 
Instructional Design Framework(s): Guided Inquiry (Level 3), Learning Cycle (e.g., 5E)
Resource Collection: MIT BLOSSOMS

Aligned Standards

This vetted resource aligns to concepts or skills in these benchmarks.

Related Resources

Other vetted resources related to this resource.