AS PONTES DE KÖNIGSBERG

Os moradores de Königsberg (hoje Kaliningrad, na Rússia) se perguntavam se era possível fazer um passeio pela cidade passando exatamente uma vez em cada uma das suas (à época) sete pontes.
Leonard Euler, um grande matemático suíço, deu uma solução elegante e simples para a questão. Para tanto, “traduziu” o problema para a linguagem de grafos. Este resultado, publicado em 1736, é considerado por muitos o primeiro artigo em Teoria dos Grafos. Você pode pensar em um grafo como um conjunto de pontos (vértices) ligados (ou não) por um ou mais traços (arestas).
Atualmente, esta teoria desperta grande interesse pelas inúmeras aplicações que possibilita: circuitos elétricos, circulação de mercadorias, transporte, administração de redes etc. Por exemplo, uma rede telefônica ou a internet podem ser tratadas como grafos.

Coloque quantas pontes quiser entre as regiões e tente, com o giz, traçar um caminho que passe por todas as pontes sem repetir nenhuma! Não é necessário voltar ao ponto inicial. Nem sempre esse problema tem solução. Do que isso depende?
Um mapa de metrô é um grafo.
Fonte: MIT OpenCourseWare.

O problema original das Pontes de Königsberg, ilustrado acima, não tem solução. Repare que, para que o caminho passe exatamente uma vez em cada ponte, as porções de terra onde o passeio se inicia e onde termina são as únicas que podem ter um número ímpar de pontes.

THE BRIDGES OF KÖNIGSBERG

The citizens of Königsberg (today Kaliningrad, Russia) wondered if it was possible to take a walk through the city passing exactly once on each of its (at the time) seven bridges.

Leonard Euler, a great Swiss mathematician, gave a simple and elegant solution to the matter. To do so, he "translated" the problem into the graph language. Many consider this result, published in 1736, the first paper in Graph Theory. A graph is a set of points (vertices) linked (or not) by one or more dashes (edges).

Currently, this theory arouses great interest for its many applications: electrical circuits, logistics, administration of networks, etc. For example, a telephone network or the internet can be treated as graphs.

Place as many bridges as you like connecting the regions and then try, with the chalk, to draw a path that goes through all the bridges without repeating any! There is no need to go back to the starting point. Not always does this problem have a solution. What does the existence of a solution depend on?

A subway map is a graph.

The original problem of the Konigsberg Bridges, illustrated above, has no solution. Note that for the path to pass exactly once on each bridge, the portions of land where the walk starts and ends are the only ones that can have an odd number of bridges.