§ 2. Эйлеровы и гамильтоновы графы

Определение 1. Связный граф G называется эйлеровым, если существует замкнутая простая цепь, содержащая каждое его ребро. Такая цепь называется эйлеровым циклом. Если граф не эйлеров, но имеется простая цепь, содержащая каждое его ребро, то он называется полуэйлеровым.

Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет чётную степень.

По этой теореме графы и октаэдра являются эйлеровыми.

В силу алгоритма Флёри (Fleury) для построения эйлеровой цепи в данном эйлеровом графе можно выйти из любой вершины графа и идти по рёбрам графа произвольным образом, соблюдая лишь следующие правила:

1. стирать рёбра по мере их прохождения и изолированные вершины, если они при этом образуются;

2. на каждом этапе идти по мосту только тогда, когда нет других возможностей.

Если граф не является эйлеровым, то по теореме 1 у него имеется хотя бы одна вершина нечётной степени. По теореме 2 из § 1 таких вершин тогда у него не менее двух.

Теорема 2. Связный граф G является полуэйлеровым тогда и только тогда, когда у него имеется ровно две вершины нечётной степени.

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

Так будет у графа на рис. 3.2. Приведем другие примеры.

Пример 1. В графах на рис. 3.7 цифрами показаны этапы одного из эйлерова цикла и эйлерова пути, если они существуют:

Рис. 3.7

Левый граф (‘запечатанный конверт’) на рис. 3.7 не эйлеров и не полуэйлеров, т. к. у него имеется более двух вершин нечётной степени.

Рассмотрим задачу о семи кёнигсбергских мостах с помощью изложенной теории.

Поскольку, по отношению к основному условию задачи (о прохождении мостов, см. рис 3.1), форма и размеры островов и берегов совершенно не существенны, разумно их обозначить точками, соответственно, A, B, C, D. Важным для задачи является то, какие из этих частей города (точек) соединены друг с другом мостами (соответственно, дугами) и сколькими, если их больше одного. Соответствующие соединения показаны на рис. 3.8. Эта картинка из точек и линий, соединяющих некоторые из них попарно, моделирует условия задачи о прогулке по 7 мостам.

Теперь вопрос звучит так: можно ли, начав с какой-либо точки A, B, C или D, пройти по одному разу по всем линиям на рис. 3.8 и вернуться в начальную точку.

Рис. 3.8. Граф задачи о семи мостах

Так как теоремы 1 и 2 Л. Эйлера справедливы не только для простых графов, то ясно, что граф на рис. 3.8 не является эйлеровым и даже полуэйлеровым (у него четыре вершины нечётной степени). Следовательно, ответ на вопрос жителя Кёнигсберга – отрицательный, где бы он ни проживал. И этот ответ обоснован с помощью теории графов.

Рассмотрим задачу, которая может возникнуть у архитектора или у директора музея, помещение для которого еще только создаётся.

На рис. 3.9 изображена схема расположения залов музея (их девять: от (1) до (9)) и дверей между ними (светлые кружочки), задуманного для постройки.

A

B

D

C

Рис. 3.9. Схема залов музея

Можно ли на фрагменте BC или FG внешнего контура схемы будущего музея запланировать входные двери, которые служили бы и выходом из музея, и при этом для посетителей музея была бы возможность проходить все его залы (естественно, кроме зала входа-выхода) ровно по одному разу?

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

1) заменить каждый зал схемы музея точкой – вершиной будущего графа,

2) наличие дверей, соединяющих непосредственно два соседних зала, отразить отрезком (дугой) с концами в тех двух вершинах, которые соответствуют этим залам.

Картинка этих соединений показана на рис. 3.10 (на ней 9 вершин и 14 соединяющих их отрезков – по числу залов и дверей на схеме 3.9). Мы создали графовую модель условия задачи о схеме музея. Теперь вопрос звучит так: можно ли, начав из точки (4) или (7), пройти по одному разу через все вершины графа на рис. 3.10 и вернуться в начальную точку?

Рис. 3.10. Граф схемы залов музея

Подобные замкнутые обходы вершин впервые рассматривал ирландский математик У. Гамильтон (1805–1865), решая следующую головоломку: найти замкнутую элементарную цепь, проходящую некоторым рёбрам через все вершины в графе додекаэдра, изображенного на рис. П.8 Части 2. Решение этой задачи представлено на рис. 3.11 с помощью плоского графа, изоморфного графу додекаэдра.

Рис. 3.11. Гамильтонов цикл на додекаэдре

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

Указанный метод «растяжки продырявленной резиновой оболочки» помогает получать плоские изображения графов любых выпуклых многогранников (см., например, рис. 3.4, 3.5, 3.6).

Определение 2. Граф G называется гамильтоновым, если в G существует элементарная замкнутая цепь, проходящая через каждую его вершину. Такая цепь называется гамильтоновым циклом. Если граф не является гамильтоновым, но имеется элементарная цепь, проходящая через каждую его вершину, то он называется полугамильтоновым.

Отметим, что граф на рис. 3.10 не является гамильтоновым. Следовательно, вход-выход в музей, сделанный на BC (соответственно, на FG) рис. 3.9, не обеспечивает требуемой возможности обхода залов.

Что в таком случае можно посоветовать архитектору?

По рис. 3.10 можно догадаться, что, например, при добавлении ребра (1,4) (т. е. создании двери между залами (1) и (4) на рис. 3.9) новый граф станет гамильтоновым. Тогда вход в музей через зал (7) обеспечит требуемый обход залов. Например, таким будет обход: (7) – (2) – (8) – (3) – (1) – (4) – (5) – (9) – (6) – (7).

А как быть, если пробивание внутренней стены нежелательно?

Анализ графа на рис. 3.10 позволяет заметить, что он полугамильтонов: (7) – (2) – (8) – (3) – (1) – (6) – (9) – (5) – (4). Следовательно, архитектор вместо пробивания новых дверей внутри музея может запланировать создание входа на отрезке FG с выходом на отрезке BC (или наоборот).

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

Теорема 3. Полный граф с n вершинами при n ≥ 3 является гамильтоновым.

Теорема 4 (G.A. Dirac). Пусть G – простой граф с n вершинами, n ≥ 3 и пусть степень любой его вершины не меньше, чем n/2. Тогда G – гамильтонов граф.