Онлайн подготовка к ЕГЭ-2022 по профильной математике
Подготовьтесь к ЕГЭ на 80+ баллов. Смотрите видео, читайте теорию, занимайтесь на онлайн-тренажерах
design_arrow
Прогулки по мостам и графы

Прогулки по мостам и графы

Вот уже больше семи веков на реке Преголи стоит красивый город Кёнигсберг – сейчас он называется Калининград. В пределах города находятся два острова, поэтому он разделен рекой на четыре части. Вы удивитесь, но Калининград обладает очень интересной архитектурой – разумеется, с точки зрения математики. Издавна его жители предлагали всем приезжим решить занимательную Задачу о семи Кёнигсбергских мостах: нужно было во время прогулки пройти по каждому мосту ровно один раз.

2.png

Так задача и оставалась нерешенной, вплоть до того, как в 1736 году прогуляться по мостам предложили Леонарду Эйлеру. После безуспешной попытки построить такой маршрут Эйлер заинтересовался задачей и вывел общее правило, по которому легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Именно это предстоит сделать нам с вами в этой статье!


Первое, что необходимо сделать – описать задачу в терминах математики. Давайте упростим схему города, оставив только вершины – отделенные рекой районы, и ребра – мосты, которые их соединяют. Получается, мы свели задачу к поиску пути в плоском графе, содержащего все ребра и не проходящего по какому-либо из них дважды. С таким условием гораздо проще работать:

граф.PNG

На следующем этапе рассмотрим слегка измененную задачу: пусть нужно не только пройти по всем мостам, но и вернуться в исходную точку. Если в графе существует такой маршрут, какие появляются ограничения на его вершины и ребра? Во-первых, граф должен быть связным – из любой его вершины должно быть возможно попасть в любую другую, иначе часть города окажется отрезана рекой. Во-вторых, идя по заданному маршруту, в каждую вершину графа мы можем прийти несколько раз – по разным ребрам, но ровно столько же раз придется из нее уйти, поэтому число ребер, выходящих из каждой вершины, должно быть четным. Оказывается, этих условий достаточно для существования замкнутого пути, проходящего по одному разу по всем рёбрам графа, с тех пор называемого эйлеровым циклом.

На последнем этапе наших рассуждений вспомним, что изначально задача звучала иначе: начинаться и заканчиваться прогулка может в разных частях города, то есть первая и последняя вершины пути в графе могут не совпадать. Внесем корректировки в поставленные условия. Теперь мы допускаем ровно две вершины с нечетным числом исходящих ребер – в одной их них должно быть начало нужного маршрута, а во второй – конец. Такие условия будут достаточными и в общем случае: начертить одним росчерком можно любой связный граф, все вершины которого четные, или же ровно две из них имеют нечетное число исходящих ребер.

Давайте вновь посмотрим на нашу схему города: все четыре вершины графа – нечетные, и это означает, что построить нужный маршрут прогулки по семи мостам Кёнигсберга невозможно. Однако существует легенда, что император Германии Вильгельм II не пожелал мириться с таким положением дел, и в 1905 году был построен восьмой Императорский мост. К сожалению, сейчас город выглядит совсем иначе – все восемь мостов были перестроены или разрушены, но благодаря старым картам вы можете найти императорское решение задачи!

кёнигсберг_2.png