Pontes, grafos e uma brincadeira infantil

Euler (lê-se Óiler), matemático suíço e não o futebolista conhecido como o Filho do Vento, foi o pioneiro no estudo dos grafos. Eu já abordei grafos anteriormente, mas fazendo uma relação entre eles e o amor e não com pontes.

Pontes?

Sim, pontes.

O mapa acima retrata a cidade de Königsberg, na Prússia (atual Kaliningrado, na Rússia) na época de Euler. A questão que Euler se propôs a responder foi:

Será possível caminhar por todas as pontes de cidade, de modo que cada ponte seja percorrida uma e apenas uma vez?

Para facilitar a análise deste problema, o melhor é simplificá-lo um pouco. Em vez de analisarmos o mapa da cidade em si, vamos analisar um diagrama que o represente, mas que mantenha as mesmas características, isto é, o mesmo número de porções de terra e o mesmo número de pontes.

O diagrama acima pode ser simplificado ainda mais:

Percebam que os dois diagramas acima são isomorfos ao mapa da cidade. Apesar de diferentes do mapa original, eles preservam as principais características, que são o número de partes de terra (os vértices do grafo) e o número de pontes (as arestas do grafo).

O que Euler percebeu e que se transformou no primeiro teorema de teoria dos grafos é que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse no máximo dois pontos de onde saia um número ímpar de pontes. Isto se deve ao fato de cada porção de terra obrigatoriamente possuir um número par de pontes, pois é preciso um caminho para entrar e outro para sair. Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de uma ponte para entrar e outra para sair.

Mas e daí? O que isto tem de prático? Qual a aplicação dos grafos no dia-a-dia?

Placas de circuito impresso são uma das muitas aplicações. Num projeto de uma nova placa, basta encarar os componentes como vértices e os caminhos entre eles como arestas para descobrir se a proposta pode ser construída ou não.

Ok, mas e a brincadeira infantil, qualé? Vocês lembram de um desafio que consistia em três casas que deveriam receber, simultaneamente, águas, gás e eletricidade, de modo que os caminhos entre estes insumos não se cruzassem?

^{Água, gás, eletricidade}

Todo mundo deve ter um colega de aula cujo vizinho do primo conseguiu resolver este problema, mas a teoria dos grafos diz que é impossível, num plano, ligar os três vértices superiores aos três vértices inferiores, sem que pelo menos duas arestas se cruzem. Podem tentar resolver. Eu espero.

A demonstração deste fato não cabe aqui, mas é interessante notar que adultos adoram torturar crianças e deixá-las frustradas por um bom tempo. Embora o problema não tenha solução no plano, ele pode ser resolvido num toro (aka rosquinha). Na tela:

A solução neste caso é um tipo de truque: a aresta entre Y e B passa por baixo do toro, manobra impossível de ser realizada em um plano euclidiano.

Fontes:

• Euler
• Seven Bridges of Königsberg
• Água, gás e eletricidade
• Utility Graph