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

Издавна жителей Кёнигсберга (Калининград) интересовала загадка: как пройти по всем 7 мостам через реку Преголя, не проходя ни по одному из них дважды. Многие пытались решить эту задачу - теоретически или практически, во время прогулки. Однако, найти такой маршрут или доказать невозможность его существования никто не мог.

В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера, математика, члена Петербургской академии наук. Из его письма итальянскому математику и инженеру Мариони, написанного 13 марта 1736 года, мы знаем, что Эйлер смог найти решение задачи. Он сформулировал правила, пользуясь которыми легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

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

В истории математики решение Эйлера считается первой теоремой теории графов. Теория графов нашла очень широкое применение в транспортных и коммуникационных системах, - для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете.