Логическая задачка, которую 200 лет не могли решить именитые математики: как пройти по мостам старого Кенигсберга
Издавна среди жителей старого Кенигсберга была в ходу такая головоломка: как так исхитриться и пройти по всем городским мостам через реку Преголя, чтобы не пройти ни по одному из них дважды. Не один мозг был сломан в попытках решить эту задачу как теоретически, так и во время прогулок. Более того, доказать или опровергнуть возможность существования такого маршрута никто тоже не мог. Попробуйте сами, может вам удастся найти тот самый путь?
Так и жили бедные горожане без решения, пока в 1736 году талантливый во всех смыслах член Петербургской академии наук Леонард Эйлер, внесший существенный вклад в становление российской науки, научно обосновал невозможность решения этой задачи.
Итак, для начала нарисуем упрощенную схему города в виде математического графа. Его ребра у нас будут соответствовать мостам — их всего семь, — а частям города — вершины нашего графа. В процессе решения задачи Эйлер пришел к следующим выводам:
- Не существует такого графа, который имел бы нечетное число нечетных же вершин
- Если все вершины графа четные, то можно начертить его без отрыва карандаша от бумаги, при этом начало и конец могут быть в одной вершине
- Если две вершины графа нечетные, то этот граф можно начертить без отрыва карандаша от бумаги, но в таком случае начало будет в одной нечетной вершине, а конец — в другой
- У графа кенигсбергских мостов все вершины были нечетными, из чего следовало, что невозможно пройти по всем мостам, не проходя ни по одному из них дважды
Благодаря семи кенигсбергским мостам Эйлер изобрел математические циклы имени себя. Эйлеров цикл — это замкнутый путь, проходящий через каждое ребро графа ровно по одному разу. Согласно теореме, эйлеров цикл существует тогда и только тогда, когда граф связный (между любой парой вершин графа есть как минимум один путь) или будет являться связным, если удалить из него все изолированные вершины, и в нем отсутствуют вершины нечетной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечетной степени.
Но на этом история с семью кенигсбергскими мостами не заканчивается. Решение Эйлера было актуально на протяжении долгого времени, но в 1905 году все изменилось. Существует городская легенда, что на одном из светских приемов группа ученых решила подшутить над самим кайзером — императором Вильгельмом II. Тот пыхтел не один час в попытке решить головоломку, пока не включил императорскую смекалку. Так в Кенигсберге появился восьмой мост, который назвали, естественно, Императорским, а что стало с теми учеными-шутниками доподлинно не известно.
Увы, но восьмой мост был разрушен в ходе бомбардировки во время Второй мировой. На его опорах уже в 2005 году был построен Юбилейный мост, чье открытие приурочили к 750-летнему юбилею города.