The seven bridges of Konigsberg [Solution]
It's easy to see that every place in which there are
an odd number of streets must be either the start or
the stop of a path while a place with an even number
of street can be also a passage point (when you "pass"
from the place you use two streets, one for arrival
and one for departure).
In the problem one can see 4 places: the two river
sides and the two islands and all of them have an
odd number of streets and so all of them must be
either the begin or the end of a path. This is
clearly impossible.
Note that if you remove any of the bridges then
the solution is easy as we will remain with two
places with an odd number of streets and two
places with an even number of streets.
For example eliminating the bridge between the
two islands it's easy to find paths, and all
of them will start from one side and end to
the other. Or if we remove one of the bridges
of the big island to the land then we will
find paths either starting or ending on the
small island (see next figure).
Example of removal of a bridge and one
of the solutions it generates.
|
|