AS PONTES DE KÖNIGSBERG (E OS CAMINHOS EULERIANOS)

Os moradores de Königsberg (hoje Kaliningrad, cidade da 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! Quando esse problema tem solução?

Um mapa de metrô é um grafo.

Fonte: MIT OpenCourseWare