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

Tradutor: Vinícius Pontes Revisor: Ruy Lopes Pereira

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

Seria difícil encontrar Königsberg em um mapa moderno,

but one particular quirk in its geography

mas uma particularidade em sua geografia

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

a tornou uma das mais famosas cidades da matemática.

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

A cidade medieval alemã ocupava as duas margens do rio Pregel.

At the center were two large islands.

No centro, ficavam duas grandes ilhas.

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

As conexões entre as duas ilhas e as margens do rio

by seven bridges.

se davam através de sete pontes.

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

Carl Gottlieb Ehler, um matemático que se tornaria prefeito numa cidade próxima,

grew obsessed with these islands and bridges.

ficou obcecado por essas ilhas e pontes.

He kept coming back to a single question:

Ele insistia em uma única questão:

Which route would allow someone to cross all seven bridges

qual caminho teria que ser feito para se cruzar as sete pontes

without crossing any of them more than once?

sem passar por uma ponte mais de uma vez?

Think about it for a moment.

Reflita por um momento.

7

[7]

6

[6]

5

[5]

4

[4]

3

[3]

2

[2]

1

[1]

Give up?

Desistiu?

You should.

Muito bem.

It's not possible.

É impossível.

But attempting to explain why led famous mathematician Leonhard Euler

Mas a tentativa de explicar o porquê levou o famoso matemático Leonhard Euler

to invent a new field of mathematics.

a inventar um novo campo da matemática.

Carl wrote to Euler for help with the problem.

Carl pediu a Euler ajuda com o problema.

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

Euler a princípio pensou que a questão não tinha relação com matemática.

But the more he wrestled with it,

Mas quanto mais ele pensava,

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

mais parecia haver algo ali no fim das contas.

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

A solução que ele 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, a qual ele nomeou "Geometria de Posição",

now known as Graph Theory.

conhecida hoje como Teoria dos Grafos.

Euler's first insight

Euler concluiu primeiro

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

que o caminho percorrido dentro de uma ilha ou margem específica

didn't actually matter.

não importava.

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

Assim, o mapa podia ser simplificado se cada porção de terra

represented as a single point,

fosse representada por um ponto,

what we now call a node,

o que nós hoje chamamos de vértice,

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

com linhas, ou arestas, entre eles representando as pontes.

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

Esse grafo simplificado nos permite contar os graus de cada vértice.

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

Esse é o número de pontes que cada porção de terra possui.

Why do the degrees matter?

Qual a importância dos graus?

Well, according to the rules of the challenge,

Segundo as regras do desafio,

once travelers arrive onto a landmass by one bridge,

quando viajantes entrarem numa porção de terra por uma ponte,

they would have to leave it via a different bridge.

eles têm que sair dela por outra ponte.

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

Ou seja, as pontes que chegam e que saem de cada vértice

must occur in distinct pairs,

devem ocorrer em pares,

meaning that the number of bridges touching each landmass visited

o que significa que o número de pontes em cada porção de terra visitada

must be even.

deve ser par.

The only possible exceptions would be the locations of the beginning

As únicas exceções seriam o começo

and end of the walk.

e o fim da caminhada.

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

Olhando para o grafo, fica evidente que todos os vértices têm grau ímpar.

So no matter which path is chosen,

Não importa o caminho escolhido,

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

em algum momento, uma ponte será cruzada duas vezes.

Euler used this proof to formulate a general theory

Euler usou essa prova para formular uma teoria geral

that applies to all graphs with two or more nodes.

que se aplica a todo grafo com dois ou mais vértices.

A Eulerian path that visits each edge only once

Um caminho euleriano que passa apenas uma vez por cada aresta

is only possible in one of two scenarios.

só é possível num dos seguintes cenários.

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

O primeiro é quando existem exatos dois vértices de grau ímpar,

meaning all the rest are even.

e todos os outros são pares.

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

Nesse caso, o ponto de partida é um dos vértices ímpares,

and the end point is the other.

e o final é o outro.

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

O segundo é quando todos os vértices têm grau par.

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

Nesse caso, o caminho inicia e termina no mesmo local,

which also makes it something called a Eulerian circuit.

configurando o que chamamos de circuito euleriano.

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

Então, como um caminho euleriano poderia ser criado em Königsberg?

It's simple.

É simples.

Just remove any one bridge.

É só remover uma das pontes.

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

Curiosamente, a história criou um caminho euleriano por conta própria.

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

Na 2ª Guerra Mundial, aviões soviéticos destruíram duas das pontes da cidade,

making a Eulerian path easily possible.

fazendo surgir um caminho euleriano.

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

Embora essa provavelmente não fosse sua intenção.

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

Os bombardeios praticamente varreram Königsberg do mapa,

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

e a cidade foi reconstruída pela Rússia sob o nome de Kaliningrado.

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

Mesmo que Königsberg e suas sete pontes não estejam mais entre nós,

they will be remembered throughout history by the seemingly trivial riddle

elas ficarão para sempre na história por causa desse simples enigma

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

que deu origem a um ramo da matemática inteiramente novo.