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

Как задача о семи мостах Кёнигсберга изменила математику — Дан Ван дер Вирен

Переводчик: Ростислав Голод Редактор: Anna Kotova

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

Найти Кёнигсберг на современных картах вряд ли получится,

but one particular quirk in its geography

но именно одна его картографическая особенность

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

сделала город одним из самых известных в математике.

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

Средневековый город располагался на обоих берегах реки Прегель.

At the center were two large islands.

В центре города было два больших острова.

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

Оба острова друг с другом и с берегами соединяли

by seven bridges.

семь мостов.

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

Карлу Готтлибу Элеру, математику, ставшему впоследствии главой близлежащего города,

grew obsessed with these islands and bridges.

всё не давали покоя эти острова и их мосты.

He kept coming back to a single question:

Он всё больше задавался вопросом:

Which route would allow someone to cross all seven bridges

«Каким путём можно пройти все семь мостов,

without crossing any of them more than once?

но ни по одному из них не пройти дважды?»

Think about it for a moment.

Подумайте несколько секунд.

7

[7]

6

[6]

5

[5]

4

[4]

3

[3]

2

[2]

1

[1]

Give up?

Сдаётесь?

You should.

Наверное, сдаётесь.

It's not possible.

Да, это невозможно.

But attempting to explain why led famous mathematician Leonhard Euler

Однако в попытке объяснить почему, знаменитый математик Леонард Эйлер

to invent a new field of mathematics.

изобрёл новое направление в математике.

Carl wrote to Euler for help with the problem.

Карл написал Эйлеру письмо и попросил помочь с задачей.

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

Эйлер вначале посчитал, что вопрос никак не связан с математикой.

But the more he wrestled with it,

Но чем дольше он думал над решением,

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

тем больше ему начинало казаться, что что-то тут не так.

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

Он нашёл ответ, который лежит в плоскости геометрии,

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

в ту пору ещё не существовавшей, которую он назвал позиционной геометрией

now known as Graph Theory.

и которая сейчас известна под названием теории графов.

Euler's first insight

Первая мысль, осенившая Эйлера,

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

была о том, что маршрут от входа на остров или перехода на берег и до выхода оттуда

didn't actually matter.

не имеет никакого значения.

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

Поэтому карту можно упрощённо изобразить как совокупность четырёх частей города,

represented as a single point,

каждая из которых представляет собой точку,

what we now call a node,

которую мы сейчас называем вершиной,

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

с линиями, или рёбрами, между ними, представленными мостами.

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

Упрощённый граф позволяет нам легко сосчитать рёбра каждой вершины.

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

Это число мостов, которые соединяют эту часть города.

Why do the degrees matter?

Но зачем нам рёбра?

Well, according to the rules of the challenge,

В соответствии с правилами задачи,

once travelers arrive onto a landmass by one bridge,

если путешественники попадают в эту часть города по одному мосту,

they would have to leave it via a different bridge.

им надо выйти из неё через другой мост.

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

То есть мосты, ведущие к вершине и от неё по любому маршруту,

must occur in distinct pairs,

должны сочетаться в различных парах,

meaning that the number of bridges touching each landmass visited

это означает, что число мостов, соединяющих каждую из частей города,

must be even.

должно быть чётным.

The only possible exceptions would be the locations of the beginning

Единственными исключениями могут быть точки начала

and end of the walk.

и конца маршрута.

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

На нашем графе мы видим на четырёх вершинах нечётное число ребёр.

So no matter which path is chosen,

Поэтому неважно, какой выбран путь,

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

в определённой точке какой-то мост придётся пересекать дважды.

Euler used this proof to formulate a general theory

Эйлер использовал это доказательство, чтобы сформулировать общую теорию,

that applies to all graphs with two or more nodes.

которая относится ко всем графам с двумя и более вершинами.

A Eulerian path that visits each edge only once

Путь Эйлера, двигаясь по которому можно пройти по мостам только один раз,

is only possible in one of two scenarios.

возможен в одном из двух случаев.

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

Первый: когда есть ровно две вершины, имеющие нечётное число рёбер,

meaning all the rest are even.

а остальные должны иметь чётное число рёбер.

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

В данном случае начинать двигаться надо с одной из нечётных вершин,

and the end point is the other.

а заканчивать — на второй вершине.

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

Второй случай — это когда все вершины имеют чётное число рёбер.

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

В таком случае путь Эйлера начнётся и закончится в одной точке,

which also makes it something called a Eulerian circuit.

этот случай принято называть Эйлеровым циклом.

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

Так как же создать Эйлеров путь в Кёнингсберге?

It's simple.

Очень просто.

Just remove any one bridge.

Надо просто убрать один из мостов.

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

И, похоже, история сама создала свой собственный Эйлеров путь.

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

Во время Второй мировой войны советские ВВС уничтожили два моста,

making a Eulerian path easily possible.

и путь Эйлера стал вполне возможен.

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

Хотя, по правде говоря, в планы лётчиков решение задачи не входило.

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

В результате бомбардировок Кёнигсберг был почти стёрт с лица земли,

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

а затем город отстроили заново и назвали советским Калининградом.

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

И хотя Кёнигсберга и его семи мостов больше не существует,

they will be remembered throughout history by the seemingly trivial riddle

он вошёл в историю благодаря задаче, которая только кажется простой,

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

но именно её решение привело к появлению новой области математики.