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

Fordító: Maria Ruzsane Cseresnyes Lektor: Péter Pallós

Hiába is keresnénk Königsberget egy mai térképen,

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

but one particular quirk in its geography

különös földrajzi helyzete folytán

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

mégis az egyik leghíresebb várossá vált a matematikában.

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

A középkori német város a Pregel folyó két partján terült el.

At the center were two large islands.

Közepén volt két nagy sziget.

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

A két szigetet egymással és a partokkal

by seven bridges.

hét híd kötötte össze.

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

Carl Gottlieb Ehler matematikus, egy közeli város későbbi polgármestere

grew obsessed with these islands and bridges.

e szigeteknek és hidaknak megszállottjává vált.

He kept coming back to a single question:

Folyton ugyanahhoz a kérdéshez kanyarodott vissza:

Which route would allow someone to cross all seven bridges

Melyik az az út, amely mentén átmehetünk minden hídon,

without crossing any of them more than once?

de mindegyiken csak egyszer?

Think about it for a moment.

Gondolkodjunk csak egy pillanatig.

7

7

6

6

5

5

4

4

3

3

2

2

1

1

Give up?

Feladják?

You should.

Fel kéne.

It's not possible.

Nincs ilyen.

But attempting to explain why led famous mathematician Leonhard Euler

Leonhard Euler, a neves matematikus, amikor megpróbálta ezt megmagyarázni,

to invent a new field of mathematics.

a matematika egy új területét hozta létre.

Carl wrote to Euler for help with the problem.

Carl írt Eulernek, hogy segítsen megoldani a problémát.

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

Euler először elhessentette a kérdést, mint aminek semmi köze a matematikához.

But the more he wrestled with it,

de minél többet nyűglődött rajta,

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

annál inkább úgy tűnt, hogy talán mégis lenne valami köze.

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

A válasz, amit talált, a geometriának olyan ágához köthető,

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

ami ekkor még nem igazán létezett, és amit ő a helyek geometriájának hívott,

now known as Graph Theory.

ma pedig gráfelmélet néven ismert.

Euler's first insight

Euler első meglátása az volt,

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

hogy nem számít, hogy a szigeteken és a partokon

didn't actually matter.

milyen úton megyünk.

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

Így a térkép leegyszerűsíthető oly módon, hogy a négy földdarabot

represented as a single point,

egy-egy pont reprezentálja –

what we now call a node,

ezeket csúcsoknak nevezzük –,

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

a hidakat pedig vonalaknak vagy éleknek, amelyek összekötik a pontokat.

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

E leegyszerűsített ábra lehetővé teszi, hogy megszámoljuk minden csúcs fokszámát.

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

Ez a szám az adott szárazföldet érintő hidak száma.

Why do the degrees matter?

Miért érdekes a fokszám?

Well, according to the rules of the challenge,

A séta szabályai szerint

once travelers arrive onto a landmass by one bridge,

ha egyszer az utazó megérkezik a szárazföldre az egyik hídon,

they would have to leave it via a different bridge.

akkor egy másikon keresztül kell onnan távoznia.

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

Vagyis az egy csúcsba be- és onnan kifutó hidak

must occur in distinct pairs,

egyértelműen megfeleltethetők egymásnak,

meaning that the number of bridges touching each landmass visited

ami azt jelenti, hogy minden földdarabot

must be even.

páros számú hídnak kell érintenie.

The only possible exceptions would be the locations of the beginning

Kivétel ez alól csak

and end of the walk.

a séta kezdő- és végpontja lehet.

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

Ha ránézünk a gráfra, rögtön látszik, hogy mind a négy csúcs fokszáma páratlan.

So no matter which path is chosen,

Bármelyik utat is választjuk tehát,

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

valamelyik pontnál az egyik hidat kétszer kell használjuk.

Euler used this proof to formulate a general theory

Euler ezt a bizonyítást használta egy általános tétel megfogalmazására,

that applies to all graphs with two or more nodes.

amely igaz minden olyan gráfra, amelynek legalább két csúcsa van.

A Eulerian path that visits each edge only once

Az Euler-vonal, amely minden élt csak egyszer használ,

is only possible in one of two scenarios.

csupán az alábbi két eset valamelyikében lehetséges:

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

Az első, amikor pontosan két olyan csúcs van, melyeknek a fokszáma páratlan,

meaning all the rest are even.

azaz az összes többié páros.

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

Ilyenkor a kezdőpont az egyik páratlan fokszámú csúcs,

and the end point is the other.

a végpont pedig a másik.

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

A másik eset, amikor minden csúcs fokszáma páros.

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

Ilyenkor az Euler-vonal kezdő- és végpontja megegyezik,

which also makes it something called a Eulerian circuit.

ezt Euler-körnek is nevezik.

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

Tehát hogyan tudnánk létrehozni egy Euler-vonalat Königsbergben?

It's simple.

Egyszerűen.

Just remove any one bridge.

Hagyjunk el egy hidat.

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

A történelem megcsinálta a maga Euler-vonalát.

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

A 2. világháború alatt a szovjet légierő a város két hídját megsemmisítette,

making a Eulerian path easily possible.

ezzel az Euler-vonalat könnyen megrajzolhatóvá tette.

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

Az igazsághoz tartozik, hogy valószínűleg nem ez volt a céljuk.

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

Ezek a bombák jócskán letörölték Königsberget a térképről.

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

hogy azután orosz városként épüljön újjá, Kalinyingrád néven.

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

Így, bár Königsberget és hét hídját már nem lehet körbejárni,

they will be remembered throughout history by the seemingly trivial riddle

mindenkorra emlékezetes marad e látszólag egyszerű rejtvény révén,

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

amely a matematika egy új ágának felbukkanásához vezetett.