x

graphen
Leonhard Euler's Problem of The Bridges of Königsberg and a Suitable Graph (seven bridges of königsberg problem)

Was it possible to have a parade through what was then Königsberg, in such a way, that the parade route crossed every bridge, but none of those more often than once? This problem gave Carl Leonhard Gottlieb Ehler sleepless nights until he approached Leonhard Euler. Euler refused at first, because this was not a geometrical problem. But eventually he paved the way for a new field of mathematics, today called graph theory, by generalizing the principle. His first insight was that every land mass can be represented by a single point on a piece of paper and the bridges can be drawn as line segments connecting these points. Today we call this a graph. We call the dots vertices and the lines we call edges. Euler found that it was crucial to think about how many edges enter a vertex. For the vertices 1, 3 und 4 this number (we call it today the degree of the vertex) is equal to three, for vertex 2 we have deg(2) = 5. Think, think, think, ... 😁

Graph theory has become important not only in transportation, communication, traffic and operations research but also in many other fields. In recent decades it became an issue in mathematical computer science - the study of data structures and information flow.

download PDF: BASIC CONCEPTS OF GRAPH THEORY
See also: Carl Leonhard Gottlieb Ehler