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

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

Как пройти по всем мостам, не проходя при этом ни по одному из них дважды?

Эта задача известна с давних времён, и это действительно так. Её название - "Семь мостов Кёнигсберга". Согласно легенде, жители Кёнигсберга задавались долгое время вопросом: как пройти по всем мостам города (через реку Преголя), при этом не проходя ни по одному мосту дважды? Многие люди пытались решить эту задачу как теоретически, так и практически, прогуливаясь по городу. Но решения долгое время не было: такой маршрут не находился, но и доказать, что его существовать не может, также никто не мог.

Впервые эту задачу решил в 1736 году великий математик Леонард Эйлер, которого она очень заинтересовала. Он нашёл простое правило, с помощью которого можно решить эту задачу и бесчисленное количество других задач, аналогичных этой. Действительно, можно придумать и другие задачи со сходными условиями, добавив или убавив количество островков и мостов.

Как Эйлер пришёл к решению задач такого типа? Он заметил, что в этой конкретной задаче есть четыре "области": два берега реки и два острова, соединённые между собой мостами. Для упрощения понимания задачи он предложил "области" заменить точками, а мосты - линиями. Визуально задача стала выглядеть проще. Теперь она состояла в следующем: как, не отрываясь от бумаги, провести карандашом по всем линиям и точкам, не проходя по одной и той же линии два раза?

Эйлер заметил, что все точки соединены друг с другом нечётным количеством линий. Нарисовав ещё несколько подобных рисунков, только с разным количеством точек и соединявших их линий, он довольно быстро нашёл несколько правил для решения: 1) количество нечётных точек (то есть точек, которые соединяются с другими точками нечётным количеством линий), всегда будет чётное количество, т. е. 0, 2, 4, 6, и т. д.; 2) если все точки чётные (то есть соединяются друг с другом чётным количеством линий), а следовательно, нечётных точек - 0, то, чтобы соблюсти условие задачи, начните движение из любой точки и, пройдя все линии, Вы вернётесь в исходную точку; 3) если нечётных точек две, то начинать движение нужно в одной из них и закончить во второй; 4) если нечётных точек больше двух, то решения у данной конкретной задачи нет. Вот так всё просто оказалось! Следовательно, задача о семи мостах Кёнигсберга не имеет решения, так как нечётных точек четыре, что больше двух.