Seven Bridges of Königsberg

From Math Images

(Difference between revisions)
Jump to: navigation, search
Current revision (07:07, 26 November 2011) (edit) (undo)
(Undo revision 28262 by 144.118.94.68 (Talk))
 
(28 intermediate revisions not shown.)
Line 1: Line 1:
-
{{Image Description
+
{{Image Description Ready
|ImageName=Seven Bridges of Königsberg
|ImageName=Seven Bridges of Königsberg
|Image=Konigsberg bridges.png
|Image=Konigsberg bridges.png
-
|ImageIntro=The Seven Bridges of Königsberg is a historical problem that illustrates the foundations of graph theory.
+
|ImageIntro=The Seven Bridges of Königsberg is a historical problem that illustrates the foundations of [[Field:Graph Theory|Graph Theory]]
|ImageDescElem=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.
|ImageDescElem=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 essentially to walk through the city and cross each bridge once and only once.
+
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==
==Solution==
-
While we could literally test out every possible case by hand, this would be extremely tedious and prone to error. Instead we will analyze the problem abstractly. By abstract, we mean to essentialize the problem; in this case, eliminating all features possible.
+
{{hide|1=While we could literally test out every possible case by hand, this would be extremely tedious and prone to error but possible. Instead we will analyze the problem abstractly by eliminating all inessential details to get a better grip on the problem.
-
Our first step is to remove the distractions of the image itself.
+
Our first step is to remove the original image's distractions.
-
[[Image:Bridgepaint1.JPG]]
+
[[Image:Simplifiedbridges3.PNG]]
-
From here we can make the observation that the size of the islands, sides of the river, and even the river itself are irrelevant. In addition the distances between the land masses are immaterial, thus the lengths of the bridges are irrelevant. Keeping these observations in mind, we resize the landmasses to points, and the bridges to lines.
+
From here we can make the observation that the size of the islands, sides of the river, and even the river itself are irrelevant. In addition the distances between the land masses are immaterial, thus the lengths of the bridges are irrelevant. Keeping these observations in mind, we resize the landmasses to points, and the bridges to lines .
-
[[Image:Konigsburg graph.svg.png]]
+
[[Image:Bridges graph.JPG]]
 +
 
 +
From here on we will use the word line instead of bridge, and <balloon title="A vertex is a point where two line segments.">vertex</balloon> instead of landmasses.
 +
 
 +
Now we make the key observation that, except for the starting and finishing landmass, the walker must exit each landmass exactly as many times as she enters it, and each entry and exit must be through a different line. In order for this to be possible there must be an even number of lines at every vertex with the exceptions of the starting and finishing vertexes of the walk. For those two vertexes, an odd number of vertexes is permitted since the walker only exits the starting vertex and only enters the final vertex.
 +
 
 +
We can see this idea come into play in one failed solution.
 +
 
 +
[[Image:Bridges_graph2.JPG]]
 +
 
 +
The order of the path goes 3-1-2-3-4-2-1. At vertex 1, we can see that this solution fails because we get in but have no way out. Since vertex 1 is neither a starting point nor an end point (since we still have to go to vertex 4), and with an odd number of lines, scraps any possible solution that has vertex 1 as an intermediate vertex.
 +
 
 +
Looking back at the previous figure, we can see that all four vertexes have an odd number of lines. The existence of a path that could reach all four landmasses is impossible because it would go through more than two vertexes with odd number of lines.
 +
 
 +
Leonard Euler first solved this problem in 1735.}}
 +
 
 +
==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.
-
Now we make the key observation that the walker must enter and exit every landmass.
 
|AuthorName=Bogdan Giuşcă
|AuthorName=Bogdan Giuşcă
-
|Field=Topology
+
|Field=Graph Theory
 +
|Pre-K=No
|InProgress=Yes
|InProgress=Yes
}}
}}

Current revision

Image:inprogress.png
Seven Bridges of Königsberg
Field: Graph Theory
Image Created By: Bogdan Giuşcă

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

While we could literally test out every possible case by hand, this would be extremely tedious and prone to error but possible. Instead we will analyze the problem abstractly by eliminating all inessential details to get a better grip on the problem.

Our first step is to remove the original image's distractions.

Image:Simplifiedbridges3.PNG

From here we can make the observation that the size of the islands, sides of the river, and even the river itself are irrelevant. In addition the distances between the land masses are immaterial, thus the lengths of the bridges are irrelevant. Keeping these observations in mind, we resize the landmasses to points, and the bridges to lines .

Image:Bridges graph.JPG

From here on we will use the word line instead of bridge, and vertex instead of landmasses.

Now we make the key observation that, except for the starting and finishing landmass, the walker must exit each landmass exactly as many times as she enters it, and each entry and exit must be through a different line. In order for this to be possible there must be an even number of lines at every vertex with the exceptions of the starting and finishing vertexes of the walk. For those two vertexes, an odd number of vertexes is permitted since the walker only exits the starting vertex and only enters the final vertex.

We can see this idea come into play in one failed solution.

Image:Bridges_graph2.JPG

The order of the path goes 3-1-2-3-4-2-1. At vertex 1, we can see that this solution fails because we get in but have no way out. Since vertex 1 is neither a starting point nor an end point (since we still have to go to vertex 4), and with an odd number of lines, scraps any possible solution that has vertex 1 as an intermediate vertex.

Looking back at the previous figure, we can see that all four vertexes have an odd number of lines. The existence of a path that could reach all four landmasses is impossible because it would go through more than two vertexes with odd number of lines.

Leonard Euler first solved this problem in 1735.

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.









If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools