Translate

The problem of the bridges of Königsberg

Jonathan
In the eighteenth century there were in the city of Königsberg (located in the former Prussia, now Kaliningrad, part of Russia) seven bridges connecting each of the banks of the river Pergel with two inner islands. The citizens were very proud of their bridges and joked about the possibility to visit all of them passing once for each.
Is this possible?


Solution:

Euler's solution to the problem of the Königsberg bridges involved the observation that when a vertex is "visited" in the middle of the process of tracing a graph, there must be an edge coming into the vertex, and another edge leaving it; and so the order of the vertex must be an even number.  This must be true for all but at most two of the vertices--the one you start at, and the one you end at, and so a connected graph is traversible if and only if it has at most two vertices of odd order. Now a quick look at the graph above shows that there are more than two vertices of odd order, and so the graph cannot be traced; that is the desired walking tour of Königsberg is impossible.



Category: , , , 1 comentarios
Suscribirse a: Comentarios (Atom)