16.1. Эйлеровы и гамильтоновы цепи и циклы

При решении задач информатики важное значение имеют графы специального вида ─ Эйлеровы и Гамильтоновы.

Постановка задачи о Кенигсберских мостах знаменует начало создания теории графов. На рис. 16.1 показан условный план города, а на рис. 16.2 ─ его модель в виде графа. Здесь A, B, C, D (рис. 16.1) ─ суша, a, b, c, d, e, f, g – мосты, соединяющие сушу между собой.

Рис. 16.1. Условный план города

Рис. 16.2. Модель плана города в виде графа

Требуется пройти каждый мост по одному разу и вернуться в исходную часть города. На рис. 2.2 вершины графа ─ части города, а ребра графа ─ мосты.

Все вершины графа на рис. 2.2 имеют нечетную степень, следовательно, решения нет.

Теорема 16.1 (Л. Эйлер 1736 г.) Связный неориентированный граф содержит эйлеров цикл (эйлерову цепь) тогда и только тогда, когда число вершин нечетной степени равно 0 (или 2).

Доказательство для цикла:

1) Необходимость: Любой Эйлеров цикл (ЭЦ) должен прийти в вершину по одному ребру и покинуть ее по другому, так как любое ребро должно использоваться только один раз. Поэтому, если G содержит ЭЦ, то степени всех вершин должны быть четными.

2) Достаточность: Пусть G ─ связный неорграф, все вершины которого имеют четную степень. Начнем путь из произвольной вершины x₀ и пойдем по некоторому ранее не использованному ребру к следующей вершине и так до тех пор, пока не вернемся в x₀ и не замкнем цикл. Если все ребра использованы, то ЭЦ построен. Если некоторые ребра не использованы, то процесс продолжается. Пусть Ф ─ построенный цикл (рис. 2.3) и Ф1 ─ цикл с не использованными ребрами.

Рис. 16.3. Пример построения эйлерова цикла

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

Если удалить ребра Ф, то в оставшемся графе вершины по-прежнему будут иметь четную степень, так как в Ф должно быть четное число ребер, инцидентных каждой вершине. Начиная с x_i, получаем цикл Ф1. Если все ребра использованы, то ЭЦ построен путем Ф  Ф1. Если остались неиспользованные ребра, то процесс снова продолжается, до тех пор, пока не будут использованы все ребра и построен ЭЦ Ф (рис. 16.4). Это доказывает теорему.

Рис. 16.4. Пример эйлерова цикла в графе

Граф называется полуэйлеровым, если существует незамкнутая цепь, проходящая через каждое ребро графа только один раз. Конечный граф G является эйлеровым, если он связен и все его локальные степени четны. Если эйлеров цикл Сэ существует, то, проходя по его ребрам, можно нарисовать эйлеров граф на бумаге, не отрывая карандаша. На рис. 16.5 ─ 16.7 показаны неэйлеров (рис. 16.5), полуэйлеров (рис 16.6) и эйлеров (16.7) графы. Порядок обхода полуэйлерова и эйлерова графов показан стрелками.

Рис. 16.5. Неэйлеров граф Рис. 16.6. Полуэйлеров граф

Рис. 16.7. Эйлеров граф

Например, граф G (рис. 16.6) не является эйлеровым, так как степени вершин x₁, x₃ ─ нечетны. Граф G также не является эйлеровым, если он не связен, хотя его компоненты могут являться эйлеровыми графами.

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

Запишем алгоритм Флери построения Сэ в связном графе G = (X, U), локальные степени которого четны.

1. Пусть начальная вершина цикла x_k = x₁. Число ребер U графа G равно |U| = n, а x_s – произвольно выбранная вершина графа. Эйлеров цикл Ci = .

2. Определяем множество ребер, смежных вершине x_s.

3. Выбираем ребро, удаление которого не приведет к разбиению графа на два компонента связности (кроме изолированных вершин). Пусть это будет ребро u_k = (x_s, x_p).

4. Тогда добавляем это ребро в эйлеров цикл C_k = C_k  u_k и удаляем его из графа G.

5. Если выполняется условие |C_k| = n, то переход к п. 7, иначе переход к п. 6.

6. Присваиваем k = k + 1, s = p и переходим к п. 2.

7. Эйлеров цикл построен, конец работы алгоритма.

Также можно привести еще один вариант записи алгоритма Флери.

1. Выбирается произвольная вершина x_i, i  I = {1, 2, ..., n}.

2. Определяется произвольное ребро (x_i, x_j) j  i, j  I, инцидентное вершине x_i, ему присваивается номер 1. Это ребро заносится в список Lэ и вычеркивается из графа G.

3. Рассматривается вершина x_j, если есть возможность другого выбора, не выбираются ребра (x_j, x_k), ему присваивается номер, оно заносится в список Lэ и вычеркивается из G.

4. Производится проверка |Lэ| = m. Если да, то переход к п. 5, если нет, то п. 3 повторяется для вершин x_b, ..., x_n.

5. Построен эйлеров цикл Сэ, конец работы алгоритма.

На рис. 16.7 стрелками показан пример работы алгоритма

Сэ = (x₁, x₂), (x₂, x₆), (x₆, x₃), (x₃, x₂), (x₂, x₄), (x₄, x₅), (x₅, x₃), (x₃, x₁).

Цикл, проходящий по всем вершинам графа G один раз, называется гамильтоновым, а G называется гамильтоновым графом. Например, граф G (рис. 16.7) не имеет гамильтонова цикла (ГЦ), а граф G (рис. 16.5) имеет Gг = (x₁, x₂), (x₂, x₅), (x₅, x₄), (x₄, x₃), (x₃, x₁). В отличие от эйлеровых циклов для ГЦ неизвестен общий критерий существования. В основном известны только теоремы, дающие достаточные условия существования ГЦ.

Теорема 16.2. Если в графе G с n вершинами для любой пары несмежных вершин x_i, x_j верно: (x_i) + (x_j)  n, то G имеет ГЦ.

Из теоремы следует результат Дирака, что граф имеет ГЦ, если для каждой его вершины

(x_i)  n/2. (16.1)