Семь мостов Кенигсберга

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

Вы уже догадались, о чем идет речь? Конечно же, это граф Кенигсбергских мостов!

Семь мостов Кенигсберга - старинная математическая задача, решение которой Леонардом Эйлером в 1736 фактически ознаменовало собой начало новой эры в истории математики.

Прусский город Кенигсберг (ныне - Калининград, Российская Федерация) раскинулся на берегах реки Прегель, рукава которой разделяли город на четыре района - Кнайпхоф, Ломзе, Альтштадт и Форштадт - соединенные семью мостами.

Мосты Кенигсберга носили следующие названия: Кузнечный (Schmiedebrücke), Рабочий (Koettelbrucke), Зеленый (Grüne Brücke), Лавочный (Krämerbrücke), Деревянный (Holzbrücke), Высокий (Hohe Brücke) и Медовый (Honigbrücke).

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

К счастью для них, слухи о кенигсбергской головоломке достигли Санкт-Петербурга и привлекли внимание выдающегося математика Леонарда Эйлера. В письме к итальянскому математику и инженеру Джованни Маринони Эйлер писал, что задача, хотя и незатейлива, но представляет определенный интерес.

Предложенное Эйлером решение задачи о Кенигсбергских мостах было представлено вниманию членов Петербургской Академии наук 26 августа 1736 и опубликовано в научном журнале Академии (Commentarii academiae scientiarum Petropolitanae) в 1741 под заголовком Solutio problematis ad geometriam situs pertinentis. 

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

В ходе рассуждений Эйлер пришел к следующим выводам:

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

Граф Кенигсбергских мостов имеет четыре нечетные вершины (то есть все). Следовательно, невозможно обойти весь город, воспользовавшись каждым из мостов лишь единожды. Помимо разрешения стародавнего спора, труд Леонарда Эйлера положил начало новому разделу математики - теории графов, а также предвосхитил появление новой математической дисциплины - топологии.