‪Taking Walks, Delivering Mail: An Introduction to Graph Theory‬

MIT Blossoms

No votes yet
165 Downloads 986 Views Updated: Saturday, May 6, 2017 - 12:06pm
Share with a friend

‪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! ‬View here ‪http://blossoms.mit.edu/video/nigmatulina/ChinesePostman.swf

For more information, visit http://blossoms.mit.edu/videos/lessons/taking_walks_delivering_mail_intr....