| Version 5 |
Version 4 |
| \PMlinkescapeword{bridge} |
\PMlinkescapeword{bridge} |
| \PMlinkescapeword{bridges} |
\PMlinkescapeword{bridges} |
| \PMlinkescapeword{map} |
\PMlinkescapeword{map} |
| \PMlinkescapeword{representation} |
\PMlinkescapeword{representation} |
| The \emph{bridges of K\"onigsberg} is a famous problem inspired by an actual place and situation. The solution of the problem, put forth by Leonhard Euler in 1736, is the first work of graph theory and is responsible for the foundation of the discipline. |
The \emph{bridges of K\"onigsberg} is a famous problem inspired by an actual place and situation. The solution of the problem, put forth by Leonhard Euler in 1736, is the first work of graph theory and is responsible for the foundation of the discipline. |
| The following figure shows a portion of the Prussian city of K\"onigsberg. A river passes through the city, and there are two islands in the river. Seven bridges cross between the islands and the mainland: |
The following figure shows a portion of the Prussian city of K |
| \begin{center} |
nigsberg. A river passes through the city, and there are two islands in the river. Seven bridges cross between the islands and the mainland: |
| \includegraphics[scale=.5]{koenigs1} |
|
| {\tiny Figure 1: Map of the K\"onigsberg bridges.} |
|
| \end{center} |
|
| The mathematical problem arose when citizens of K\"onigsburg noticed that one could not take a stroll across all seven bridges, returning to the starting point, without crossing at least one bridge twice. |
|
| Answering the question of why this is the case required a mathematical theory that didn't exist yet: graph theory. This was provided by Euler, in a paper which is still available today. |
|
| To solve the problem, we must translate it into a graph-theoretic representation. We model the land masses, $A$, $B$, $C$ and $D$, as vertices in a graph. The bridges between the land masses become edges. This generates from the above picture the following graph: |
|
| \begin{center} |
|
| \psfrag{A}{$A$} |
|
| \psfrag{B}{$B$} |
|
| \psfrag{C}{$C$} |
|
| \psfrag{D}{$D$} |
|
| \psfrag{1}{$1$} |
|
| \psfrag{2}{$2$} |
|
| \psfrag{3}{$3$} |
|
| \psfrag{4}{$4$} |
|
| \psfrag{5}{$5$} |
|
| \psfrag{6}{$6$} |
|
| \psfrag{7}{$7$} |
|
| \includegraphics[scale |
|
| passes through the city, and there are two islands in the river. Seven bridges cross between the islands and the mainland: |
|
| \begin{center} |
\begin{center} |
| \includegraphics[scale=.5]{koenigs1} |
\includegraphics[scale=.5]{koenigs1} |
| {\tiny Figure 1: Map of the K |
{\tiny Figure 1: Map of the K |
| nigsberg bridges.} |
nigsberg bridges.} |
| \end{center} |
\end{center} |
| The mathematical problem arose when citizens of K\"onigsburg noticed that one could not take a stroll across all seven bridges, returning to the starting point, without crossing at least one bridge twice. |
The mathematical problem arose when citizens of K\"onigsburg noticed that one could not take a stroll across all seven bridges, returning to the starting point, without crossing at least one bridge twice. |
| Answering the question of why this is the case required a mathematical theory that didn't exist yet: graph theory. This was provided by Euler, in a paper which is still available today. |
Answering the question of why this is the case required a mathematical theory that didn't exist yet: graph theory. This was provided by Euler, in a paper which is still available today. |
| To solve the problem, we must translate it into a graph-theoretic representation. We model the land masses, $A$, $B$, $C$ and $D$, as vertices in a graph. The bridges between the land masses become edges. This generates from the above picture the following graph: |
To solve the problem, we must translate it into a graph-theoretic representation. We model the land masses, $A$, $B$, $C$ and $D$, as vertices in a graph. The bridges between the land masses become edges. This generates from the above picture the following graph: |
| \begin{center} |
\begin{center} |
| \psfrag{A}{$A$} |
\psfrag{A}{$A$} |
| \psfrag{B}{$B$} |
\psfrag{B}{$B$} |
| \psfrag{C}{$C$} |
\psfrag{C}{$C$} |
| \psfrag{D}{$D$} |
\psfrag{D}{$D$} |
| \psfrag{1}{$1$} |
\psfrag{1}{$1$} |
| \psfrag{2}{$2$} |
\psfrag{2}{$2$} |
| \psfrag{3}{$3$} |
\psfrag{3}{$3$} |
| \psfrag{4}{$4$} |
\psfrag{4}{$4$} |
| \psfrag{5}{$5$} |
\psfrag{5}{$5$} |
| \psfrag{6}{$6$} |
\psfrag{6}{$6$} |
| \psfrag{7}{$7$} |
\psfrag{7}{$7$} |
| \includegraphics[scale=.9]{koenigs2} |
\includegraphics[scale=.9]{koenigs2} |
| {\tiny Figure 2: Graph-theoretic representation of the K\"onigsburg bridges.} |
{\tiny Figure 2: Graph-theoretic representation of the K\"onigsburg bridges.} |
| \end{center} |
\end{center} |
| At this point, we can apply what we know about Euler paths and Euler circuits. Since an Euler circuit for a graph exists only if every vertex has an even degree, the K\"onigsberg graph must have no Euler circuit. Hence, we have explained why one cannot take a walk around K\"onigsberg and return to the starting point without crossing at least one bridge more than once. |
At this point, we can apply what we know about Euler paths and Euler circuits. Since an Euler circuit for a graph exists only if every vertex has an even degree, the K\"onigsberg graph must have no Euler circuit. Hence, we have explained why one cannot take a walk around K\"onigsberg and return to the starting point without crossing at least one bridge more than once. |
