Графы, степени и эйлеровы цепи

Определение и область рассмотрения

Конечный неориентированный мультиграф $G=(V,E)$G=(V,E) состоит из конечного множества вершин $V$V и конечного набора рёбер $E$E. Каждое ребро соединяет две вершины, не задавая направления движения. Одну и ту же пару вершин могут соединять несколько рёбер; петля также может соединять вершину с самой собой. Простой граф — это частный случай без петель и параллельных рёбер.

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

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

Минимальный словарь

Эйлерова цепь использует каждое ребро ровно один раз. Она открыта, если её концы различны, и становится эйлеровым циклом, если возвращается в начальную вершину. Слово «эйлеров» относится здесь к рёбрам, а не к вершинам.

Лемма о рукопожатиях

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

$\sum_{v\in V} \deg(v)=2\,|E|$v∈V∑​deg(v)=2∣E∣

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

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

Мосты Кёнигсберга

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

Эйлер обозначил участки буквами и представил последовательные переходы последовательностями букв. В современной теоретико-графовой формулировке каждый участок становится вершиной, а каждый мост — ребром. Полученный мультиграф имеет четыре вершины степеней 5, 3, 3 и 3. Их сумма равна 14, то есть вдвое больше числа рёбер (их семь), что согласуется с леммой.

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

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

Современная теорема Эйлера

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

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

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

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

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

Моделирование требует выбора правильной структуры

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

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

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

Резюме

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

Основные источники

• Leonhard Euler — Решение одной задачи из геометрии положения, английский перевод
• University of Warwick — Комбинаторика, лемма о рукопожатиях и эйлеровы циклы
• Carnegie Mellon University — Эйлеровы цепи и циклы