Paulo Feofiloff, professor de Ciência da Computação do Instituto de Matemática da USP (Foto: Divulgação)No século 13, um enigma mobilizou uma pequena cidade localizada ao norte da Europa. Tratava-se do desafio das sete pontes de Königsberg, atual Kaliningrado. Seis delas interligavam duas ilhas às margens do Rio Pregel e uma que fazia a ligação entre as duas ilhas. O problema consistia na seguinte questão: como seria possível fazer um passeio a pé pela cidade de forma a se passar uma única vez por cada uma das sete pontes e retornar ao ponto de partida? Da resposta ao enigma surgiu a Teoria dos Grafos, criada em 1736 por Leonhard Euler.
Mas será que o problema de Königsberg teve solução? Buscando uma resposta, conversamos com Paulo Feofiloff, professor do Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo (IME / USP), que explicou os grafos e a sua aplicação prática nos dias de hoje. Doutor em Matemática Combinatória e Otimização pela Universidade de Waterloo, no Canadá, Feofiloff também é membro da Sociedade Brasileira de Computação.
As sete pontes de Könisberg (Foto: André Iunes)
Do que constava o problema das sete pontes de Königsberg?
- A história das pontes é de 300 anos atrás. Königsberg foi uma importante cidade da Prússia, localizada ao norte da Europa, próximo à costa do Mar Báltico, e que hoje é chamada de Kaliningrado. A cidade possuía duas ilhas cortadas pelo Rio Pregel e, na época, seis pontes as ligavam às margens e outra fazia a ligação das duas ilhas entre si. Por volta de 1735, os moradores de Königsberg se desafiaram com o seguinte problema: como seria possível fazer um passeio a pé pela cidade de forma a passar uma única vez por cada uma das sete pontes e retornar ao ponto de partida. Na época, foi o matemático Leonhard Euler quem decifrou o enigma, revelando ser impossível tal façanha.
Como Leonhard Euler resolveu essa questão?
- Pela matemática, ele provou por “A + B” que era impossível a solução desse problema. Na matemática, você tem que provar as coisas e foi isso que ele fez. O jeito que Euler adotou foi simples, mas interessante. Ele eliminou os detalhes geométricos do problema, como o comprimento das pontes, a sua forma, o tamanho das ilhas, ou seja, descartou tudo que era irrelevante ao problema, colocando foco somente no que importava. Sendo assim, ele acabou representando o problema por um grafo.
Grafo de Leonhard Euler (Foto: Divulgação)
Como era o grafo de Euler?
- Grafo é um conceito moderno, que não existia na época do Euler. Um grafo é algo muito simples, um desenho no qual temos alguns pontos e linhas ligando pares de pontos. No caso do problema das pontes, o grafo de Euler tinha quatro pontos: um representando uma das margens do rio e o outro a outra margem. Já o terceiro representava uma das ilhas e o quarto a outra ilha. Sendo assim, o grafo tinha quatro pontos e sete linhas, que representavam as pontes. O desafio era fazer um passeio pelo grafo que partisse de um dos quatro pontos, percorresse cada uma das sete linhas uma única vez e voltasse ao ponto de partida.
Como Euler raciocinou o problema?
- Euler raciocinou da seguinte maneira: ao atravessar cada ponto, são gastos exatamente duas linhas, uma para entrar no ponto e outra para sair. Para atravessar qualquer vértice, são gastas duas linhas, uma para entrar no vértice e outra para sair. Conclusão, cada vértice deve ter grau par de linhas. Acontece que o grafo das pontes de Königsberg tem pontos de grau ímpar e, portanto, o problema não pode ter solução.
Qual foi a importância da resolução desse problema para a matemática?
- O problema das pontes de Königsberg em si não tinha tanta relevância, mas já o raciocínio que Euler empregou teve sim muita importância para a resolução de outros problemas usando o mesmo tipo de lógica. Euler não só provou que o enigma das pontes não tinha solução, como deu um critério para verificar se qualquer outro problema semelhante tem solução, ou não. Ou seja, podemos utilizar a técnica dos grafos e aplicar em outra cidade, com um número diferente de pontes, com outras ligações, e adotar o mesmo raciocínio.
Como utilizar os grafos para a nossa realidade?
- A ideia de grafos serve de modelo para uma enorme quantidade de problemas práticos. Um deles tem a ver com o desafio enfrentado pelos carteiros. O carteiro parte da sede dos correios, percorre as ruas para fazer as entregas e volta ao seu posto de trabalho. Ele realiza um percurso diariamente para entregar as cartas e é preciso que ele repita, o mínimo possível, passar por uma rua mais de uma vez. Essa situação é um problema prático de certa importância, e que segue a mesma lógica dos grafos. Na coleta de lixo temos, praticamente, o mesmo problema. O caminhão tem que sair do depósito, percorrer o seu trajeto com o mínimo de repetição de ruas.
É preciso lembrar também que a internet é modelada por um grafo. Os pontos são os computadores e as linhas que os ligam são referentes aos links de fibra ótica. O grafo é uma ideia muito geral e útil, podendo ser usada para uma enorme quantidade de problemas práticos, seja na indústria, na informática, ou na engenharia. Lembrando que a palavra grafo, e o seu uso generalizado para a resolução de problemas, só surgiram a partir do final do século 19.
