Seven Bridges of Königsberg

From Math Images

(Difference between revisions)
Jump to: navigation, search
Line 15: Line 15:
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]]
 +
 +
Now we make the key observation that the walker must enter and exit every landmass.
|AuthorName=Bogdan Giuşcă
|AuthorName=Bogdan Giuşcă

Revision as of 12:58, 17 June 2009

Image:inprogress.png

Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historical problem that illustrates the foundations of graph theory.


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 essentially to walk through the city and cross each bridge once and only once.

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.

Our first step is to remove the distractions of the image itself.

Image:Bridgepaint1.JPG

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

Now we make the key observation that the walker must enter and exit every landmass.





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