Сегодня мы поговорим об одной замечательной старинной задаче, которая имеет простое, но в то же время красивое решение.
Издавна среди жителей Кёнигсберга (нынче - Калининград) была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году за эту задачу взялся великий Леонард Эйлер. Кто бы сомневался в том, что он её решит! Довольно быстро Эйлер смог доказать, что обойти город требуемым образом невозможно.
Давайте же разбираться, как же Эйлер разрешил эту головоломку!
Для наглядности упростим схему города. Приведённая ниже картинка называется граф. В данном случае вершинами графа являются части города, на которые разбит город семью мостами (их ровно 4), а рёбрами - сами мосты.
Степенью вершины называется количество рёбер, из неё выходящих (например, степень левой вершины равна 5, степень остальных - 3). Вершину назовём чётной/нечётной, если её степень чётная/нечётная.
Давайте докажем от противного, что обойти наш граф требуемым образом невозможно. Итак, предположим противное. Пусть Z - вершина, в которой мы не начали и не закончили путь. При этом, в Z мы, очевидно, побывали в процессе пути (ибо мы обязаны пройти по всем рёбрам, в том числе и ведущим в Z). Но тогда в вершину Z мы вошли столько же раз, сколько и вышли из неё. При этом каждый раз мы проходили по новому ребру (ходить по одному ребру несколько раз нам запрещено условиями задачи). Получается, Z - чётная вершина. Но ведь степени всех вершин нашего графа нечётны. Противоречие! А значит, обойти граф требуемым образом невозможно. Вот и всё доказательство!
И, напоследок, теорема, теснейшим образом связанная с задачей (её Эйлер и доказал в процессе решения задачи о мостах): в связном (т.е. в графе, где между любыми двумя вершинами есть путь по рёбрам) графе существует Эйлеров путь (т.е. путь по всем рёбрам, как в задаче про мосты) тогда и только тогда, когда в нём не более двух нечётных вершин (кроме того, в графе не может быть ровно одной нечётной вершины, но об этом - в другой раз). Попробуйте доказать эту теорему сами, подсказка - в решении задачи про мосты. Кроме того, если в связном графе все вершины чётные, то он содержит Эйлеров цикл (Эйлеров путь, который начинается и заканчивается в одной вершине).
А на сегодня всё.
Не забывайте подписываться на канал, ставить лайк и писать в комментарии идеи для статей!
Читайте также: