Seven Bridges of KönigsbergThe Seven Bridges of Königsberg is a famous problem from the annals of mathematics. The problem was to devise a walk through the city of Königsberg, which would cross each of the city's seven bridges once and only once. (Leonhard Euler proved in 1736 that the problem had no solution, using ideas that laid a foundation for modern graph theory.)
|
Graph theory problems are easier to understand once reduced to graph drawings. The graph drawing for the Bridges of Königsberg is shown at right.
Starting from a point of your choosing, is it possible to traverse each edge p, q, r, s, t, u and v once and only once, without removing your pencil from the paper? Why or why not?
Starting from a point of your choosing, is it possible to traverse each edge p, q, r, s, t, u and v once and only once, without removing your pencil from the paper? Why or why not?
Let's begin by learning how to express basic concepts in graph theory. A route around a graph that visits each vertex once is called a simple path. A route around a graph that visits each edge exactly once is called an Euler path. The Bridges of Königsberg problem asks for an Euler path.
The number of edges that lead to each vertex is called its degree. Is there a quick and easy way to use the degrees of each vertex to identify graphs that do or don't have Euler paths? The Hamilton Village problem above can be solved quickly with the rule, if you can find it. Complete the MathIsFun: Bridges of Königsberg activity to discover the rule of thumb!
For more fun with graph theory, install Graph Theory Pad on iTunes!
Graph Theory Pad is a free iOS app that lets you draw, annotate, save, and share your work on graph theory problems. Graph Theory Pad even supports pdf exports and in-app calculations for counting and probabilistic functions (nCr and nPr).
Graph Theory Pad is a free iOS app that lets you draw, annotate, save, and share your work on graph theory problems. Graph Theory Pad even supports pdf exports and in-app calculations for counting and probabilistic functions (nCr and nPr).