Pontes de Königsberg: destruí-las é a solução

As “Sete Pontes de Königsberg” é um problema historicamente notável em matemática:

Na cidade de Königsberg temos uma curiosa região com 4 áreas de terra firme (uma acima, uma abaixo e duas no meio) conectadas por 7 pontes como apresentada na figura abaixo.

Eis a conjectura:

É possível partir de uma das 4 áreas de terra firme, passar pelas 7 pontes retornando para a área inicial.

Detalhes técnicos:

1. Não vale sair desta região do mapa;

2. Não vale atravessar uma mesma ponte mais do que uma vez;

3. É permitido cruzar o rio somente passando pelas pontes.

Pense um pouco neste problema antes de discutirmos a resolução. Lembre-se que conjecturas são afirmações que ainda não foram provadas nem como verdadeiras (no caso seriam teoremas) e nem como falsas (ou seja, refutada).

Agora que você já pensou um pouco sobre este problema, saiba que o grande matemático Leonhard Euler passou por este mesmo dilema em 1736. Como resultado de sua análise chegou a uma resolução que refuta esta conjectura (ou seja, passar pelas Sete Pontes de Königsberg e retornar à posição original é impossível). Para isto, Euler propôs o problema no seguinte modelo simplificado, no qual cada círculo representa uma área de terra firme e cada linha representa uma ponte.

Para entendermos o argumento de Euler, chamemos de vértice cada área de terra firme e de aresta cada ponte. Assim, na representação acima podemos perceber que todos os vértices estão conectados por um número ímpar de arestas. Isso significa que se houvesse solução, ela deveria partir de um vértice qualquer e passar pelas arestas que o conectam. Mas cada vez que ele passa por uma aresta conectada a este vértice, temos a seguinte situação:

1. Se estávamos no vértice, então saímos dele;

2. Se não estávamos no vértice, então entramos nele.

Como saímos de um vértice, temos que se o número de vezes que passamos por arestas conectadas ao vértice for ímpar, então terminaremos fora deste vértice. Por outro lado, se o número de vezes que passamos por arestas conectadas ao vértice for par, voltamos a este vértice.

Observe então que no problema proposto para as Pontes de Königsberg, todos os vértices possuem um número ímpar de arestas, e o problema pede que comece e termine no mesmo vértice. Desse modo, se passamos por todas as arestas, então passamos por uma quantidade ímpar de arestas conectadas àquele vértice, logo devemos estar fora do vértice. Com isto, temos demonstrado que não existe solução para este problema.

No caso, caminhos que viabilizam sair de um vértice, percorrer todas as arestas apenas uma vez cada e retornar para o vértice original, são chamados de grafos eulerianos. Um teorema que sucede desse conceito é o seguinte:

Um grafo será euleriano se ele for conexo e todos os seus vértices tiverem um número par de arestas conectadas a ele.

Podemos entender a razão de terem um número par de arestas, pois se passamos pelas arestas de um vértice um número par de vezes, e não começamos naquele vértice, então terminaremos fora daquele vértice.

Desse modo, para o famoso problema das “Sete Pontes de Königsberg” não achar uma solução é diferente de provar que ela não existe. Mas como ela forma um grafo que não é euleriano, então de fato sua solução não existe. Mas o que dizer de algumas variações mais caóticas? Se por acaso destruirmos uma ou mais pontes, teremos solução? A seguir analisaremos as variações do problema destruindo suas pontes (ignorando variações de simetria ou de permutação por vértices isolados).

6-A. Não tem solução, pois os vértices 2 e 3 possuem um número ímpar de arestas.

6-B. Não tem solução, pois os vértices 3 e 4 possuem um número ímpar de arestas.

6-C. Não tem solução, pois os vértices 1 e 3 possuem um número ímpar de arestas.

5-A. Não tem solução, pois todos os vértices possuem um número ímpar de arestas.

5-B. Não tem solução, pois os vértices 3 e 4 possuem um número ímpar de arestas.

5-C. Não tem solução, pois os vértices 2 e 4 possuem um número ímpar de arestas.

5-D. Não tem solução, pois os vértices 1 e 3 possuem um número ímpar de arestas.

5-E. Tem solução! Comece do vértice 1, vá para o vértice 4, depois para o vértice 3, depois para o vértice 2, depois para o vértice 4, volte para o vértice 1.

5-F. Não tem solução, pois os vértices 2 e 3 possuem um número ímpar de arestas.

5-G. Não tem solução, pois os vértices 2 e 4 possuem um número ímpar de arestas.

4-A. Não tem solução, pois os vértices 1 e 2 possuem um número ímpar de arestas.

4-B. Não tem solução, pois os vértices 1 e 4 possuem um número ímpar de arestas.

4-C. Não tem solução, pois os vértices 1 e 3 possuem um número ímpar de arestas.

4-D. Tem solução! Comece do vértice 1, vá para o vértice 2, depois para o vértice 3, depois para o vértice 4, volte para o vértice 1.

4-E. Não tem solução, pois os vértices 3 e 4 possuem um número ímpar de arestas.

4-F. Tem solução! Comece do vértice 1, vá para o vértice 4, depois para o vértice 3, depois para o vértice 4, volte para o vértice 1.

3-A. Não tem solução, pois todos os vértices possuem um número ímpar de arestas.

3-B. Não tem solução, pois o vértice 2 possui um número ímpar de arestas.

3-C. Não tem solução, pois os vértices 3 e 4 possuem um número ímpar de arestas.

3-D. Tem solução! Comece do vértice 1, vá para o vértice 2, depois para o vértice 4, volte para o vértice 1.

2-A. Tem solução! Comece do vértice 4, vá para o vértice 3, volte para o vértice 4.

2-B. Não tem solução, pois os vértices 1 e 3 possuem um número ímpar de arestas.

O caso com 1 ponte é desnecessário, pois se apenas existe uma aresta, haverá um vértice com um número ímpar de arestas (no caso, 1).

O caso com 0 pontes é trivial, pois se não há pontes para atravessar, já começamos no vértice que satisfaz o problema.

Com isto podemos concluir que destruindo de duas a cinco pontes (ou todas) o problema insolúvel pode suportar soluções, ou seja, eliminando algumas arestas específicas podemos transformar o grafo original em grafos eulerianos.

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *