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

Comment les ponts de Königsberg ont changé les mathématiques - Dan Van der Vieren

Traducteur: Joanna Luce-Veronique Relecteur: Elisabeth Buffard

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

Vous aurez beaucoup de mal à trouver Königsberg sur une carte moderne

mais une particularité géographique

but one particular quirk in its geography

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

a fait d'elle l'une des villes les plus célèbres des mathématiques.

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

Cette ville médiévale allemande était traversée par la rivière Pregel.

At the center were two large islands.

En son centre, il y avait deux grandes îles.

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

Ces deux îles étaient reliées entre elles et aux berges

by seven bridges.

par sept ponts.

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

Carl Gottlieb Ehler, un mathématicien devenu ensuite maire d'une ville proche,

grew obsessed with these islands and bridges.

en fit son idée fixe.

He kept coming back to a single question:

Il en revenait toujours à la même question :

Which route would allow someone to cross all seven bridges

quel trajet permettrait à quelqu'un de traverser l'ensemble des sept ponts

without crossing any of them more than once?

en ne les franchissant chacun qu'une seule fois ?

Think about it for a moment.

Réfléchissez-y un instant.

7

7

6

6

5

5

4

4

3

3

2

2

1

1

Give up?

Vous jetez l'éponge ?

You should.

Vous devriez.

It's not possible.

C'est impossible.

But attempting to explain why led famous mathematician Leonhard Euler

En tentant d'expliquer pourquoi, le célèbre mathématicien Leonhard Euler

to invent a new field of mathematics.

inventa une nouvelle branche des mathématiques.

Carl wrote to Euler for help with the problem.

Carl écrivit à Euler pour lui demander son aide.

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

Dans un premier temps,

Euler écarta le problème, qui ne concernait pas les maths.

But the more he wrestled with it,

Mais plus il s'interrogeait,

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

plus il lui semblait que finalement, il y avait là quelquechose.

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

Il trouva la réponse grâce à une branche de la géométrie

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

qui n'existait pas encore et qu'il nomma Géométrie de position,

now known as Graph Theory.

désormais connue comme la Théorie des graphes.

Euler's first insight

La première idée d'Euler

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

était que le trajet emprunté pour entrer sur une île ou une berge et la quitter

didn't actually matter.

n'avait pas vraiment d'importance.

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

Donc, la carte pouvait être simplifiée en représentant les quatre zones de terre

represented as a single point,

what we now call a node,

que nous appellerons nœud,

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

reliés par des lignes ou des arcs représentant les ponts.

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

Ce graphe simplifié nous permet de compter facilement les degrés de chaque nœud.

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

C'est-à-dire le nombre de ponts partant de chaque rive.

Pourquoi les degrés sont-ils importants ?

Why do the degrees matter?

Well, according to the rules of the challenge,

Selon les règles du défi,

once travelers arrive onto a landmass by one bridge,

une fois arrivé sur la terre par un pont,

they would have to leave it via a different bridge.

le voyageur doit en repartir par un autre pont.

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

Autrement dit, les ponts menant d'un nœud à un autre

must occur in distinct pairs,

doivent, pour chaque parcours, aller par paire,

meaning that the number of bridges touching each landmass visited

ce qui signifie que le nombre de ponts menant aux différentes berges visitées

must be even.

doit être pair.

The only possible exceptions would be the locations of the beginning

Les seules exceptions possibles seraient le point de départ

and end of the walk.

et d'arrivée du trajet.

Sur le graphe, on voit que les quatre nœuds ont un degré impair.

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

So no matter which path is chosen,

Du coup, peu importe le trajet choisi,

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

à un moment ou à un autre, l'un des ponts devra être traversé deux fois.

Euler used this proof to formulate a general theory

Euler mit cette preuve à profit pour formuler une théorie générale

that applies to all graphs with two or more nodes.

s'appliquant à tous les graphes comportant au moins deux nœuds.

A Eulerian path that visits each edge only once

Un chemin eulérien ne passant qu'une fois par chaque sommet

is only possible in one of two scenarios.

n'est possible que dans un cas sur deux.

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

Dans le premier, il y a exactement deux nœuds de degré impair,

meaning all the rest are even.

tous les autres étant donc pairs.

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

Dans ce cas là, le point de départ est l'un des nœuds impairs

and the end point is the other.

et l'autre, le point d'arrivée.

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

Dans le deuxième cas, tous les nœuds sont de degré pair.

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

Le chemin eulérien commence et s'achève alors au même point ;

de fait, on le nomme également cycle eulérien.

which also makes it something called a Eulerian circuit.

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

Du coup, comment créer un chemin eulérien à Königsberg ?

It's simple.

C'est simple.

Just remove any one bridge.

Il suffit de supprimer l'un des ponts.

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

Et il s'avère que l'Histoire en a elle-même créé un.

Pendant la seconde guerre mondiale, les forces aériennes soviétiques

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

ont détruit deux des ponts de la ville, ouvrant la voie à un chemin eulérien.

making a Eulerian path easily possible.

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

Mais, pour être honnête, ce n'était sans doute pas intentionnel.

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

Ces bombardement ont pratiquement rayé Königsberg de la carte.

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

Elle fut ensuite reconstruite pour devenir la ville russe de Kaliningrad.

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

Königsberg et ses sept ponts ne sont peut-être plus aujourd'hui,

they will be remembered throughout history by the seemingly trivial riddle

mais ils resteront dans l'Histoire comme l'énigme en apparence triviale

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

à l'origine d'une branche complètement nouvelle des mathématiques.