The Seven BridgesDate: 8/28/96 at 16:9:19 From: Anonymous Subject: The Seven Bridges There is a problem from the 1700s about a town with seven bridges, where you want to cross each bridge exactly once. Date: 10/13/96 at 17:31:36 From: Doctor June Subject: Re: The Seven Bridges This is a famous problem that was sent to a mathematician named Euler (pronounced OILER). The people of Konigsberg wanted to know if they could cross all seven bridges exactly one time and end up where they started. Euler proved that it was not possible. Using Graph theory, think of the bridges as edges and the land as vertices. Being able to end where you started and crossing all edges exactly once is called an Euler Circuit. Being able to cross all edges, but NOT end where you started is called an Euler Path. Can you figure out quickly when you can have an Euler path or circuit? Hint: think odd and even! -Doctor June, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 10/13/96 at 17:31:36 From: Doctor Chuck Subject: Re: The Seven Bridges Here's the problem: There are seven bridges that cross two islands, and either side of a river. Here's a quick drawing: Pretend that the *** are water, and that BBB are bridges. | *************B******************* ***************B******************* | | ****** | ********B*******B************* ***** | | ******** **** =BBBBBBBBBBB= ***** | | ******** | ********B*******B*************************B************************** ********B*******B*************************B************************** | | | These are very pretty bridges. The question arose, can a tourist cross all seven bridges in an afteroon without crossing the same bridge twice? We can draw this problem as a graph, with each vertex representing one of the pieces of land, and each edge being a bridge. ...O......... | | \ \ / \ O.............O / \ / | | / ...O......... It turns out to be impossible to make a cycle on this graph that goes over every path exactly once. You can look up a good discussion of these types of problems at: http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Topology_in_mathematics.html Hope this helps, -Doctor Chuck, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/