Foto: As sete pontes de Königsberg (fonte: Janela para a Rússia).
Como sete pontes deram origem à Teoria dos Grafos
Como sete pontes deram origem à Teoria dos Grafos
24 de outubro de 2026
Por Diogo da S. Ferreira
No século XVIII, a cidade de Königsberg (atual Kaliningrado, na Rússia) era cortada pelo rio Prególia, formando duas ilhas que, na época, eram conectadas às margens e entre si por sete pontes. Ali, vários moradores tentavam fazer um passeio pela região de modo a percorrer todas as sete pontes uma única vez, porém ninguém havia conseguido. Nesse contexto, surgiu uma pergunta entre os habitantes: seria possível fazer um passeio pela cidade de modo a passar uma única vez por todas as sete pontes?
Foto: Esquema das pontes e regiões (fonte: Super Interessante).
Essa questão, chamada de “Problema das pontes de Königsberg”, chegou ao conhecimento do matemático suíço Leonhard Euler, que em 1736 demonstrou que não era possível fazer um passeio que percorresse todas as sete pontes uma única vez. Para resolver o problema, o matemático fez uma simplificação representando as ilhas e as margens com um ponto e as pontes com uma linha que liga os pontos.
Essa questão, chamada de “Problema das pontes de Königsberg”, chegou ao conhecimento do matemático suíço Leonhard Euler, que em 1736 demonstrou que não era possível fazer um passeio que percorresse todas as sete pontes uma única vez. Para resolver o problema, o matemático fez uma simplificação representando as ilhas e as margens com um ponto e as pontes com uma linha que liga os pontos.
Euler percebeu que, ao entrar em uma região por uma ponte, precisamos sair dela por outra, desde que não seja o fim do percurso. Assim, para cada ponte de entrada em uma região que não seja o início nem o final, deve haver uma ponte de saída, totalizando um número par de pontes conectadas àquele lugar. Desse modo, para que o passeio exista, pode haver no máximo dois pontos (o começo e o fim do trajeto) com um número ímpar de linhas incidindo neles. Olhando para o esquema (Figura 2), vemos que há uma quantidade ímpar de linhas ligadas a cada um dos quatro pontos. Portanto, não existe um caminho que percorra cada ponte exatamente uma vez.
Euler percebeu que, ao entrar em uma região por uma ponte, precisamos sair dela por outra, desde que não seja o fim do percurso. Assim, para cada ponte de entrada em uma região que não seja o início nem o final, deve haver uma ponte de saída, totalizando um número par de pontes conectadas àquele lugar. Desse modo, para que o passeio exista, pode haver no máximo dois pontos (o começo e o fim do trajeto) com um número ímpar de linhas incidindo neles. Olhando para o esquema (Figura 2), vemos que há uma quantidade ímpar de linhas ligadas a cada um dos quatro pontos. Portanto, não existe um caminho que percorra cada ponte exatamente uma vez.
O artigo publicado por Euler com a solução deu origem a uma nova área da Matemática, que hoje é conhecida por Teoria dos Grafos. O objeto central desse campo, o grafo, é uma estrutura constituída de vértices (pontos) e arestas (ligações entre os pontos). No entanto, o nome “grafo” foi concebido apenas em 1878 pelo matemático britânico James Sylvester. Atualmente, esse estudo possui diversas aplicações em outras áreas, como na Ciência da Computação, na Engenharia Elétrica e nas redes de comunicação.
Foto: Exemplo de grafo (fonte: Wikipédia).
Na época de Euler, era impossível realizar o percurso. Entretanto, durante a Segunda Guerra Mundial, duas pontes foram bombardeadas, tornando possível realizar um caminho que passasse por todas as pontes restantes uma única vez.
Referências
ROSSINI, Maria Clara. O problema urbanístico que deu origem à teoria dos grafos. Super Interessante, 2023. Disponível em: <https://super.abril.com.br/historia/o-problema-urbanistico-que-deu-origem-a-teoria-dos-grafos/>. Acesso em: 13 out. 2026.
GÚZEVA, Aleksandra. As Sete Pontes de Königsberg: Você consegue resolver esse antigo enigma matemático?. Janela para a Rússia, 2025. Disponível em: <https://br.gw2ru.com/ciencia/235499-as-sete-pontes-de-konigsberg-voce-consegue-resolver-esseantigo-enigma-matematico>. Acesso em: 13 out. 2026.
TEORIA DOS GRAFOS. In: WIKIPÉDIA, a enciclopédia livre. Flórida: Wikimedia Foundation, 2026. Disponível em: <https://pt.wikipedia.org/w/index.php?title=Teoria_dos_grafos&oldid=73205136>. Acesso em: 14 out. 2026.
Figura 2: https://super.abril.com.br/historia/o-problema-urbanistico-que-deu-origem-a-teoria-dos-grafos
Page updated
Report abuse