There is a town in Russia whose
name today is Kaliningrad. Click here to surf their web site! or click here if you'd like some information without actually surfing their site. In the 1700s, it was in Prussia and its name was Königsberg. Here's a true story. Once upon a time (OK, in the 18th century), in a place far away (well, Prussia), there once was a town called Königsberg. The townspeople enjoyed walking through their town and passing over the bridges spanning the river which passed through town. Over the years, a controversy arose and eventually word of it reached a very famous mathematician of the time, Leonhard Euler. Euler described the controvery himself in the following letter:
Euler went on to formulate a general theory which solved this particular problem and created a new branch of mathematics called graph theory. Let's reconstruct Euler's solution to the bridge problem. First, we will take a closer look at the bridges and the river.
Now let’s strip away some of the distractions:
Simplifying things once again:
A final simplification: The figure above is called a graph. The dots are called vertices and the paths connecting the vertices are called edges. The graph is the fundamental structure in the field of graph theory. Euler used the graph above to solve the Königsberg bridge problem. We will use graphs to solve routing problems. The term, graph, is defined formally below. GRAPH |