Page 90 - NUMINO Challenge_B2
P. 90
Basic Concepts The Bridges of Konigsberg
In the 18th century, in Konigsberg, Germany, there A
were seven bridges along the Pregel River. The people C
of the town wondered if a person could cross each B
bridge only once and return to the starting point.
The problem was known as the Bridges of Konigsberg problem. Euler, a
German mathematician, was the one who solved the problem out.
Therefore, the path that passes every arc only once is called an Euler path.
Example Here is a diagram of the Bridges of Konigsberg. Find out whether
a person can cross each bridge only once and reach the starting
point.
A
CD
B
Class Notes
The Bridges of Konigsberg problem can be thought of as a one-line drawing problem.
Use points to represent areas and lines to represent bridges.
A is connected to C by two bridges and to D by one bridge. A
C D
C is connected to B by two bridges and to D by one bridge. A
CD
B is connected to D by one bridge. B
A
CD
The figure in has B
odd-points making one-line drawing (possible, impossible).
Therefore, a person cannot cross each bridge only once and reach the starting point.
87Number of Outcomes
In the 18th century, in Konigsberg, Germany, there A
were seven bridges along the Pregel River. The people C
of the town wondered if a person could cross each B
bridge only once and return to the starting point.
The problem was known as the Bridges of Konigsberg problem. Euler, a
German mathematician, was the one who solved the problem out.
Therefore, the path that passes every arc only once is called an Euler path.
Example Here is a diagram of the Bridges of Konigsberg. Find out whether
a person can cross each bridge only once and reach the starting
point.
A
CD
B
Class Notes
The Bridges of Konigsberg problem can be thought of as a one-line drawing problem.
Use points to represent areas and lines to represent bridges.
A is connected to C by two bridges and to D by one bridge. A
C D
C is connected to B by two bridges and to D by one bridge. A
CD
B is connected to D by one bridge. B
A
CD
The figure in has B
odd-points making one-line drawing (possible, impossible).
Therefore, a person cannot cross each bridge only once and reach the starting point.
87Number of Outcomes
