and Network Matrices
A Brain Teaser
Swiss mathematician Leonhard Euler was enormously prolific, but he is best
remembered for devising the solution to a recreational math problem: the
Seven Bridges of Koenigsberg. At one time, it was fashionable to stroll
through the Prussian town of Koenigsberg and ponder this problem: Could
one cross each of the seven bridges that traversed the Pregel River and connected
the various districts once and only once?
Although the problem itself was simple - was it possible
to walk a circuit that crossed each bridge only once? Euler found the
solution by making the situation even simpler. He replaced the bridges
and islands of Koenigsberg with lines and points. The four landmasses
(two islands and both riverbanks) became special points, or nodes, that were
connected by seven lines representing the bridges. Using that abstract
graph, Euler demonstrated that to complete a circuit, there would have to
be a maximum of two places where an odd number of lines met, and if a return
to the start was required, there would have to be no places where an odd
number of lines met. The reasoning is simple, once seen: a continuous
journey will enter each such junction exactly as often as it leaves except
at the start and finish. Since the graph of Koenigsberg had four
nodes, each of which possessed an odd number of lines, no solution could
Euler's problem is really one of topology, the branch
of mathematics that deals with the properties of figures that are preserved
during continuous distortions. Two networks are topologically equivalent
if one can be distorted to give the other, as can the city of Koenigsberg
and Euler's graph of the city. If a network can be traversed by a single
continuous path, so can any topologically equivalent network.
Euler's work on the bridges of Koenigsberg founded the
field of graph theory. Not bad for one recreational math puzzle!!!
Borrowed from : 1000 Play Thinks by Ivan Moscovich 2001
Now you try. Can you solve this puzzle using
1. Solve the puzzle.
2. How can this information help you to
analyze network matrices.