Explore BrainMass

Euler Path Problem : The Seven Bridges of Konigsberg

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

In Konigsberg, Germany, a river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. A crude map of the center of Konigsberg might look like this:

The people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once.

© BrainMass Inc. brainmass.com October 24, 2018, 6:08 pm ad1c9bdddf


Solution Preview

In the graph, the vertex1 represents the island, which is connected to the lands by 5 bridges, vertices 2, 3 and 4 represent the lands. This graph has 7 edges, which represent the 7 bridges.
Our goal is now into trying to find a path which goes through all 7 edges ...

Solution Summary

A euler path problem is solved. The solution is detailed and well presented.

See Also This Related BrainMass Solution

Properties of Relations and an Euler Walk

1. Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined over set S. See Appendix A for the definition of reflexive, symmetric, and transitive properties.
S={1,2,3} and R={(1,1), (1,2), (2,1), (2,2)}
Appendix A Definition
A relation R on a set S may have any of the following special properties.
(1) If for each x in S, x R x is true, then R is called reflexive.
(2) If y R x is true whenever x R y is true, then R is called symmetric.
(3) If x R z is true whenever x R y and y R z are both true, then R is called transitive.

(2) The city of Konigsberg, located on the banks of the Pregel River, had seven bridges that connected islands in the river to the shores as illustrated below. It was the custom of the town people to stroll on Sunday afternoons and, in particular, to cross over the bridges. The people of Konigsberg wanted to know if it was possible to stroll in such a way that it was possible to go over each bridge exactly once and return to the starting point. Is it?

View Full Posting Details