Укрощение бесконечности. История математики от первых чисел до теории хаоса

На первый взгляд задача о кенигсбергских мостах не имеет отношения к комбинаторике многогранников. Город Кенигсберг (ныне Калининград), некогда принадлежавший Пруссии, расположен по обоим берегам реки Преголя, на которой есть два острова. Те связаны с берегами и друг с другом семью мостами. Понятно, что жители Кенигсберга долго гадали, можно ли так проложить маршрут воскресной прогулки, чтобы только один раз пройти по каждому из мостов.

Задача о кенигсбергских мостах

Загадку в 1735 г. решил Эйлер; хотя правильнее будет сказать, он доказал, что здесь нет решения, и объяснил почему. Он использовал два важных приема: упростил задачу и сократил ее до самых элементарных требований, а затем обобщил ее, сравнив со всеми головоломками такого рода. Он указал, что для решения важны не размеры и форма островов, а то, как именно связаны между собой острова, берега и мосты. Всю проблему можно было изобразить простой схемой точек (вершин), соединенных линиями (ребрами), как это показано наложением на нашей карте.

Чтобы составить такую схему, мы расположим по одной вершине на каждом массиве суши: северный берег, южный берег и два острова. Соединим две вершины ребром всякий раз, когда есть мост, связывающий соответствующие фрагменты суши. Тогда мы получаем четыре вершины A, B, C

и D и семь ребер, по одному для каждого моста.

Теперь задачу можно заменить более простым эквивалентом на схеме. Возможно ли найти на ней маршрут – связанную последовательность ребер, чтобы он включал по одному разу каждое ребро?

Эйлер определил два типа маршрутов: открытый

, у которого начало и конец находятся в разных вершинах, и замкнутый, у которого начало и конец приходятся на одну вершину. Он доказал, что именно для этой схемы не существует маршрута ни одного из этих типов.

Ключом к загадке станет рассмотрение валентности каждой вершины: в данном случае это число сходящихся в ней ребер. Сперва рассмотрим вариант замкнутого маршрута. Здесь каждое ребро, приходящее к вершине, соединяется с другим – следующим, по которому маршрут покидает эту вершину. Если замкнутый маршрут возможен, количества ребер для каждой вершины должны, соответственно, быть четными. Иными словами, у всех вершин должна быть равная валентность. Но на схеме мы видим три вершины с валентностью 3 и одну с валентностью 5 – всё это нечетные числа. Значит, замкнутого маршрута не существует.

Те же критерии мы применяем к открытому маршруту, но здесь получится минимум две вершины с нечетной валентностью: одна в начале и другая в конце. Поскольку на схеме Кенигсберга есть четыре вершины с нечетной валентностью, открытого маршрута не существует.

Эйлер сделал еще один важный шаг – доказал, что эти необходимые условия для существования маршрута являются также достаточными при условии, что на диаграмме есть связь (т. е. две любые вершины связаны каким-либо путем). Это общее свойство доказать несколько труднее, и у Эйлера ушло некоторое время на поиски решения. Сейчас мы можем записать доказательство в нескольких строках.

Геометрические свойства плоских поверхностей

Два открытия Эйлера кажутся принадлежащими к весьма далеким друг от друга разделам математики, но при внимательном рассмотрении легко заметить общие для них детали. Они используют комбинаторику схем многогранников. Одно считает грани, ребра и вершины, а другое – валентности; одно выводит общие соотношения между тремя числами, другое ищет что-то общее в имеющихся маршрутах. Но они явно родственны по духу. И даже больше, причем эта особенность оставалась незамеченной на протяжении более чем столетия: оба являются инвариантами непрерывных преобразований. Само расположение вершин и ребер здесь не имеет значения: нам важно лишь то, как они связаны между собой. Обе проблемы покажутся одинаковыми, если мы нарисуем эту схему на резиновом листе, который потом деформируется. Единственный способ создать значимые различия – разрезать или разорвать этот лист и склеить потом его куски; но эта операция уничтожит саму непрерывность.