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

Задача о кёнигсбергских мостах — это классическая математическая задача, которая положила начало теории графов. Она заключается в поиске маршрута, который проходит по всем семи мостам города Кёнигсберг (ныне Калининград) ровно по одному разу и возвращается в исходную точку. Задача была решена в 1736 году математиком Леонардом Эйлером, который доказал, что такой маршрут невозможен, и сформулировал общие критерии существования подобных путей.

¶История

¶Предыстория

В XVIII веке Кёнигсберг (столица Восточной Пруссии, ныне Калининград, Россия) располагался на берегах реки Прегель (ныне Преголя). Город включал четыре основные части: два больших острова — Кнайпхоф (ныне остров Канта) и Ломзе (ныне Октябрьский остров), а также два берега реки. Эти части соединялись семью мостами: Лавочный, Зелёный, Рабочий, Кузнечный, Дровяной, Высокий и Медовый. Жители города часто задавались вопросом: можно ли пройти по всем семи мостам, не проходя ни по одному из них дважды, и вернуться в исходную точку.

¶Решение Эйлера

В 1736 году Леонард Эйлер, швейцарский, немецкий и российский математик, работавший в Петербургской академии наук, заинтересовался этой задачей. Он опубликовал статью «Solutio problematis ad geometriam situs pertinentis» («Решение задачи, относящейся к геометрии положения»), в которой доказал, что требуемый маршрут невозможен. Эйлер абстрагировал реальную карту города, представив мосты как рёбра, а участки суши (берега и острова) — как вершины графа. Он показал, что для существования замкнутого маршрута, проходящего по каждому ребру ровно один раз (эйлерова цикла), необходимо, чтобы каждая вершина имела чётную степень (количество инцидентных ей рёбер). В случае Кёнигсберга все четыре вершины имели нечётные степени (3, 3, 3 и 5), что делало такой маршрут невозможным.

¶Значение для теории графов

Работа Эйлера считается первой публикацией по теории графов — разделу математики, изучающему структуры, состоящие из вершин и соединяющих их рёбер. Задача о кёнигсбергских мостах стала основой для понятий «эйлеров путь» и «эйлеров цикл», которые находят применение в логистике, компьютерных сетях, биоинформатике и других областях.

¶Математическая формулировка

¶Абстракция задачи

Эйлер предложил рассматривать не реальную карту, а граф, в котором:

вершины (узлы) — это участки суши: два берега (A и B) и два острова (C и D);
рёбра (линии) — это мосты, соединяющие эти участки.

Граф Кёнигсберга содержит 4 вершины и 7 рёбер. Степени вершин (количество рёбер, выходящих из каждой):

Вершина A (берег) — 3 моста;
Вершина B (берег) — 3 моста;
Вершина C (остров Кнайпхоф) — 5 мостов;
Вершина D (остров Ломзе) — 3 моста.

Все четыре вершины имеют нечётную степень.

¶Критерии Эйлера

Эйлер сформулировал два ключевых условия:

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

В случае Кёнигсберга все четыре вершины нечётные, что не удовлетворяет ни одному из условий. Следовательно, пройти все мосты ровно по одному разу невозможно ни с возвратом, ни без него.

¶Современное состояние

¶Изменение количества мостов

К XIX веку в Кёнигсберге были построены дополнительные мосты, что изменило степени вершин. Например, после строительства Железнодорожного моста (1865) и других переправ граф стал удовлетворять условиям эйлерова пути или цикла. Однако историческая задача рассматривает именно исходную конфигурацию семи мостов.

¶Калининград сегодня

В ходе Второй мировой войны (1945) многие мосты Кёнигсберга были разрушены. После перехода города в состав СССР (1946, переименован в Калининград) часть мостов была восстановлена, но конфигурация изменилась. В настоящее время в Калининграде насчитывается около 30 мостов, и задача о семи мостах утратила практическую актуальность. Однако на острове Канта (бывший Кнайпхоф) установлен памятный знак, посвящённый задаче Эйлера.

¶Применение в науке и технике

¶Теория графов

Задача о кёнигсбергских мостах является введением в теорию графов. Она используется в учебных курсах для демонстрации абстрактного мышления и перехода от реальных объектов к математическим моделям.

¶Логистика и транспорт

Понятия эйлерова пути и цикла применяются для оптимизации маршрутов: например, при планировании работы снегоуборочной техники, почтовых доставок, инспекции дорог или прокладки кабелей. В таких задачах требуется пройти по всем рёбрам графа (улицам, линиям) с минимальным количеством повторов.

¶Компьютерные науки

В информатике эйлеровы циклы используются в алгоритмах для проверки связности сетей, проектирования печатных плат, анализа последовательностей ДНК (сборка генома) и в криптографии.

¶Интересные факты

Задача о кёнигсбергских мостах считается одной из первых задач, решённых с помощью графов, и датой рождения теории графов часто называют 1736 год.
Эйлер не только доказал невозможность маршрута, но и показал, что если бы в Кёнигсберге было ровно два острова с нечётными степенями, то маршрут существовал бы, но не был бы замкнутым.
В честь задачи назван «Эйлеров путь» — маршрут, проходящий по всем рёбрам графа ровно один раз.
В 2005 году в Калининграде был установлен памятник задаче о семи мостах — скульптурная композиция, изображающая граф.

¶Критика и альтернативные интерпретации

Некоторые историки математики отмечают, что Эйлер не использовал термин «граф» (он появился позже, в XIX веке), а говорил о «геометрии положения» (geometria situs). Кроме того, в оригинальной статье Эйлер рассматривал не только семь мостов, но и обобщённую задачу для произвольного числа мостов и островов. Критики также указывают, что задача была известна жителям Кёнигсберга задолго до Эйлера, но именно он дал строгое математическое доказательство.

¶Источники

Эйлер Л. «Solutio problematis ad geometriam situs pertinentis» (1736).
Большая советская энциклопедия, статья «Графов теория».
Харари Ф. «Теория графов» (перевод с английского, 1973).
Калининградский областной историко-художественный музей: материалы по истории города.
Оре О. «Теория графов» (1962).