Почему нечётные узлы решают задачу
В старом Кёнигсберге река Преголя разделяла город на четыре участка суши, соединённые семью мостами. Вопрос был не в том, какой маршрут короче: требовалось пройти по каждому мосту ровно один раз. Чтобы понять, возможно ли это, Леонард Эйлер заменил карту схемой: участки суши стали узлами, а мосты — линиями между ними.
В такой схеме важно не расстояние, а число линий, сходящихся в каждом узле. Если путешественник входит на участок по одному мосту, а затем уходит по другому, мосты образуют пару. Значит, у промежуточного узла должно быть чётное число мостов. Нечётными могут быть только два узла — начало и конец маршрута: в одном путешественник не будет входить, в другом — выходить.
Что показала схема Эйлера
У каждого из четырёх кёнигсбергских участков число примыкающих мостов было нечётным. Но маршрут с прохождением каждого моста по одному разу допускает не более двух таких узлов. Поэтому пройти все семь мостов без повторов нельзя — как бы ни выбирать путь.
Это доказательство сильнее перебора возможных маршрутов: оно показывает, что неудача заложена в самой структуре связей. Если бы один мост добавили или убрали, число мостов у некоторых участков изменилось бы, и условие можно было бы проверить заново.
От городской загадки к новому языку
Эйлер рассматривал не конкретную длину мостов и не форму улиц, а только то, что с чем соединено. Такой переход от карты к отношениям между объектами стал одним из истоков теории графов — раздела математики о сетях связей. Схема пригодилась не только для прогулок: тот же принцип помогает выяснять, можно ли пройти по всем линиям сети без повторов, будь то улицы, маршруты или соединения в иной системе.
