EssayAI
Блог
Блог
Математика и алгоритмы

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

11 июня 2026Время чтения: 8 минут
#семь мостов кёнигсберга#теорема эйлера#эйлеров путь#теория графов#степень вершины
Задача о мостах Кёнигсберга: степени графа и теорема Эйлера

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

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

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

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

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

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

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

Схема четырёх районов Кёнигсберга с подписанными степенями вершин: у острова Кнайпхоф степень 5, у остальных трёх районов - по 3, все значения нечётные
Схема четырёх районов Кёнигсберга с подписанными степенями вершин: у острова Кнайпхоф степень 5, у остальных трёх районов - по 3, все значения нечётные

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

∑vdeg⁡(v)=2∣E∣.\sum_{v} \deg(v) = 2|E|.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FAQ

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

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

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

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

8 ноября 20268 минут
Дерево: свойства и число рёбер

Дерево: свойства и число рёбер

Как связаны вершины и рёбра дерева, почему их числа отличаются на единицу и какие признаки помогают отличить дерево от произвольного графа. Примеры и доказательство.

8 ноября 20268 минут
Формула Эйлера для планарных графов

Формула Эйлера для планарных графов

Формула Эйлера для планарных графов: как считать вершины, рёбра и грани, почему учитывается внешняя область и как доказать равенство для связного графа.

8 ноября 20268 минут
Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток алгоритмом Форда-Фалкерсона: разбираем остаточную сеть, обратные рёбра и дополняющие пути на примере, а результат проверяем разрезом.

8 ноября 20269 минут