Задача о мостах Кёнигсберга: степени графа и теорема Эйлера

Задача о семи мостах Кёнигсберга - первая задача, которую решили языком теории графов, а не геометрии или арифметики: в 1736 году Леонард Эйлер доказал, что жителям Кёнигсберга не удастся пройти по всем семи мостам через реку Прегель ровно один раз и вернуться в исходную точку. Ниже разберём, как превратить карту города в граф из вершин и рёбер, что такое степень вершины и как по одной простой теореме сразу видно, разрешима задача или нет. Чтобы сразу увидеть связь числа мостов и ответа, покрутите калькулятор ниже: он строит схему района и столбец степеней для любой конфигурации мостов, а дальше разберём теорему по шагам.

Как устроен граф мостов Кёнигсберга

Старый Кёнигсберг стоял на реке Прегель, которая делилась на два рукава и образовывала остров Кнайпхоф. Мосты соединяли четыре участка суши: северный берег, южный берег, остров Кнайпхоф и восточный берег (район Ломзе). Всего мостов было семь: два вели с северного берега на остров, два - с южного берега на остров, и по одному соединяли остальные пары районов.

Рассчитать для своей задачи

Чтобы решать задачу математически, Эйлер заменил карту графом: каждый район суши стал вершиной, а каждый мост - ребром, соединяющим две вершины. Если между районами несколько мостов, в графе появляется несколько рёбер между теми же двумя вершинами - такой граф называют мультиграфом. Именно этот шаг - свести конкретную карту к абстрактному графу - считается рождением теории графов как отдельного раздела математики.

Степень вершины и что она означает

Степень вершины - это количество рёбер (мостов), которые в неё входят. Если район соединён с соседями пятью мостами, его степень равна пяти, независимо от того, к скольким разным районам эти мосты ведут.

Рассчитать для своей задачи

В классической задаче остров Кнайпхоф соединён пятью мостами (два с северным берегом, два с южным, один с восточным районом), поэтому его степень равна пяти. Северный берег, южный берег и восточный район соединены тремя мостами каждый. Легко проверить общее свойство: сумма степеней всех вершин всегда равна удвоенному числу рёбер, потому что каждый мост учитывается дважды - по разу для каждого своего конца:

$\sum_{v} \deg(v) = 2|E|.$

Для Кёнигсберга: $3 + 3 + 5 + 3 = 14 = 2 \cdot 7$. Эта формула - не просто проверка арифметики, из неё сразу следует важный факт: число вершин нечётной степени в любом графе всегда чётно (лемма о рукопожатиях). Значит, у графа из четырёх районов таких вершин может быть 0, 2 или 4 - но никогда 1 или 3.

Теорема Эйлера: когда есть путь, а когда цикл

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

• если вершин нечётной степени нет, эйлеров цикл существует - можно обойти все рёбра и вернуться в старт из любой вершины;
• если таких вершин ровно две, существует эйлеров путь - но начинать и заканчивать нужно именно в этих двух вершинах, а не в произвольной точке;
• если нечётных вершин четыре и больше, ни путь, ни цикл невозможны в принципе, сколько бы вы ни пытались подобрать маршрут.

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

Почему у Кёнигсберга нет решения

Подставим реальные степени: северный берег - 3, южный берег - 3, остров Кнайпхоф - 5, восточный район - 3. Все четыре значения нечётные:

$\deg(A) = 3,\quad \deg(B) = 3,\quad \deg(C) = 5,\quad \deg(D) = 3.$

Нечётных вершин четыре, а не ноль и не две - значит, по теореме Эйлера обойти все семь мостов ровно по одному разу нельзя ни при каком порядке прогулки, и вернуться в старт тоже нельзя. Это и есть тот самый отрицательный результат 1736 года: он не про удачу или неудачу конкретного пешехода, а про строгую невозможность, которую можно доказать заранее, даже не выходя на улицу и не перебирая маршруты.

Как исправить граф: сколько мостов добавить

Раз проблема - в нечётных степенях, у неё есть конструктивное решение: добавить мосты так, чтобы «починить» чётность нужных вершин. Каждый новый мост между двумя нечётными районами превращает обе их степени в чётные (нечётное плюс один - чётное). Поэтому:

• чтобы получить эйлеров путь из четырёх нечётных вершин, достаточно добавить один мост между любыми двумя из них - тогда останутся ровно две нечётные вершины;
• чтобы получить эйлеров цикл, нужно добавить два моста, разбив все четыре нечётные вершины на две пары.

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

Как эта задача связана с теорией графов

Работа Эйлера 1736 года заложила метод, который сегодня используют далеко за пределами мостов: сводить прикладную задачу к абстрактному графу из вершин и рёбер и решать её через свойства этого графа. Тот же приём лежит в основе задач о маршрутах почтальона, объезде улиц дорожной техникой, проверке схем на возможность нарисовать их одной линией без отрыва карандаша и даже в анализе электрических цепей. Понятие степени вершины и критерий существования эйлерова пути с тех пор остаются одним из первых результатов, которые изучают в любом курсе дискретной математики.

Частые ошибки

• Путают степень вершины с числом соседних районов. Если между двумя районами два моста, они добавляют к степени по два, а не по одному - считать нужно мосты, а не соседей.
• Ищут маршрут перебором вместо проверки степеней. Перебор маршрутов для реального Кёнигсберга бесконечен и ничего не доказывает; правильный путь - сразу посчитать степени всех вершин.
• Забывают про связность графа. Теорема Эйлера про путь и цикл работает только для связного графа - если часть районов вообще не соединена мостами, вопрос о прогулке по всем рёбрам сразу теряет смысл.
• Считают, что две нечётные вершины дают цикл. Две нечётные вершины дают только путь с обязательным началом и концом именно в них; для цикла нужно ноль нечётных вершин.
• Путают эйлеров путь с гамильтоновым. Эйлеров путь проходит по каждому ребру один раз, гамильтонов - по каждой вершине один раз; это разные задачи с разными критериями существования.

FAQ

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

Можно ли пройти по всем мостам Кёнигсберга, если не требовать возврата в начало? Нет. Условие возврата тут ни при чём: даже без него нужно не более двух вершин нечётной степени, а в Кёнигсберге их четыре. Поэтому невозможен ни эйлеров цикл, ни просто эйлеров путь.

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

Коротко

Задача о семи мостах Кёнигсберга решается переводом карты в граф из районов-вершин и мостов-рёбер, где ключевая характеристика каждой вершины - её степень, число входящих мостов. По теореме Эйлера связный граф допускает эйлеров цикл, если все степени чётные, эйлеров путь - если ровно две вершины нечётные, и не допускает ни того ни другого при четырёх и более нечётных вершинах. У реального Кёнигсберга все четыре района имеют нечётную степень (3, 3, 5, 3), поэтому обойти семь мостов по одному разу и вернуться в начало нельзя - но задачу легко сделать разрешимой, добавив один или два моста между нечётными районами.