Задача о кёнигсбергских мостах
Как прогулка по семи мостам Кёнигсберга превратилась в первую теорему теории графов — и почему пройти их все по одному разу нельзя
В центре Кёнигсберга — нынешнего Калининграда — на реке Прегель два острова, соединённые с берегами и между собой семью мостами. Горожане развлекались задачей: можно ли прогуляться по городу, пройдя по каждому мосту ровно один раз? Никому не удавалось. В 1736 году Леонард Эйлер доказал, что это невозможно. Он заметил, что важны не улицы и не расстояния, а только то, какие участки суши соединены мостами, — и превратил карту в схему из точек и линий. Так родилась теория графов. Секрет оказался в чётности: на каждый участок суши вело нечётное число мостов.
Город на островах
В центре Кёнигсберга (ныне Калининград) на реке Прегель (ныне Преголя) лежат два острова — Кнайпхоф (сегодня остров Иммануила Канта) и Ломзе (Октябрьский остров). С берегами — Альтштадтом и Форштадтом — и друг с другом их соединяли семь мостов[1][2].
Мосты строили больше двух с половиной веков: первый — в 1286 году, седьмой, соединивший оба острова, — в 1542-м[1]. Если нарисовать схему первых четырёх мостов, их можно было обойти по одному разу и вернуться домой — и горожане так и гуляли. Но с появлением всех семи мостов это стало невозможно [1].
Городская головоломка
Жители Кёнигсберга играли в своеобразную игру: как пройти по всем мостам, ни по одному не пройдя дважды [1]. «Как я слышал, — писал Эйлер, — некоторые отрицают, что это можно сделать…»[1]
Карта превращается в граф
За задачу взялся великий математик Леонард Эйлер. Он заметил главное: неважно, как именно человек идёт по острову или по берегу, какой длины мосты и где они стоят. Важна только последовательность мостов [2].
Значит, можно выбросить всё лишнее. Каждый участок суши Эйлер заменил точкой, а каждый мост — линией между точками. Сегодня такую схему называют графом: точки — его вершины, линии — рёбра[2].
Секрет — в чётности
Дальше Эйлер рассуждал так. Если ты пришёл на участок суши по мосту, то уйти с него тоже должен по мосту. Значит, мосты, ведущие на каждый «промежуточный» участок, разбиваются на пары «пришёл — ушёл», и их число должно быть чётным. Нечётное число мостов может быть только у участка, где маршрут начинается, и у участка, где он заканчивается[2].
Отсюда правило: пройти по всем рёбрам графа ровно по одному разу можно, только если нечётных вершин нет совсем или их ровно две[2].
А в Кёнигсберге[1]:
| Участок | Сколько мостов |
|---|---|
| остров Кнайпхоф | 5 |
| Альтштадт | 3 |
| Форштадт | 3 |
| остров Ломзе | 3 |
Все четыре — нечётные. Значит, такого маршрута нет.
Маршрут, проходящий по каждому ребру графа ровно один раз, в честь Эйлера называют эйлеровым путём. Если он ещё и возвращается в начальную точку — эйлеровым циклом. Такой цикл возможен, только когда у всех вершин чётное число рёбер[2].
Рождение новой математики
Эйлер представил решение Петербургской академии наук 26 августа 1735 года, а опубликовал в 1741-м [2][1]. Его решение считают первой теоремой теории графов[2].
Задача оказалась важна и для топологии — науки о свойствах фигур, которые не меняются, если фигуру растягивать и сгибать. Эйлер понял, что важна не точная форма города, а только то, что с чем соединено[2]. О другом удивительном объекте топологии — в статье «Лента Мёбиуса».
Мосты сегодня
Два из семи мостов Эйлера погибли при бомбардировках Кёнигсберга во время Второй мировой войны, ещё два позже снесли и заменили автомагистралью. Сейчас на тех же местах стоят пять мостов, и лишь два из них сохранились со времён Эйлера[2].
Частые вопросы
Можно ли пройти по всем семи мостам Кёнигсберга по одному разу?
Нет. Эйлер доказал, что для такого маршрута не больше двух участков суши могут иметь нечётное число мостов: туда, откуда начинаешь, и туда, где заканчиваешь. А в Кёнигсберге к каждому из четырёх участков вело нечётное число мостов.
Что такое граф в математике?
Схема из точек (вершин) и соединяющих их линий (рёбер). В задаче о мостах вершины — это участки суши, а рёбра — мосты. Эйлер показал, что для ответа неважно, где именно стоят мосты и какой они длины, важно только, что с чем они соединяют.
Остались ли мосты Эйлера в Калининграде?
Частично. Два моста погибли при бомбардировках во время Второй мировой войны, ещё два снесли и заменили автомагистралью. Сейчас на тех же местах стоят пять мостов, и только два из них сохранились со времён Эйлера.
Источники
- Википедия. Задача о семи кёнигсбергских мостах, ru.wikipedia.org. ru.wikipedia.org
- Wikipedia. Seven Bridges of Königsberg, en.wikipedia.org. en.wikipedia.org
Обсуждение
Комментариев пока нет — начните обсуждение первым.
Чтобы написать комментарий или ответить, войдите на сайт: