How the Königsberg bridge problem changed mathematics - Dan Van der Vieren

Tradutor: Margarida Ferreira Revisora: António Ribeiro

You'd have a hard time finding Königsberg on any modern maps,

Terão muita dificuldade em encontrar Königsberg em qualquer mapa moderno,

but one particular quirk in its geography

mas uma certa peculiaridade na sua geografia

has made it one of the most famous cities in mathematics.

tornou-a numa das cidades mais famosas da matemática.

The medieval German city lay on both sides of the Pregel River.

A cidade medieval germânica situava-se de ambos os lados do Rio Pregel.

At the center were two large islands.

No centro havia duas grandes ilhas.

The two islands were connected to each other and to the river banks

As duas ilhas estavam ligadas uma à outra e às margens do rio

by seven bridges.

por sete pontes.

Carl Gottlieb Ehler, a mathematician who later became the mayor of a nearby town,

Carl Gottlieb Ehler, um matemático

que veio a ser o prefeito duma cidade vizinha,

grew obsessed with these islands and bridges.

começou a ficar obcecado com estas ilhas e pontes.

He kept coming back to a single question:

Voltava sempre a uma única pergunta:

Which route would allow someone to cross all seven bridges

Que caminho permitiria que uma pessoa atravessasse as sete pontes

without crossing any of them more than once?

sem cruzar nenhuma delas mais do que uma vez?

Think about it for a moment.

Pensem nisso por instantes.

7

6

5

4

3

2

1

Give up?

Desistem?

You should.

É melhor.

It's not possible.

Não é possível.

But attempting to explain why led famous mathematician Leonhard Euler

Mas a tentativa de explicar porquê,

levou Leonhard Euler, o conhecido matemático,

to invent a new field of mathematics.

a inventar uma nova área da matemática.

Carl wrote to Euler for help with the problem.

Carl escreveu a Euler, pedindo ajuda para o problema.

Euler first dismissed the question as having nothing to do with math.

A princípio, Euler achou que o problema não tinha nada a ver com a matemática.

But the more he wrestled with it,

Mas quanto mais pensava nisso,

the more it seemed there might be something there after all.

mais lhe parecia que, afinal, podia haver ali qualquer coisa.

The answer he came up with had to do with a type of geometry

A resposta que encontrou tinha a ver com um tipo de geometria

that did not quite exist yet, what he called the Geometry of Position,

que ainda não existia e a que ele chamou a Geometria de Posição,

now known as Graph Theory.

hoje conhecida por Teoria dos Grafos.

Euler's first insight

A primeira conclusão de Euler

was that the route taken between entering an island or a riverbank and leaving it

foi que o caminho tomado entre a entrada de uma ilha ou de uma margem do rio

didn't actually matter.

e a sua saída não era importante.

Thus, the map could be simplified with each of the four landmasses

Portanto, o mapa podia ser simplificado representando por um simples ponto

represented as a single point,

cada uma das quatro massas terrestres,

what we now call a node,

aquilo a que hoje chamamos um nodo.

with lines, or edges, between them to represent the bridges.

As pontes seriam representadas por linhas, ou arestas, entre elas.

And this simplified graph allows us to easily count the degrees of each node.

Este grafo simplificado permite-nos contar facilmente os graus de cada nodo.

That's the number of bridges each land mass touches.

É o número de pontes em que cada massa terrestre toca.

Porque é que estes graus são importantes?

Why do the degrees matter?

Well, according to the rules of the challenge,

Segundo as regras do problema,

once travelers arrive onto a landmass by one bridge,

quando os viajantes chegassem a uma massa terrestre por uma ponte,

they would have to leave it via a different bridge.

teriam que sair de lá por uma ponte diferente.

In other words, the bridges leading to and from each node on any route

Por outras palavras, as pontes que chegavam a um nodo

e as que dele saiam

must occur in distinct pairs,

tinham que ocorrer em pares distintos,

meaning that the number of bridges touching each landmass visited

ou seja, o número de pontes que tocavam em cada massa terrestre visitada

must be even.

teria que ser par.

The only possible exceptions would be the locations of the beginning

As únicas exceções possíveis seriam

a localização do início e a do fim da caminhada.

and end of the walk.

Looking at the graph, it becomes apparent that all four nodes have an odd degree.

Olhando para o grafo, verifica-se

que todos os quatro nodos têm um grau ímpar.

So no matter which path is chosen,

Assim, seja qual for o caminho escolhido,

at some point, a bridge will have to be crossed twice.

a certa altura, seria necessário cruzar duas vezes a mesma ponte.

Euler used this proof to formulate a general theory

Euler usou esta prova para formular uma teoria geral

that applies to all graphs with two or more nodes.

que se aplica a todos os grafos com dois ou mais nodos.

A Eulerian path that visits each edge only once

Um caminho euleriano que visita cada aresta apenas uma vez

is only possible in one of two scenarios.

só é possível num de dois cenários.

The first is when there are exactly two nodes of odd degree,

O primeiro é quando há exatamente dois nodos de grau ímpar,

meaning all the rest are even.

o que significa que todos os restantes são pares.

There, the starting point is one of the odd nodes,

Aí, o ponto de partida é um dos nodos ímpar

and the end point is the other.

e o ponto de chegada é o outro.

The second is when all the nodes are of even degree.

O segundo é quando todos os nodos são de grau par.

Then, the Eulerian path will start and stop in the same location,

Aí, o caminho euleriano pode começar e terminar no mesmo local

which also makes it something called a Eulerian circuit.

o que também lhe dá o nome de circuito euleriano.

So how might you create a Eulerian path in Königsberg?

Então, como podíamos criar um caminho euleriano em Konigsberg?

It's simple.

Muito simplesmente.

Just remove any one bridge.

Basta retirar qualquer uma das pontes.

And it turns out, history created a Eulerian path of its own.

Acontece que a História criou um caminho euleriano, por si mesma.

During World War II, the Soviet Air Force destroyed two of the city's bridges,

Durante a II Guerra Mundial,

a Força Aérea Soviética destruiu duas das pontes da cidade,

making a Eulerian path easily possible.

possibilitando um caminho euleriano.

Though, to be fair, that probably wasn't their intention.

Mas, para ser franco, provavelmente a intenção deles não era essa.

These bombings pretty much wiped Königsberg off the map,

Esse bombardeamento quase varreu Konigsberg do mapa

and it was later rebuilt as the Russian city of Kaliningrad.

que foi posteriormente reconstruída como a cidade russa de Kaliningrado.

So while Königsberg and her seven bridges may not be around anymore,

Embora Konigsberg e as suas sete pontes talvez já não existam,

they will be remembered throughout history by the seemingly trivial riddle

serão recordadas na História

por este quebra-cabeças aparentemente trivial

which led to the emergence of a whole new field of mathematics.

que levou ao aparecimento de toda uma nova área da matemática.