Seven Bridges of Königsberg
From Math Images
(Difference between revisions)
Line 24: | Line 24: | ||
We can see this idea come into play in one failed solution. | We can see this idea come into play in one failed solution. | ||
- | [[Image: | + | [[Image:Bridges_graph2.JPG]] |
The order of the path goes 3-1-2-3-4-2. At vertex 2, we can see that this solution fails because we must choose to go to either vertex 1 or 4, but with no possible way out of those vertexes. Note that 2 is neither a starting point nor an end point, and thus with an odd number of lines, scraps any possible solution. | The order of the path goes 3-1-2-3-4-2. At vertex 2, we can see that this solution fails because we must choose to go to either vertex 1 or 4, but with no possible way out of those vertexes. Note that 2 is neither a starting point nor an end point, and thus with an odd number of lines, scraps any possible solution. |
Revision as of 14:55, 9 July 2009
Seven Bridges of Königsberg |
---|
Seven Bridges of Königsberg
- The Seven Bridges of Königsberg is a historical problem that illustrates the foundations of Graph Theory
Contents |
Basic Description
The setting of the problem is the city of Konigsberg in Prussia. The city is divided by a river with two islands. The four parts of the city are linked by seven bridges.The problem is to find a path through the city and cross each bridge once and only once. You cannot cross the rivers except on bridges and must make full crossings of a bridge (you can't go halfway across, and then walk from the other end to the midway point.)
Solution
Ideas for the Future
Make some sort of app that could allow the user to attempt to solve the problem manually. Hopefully they'll be able to trace the picture and the applet will highlight the bridge the user will not be able to go across.
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.