При решении задач информатики важное значение имеют графы специального вида ─ Эйлеровы и Гамильтоновы.
Постановка задачи о Кенигсберских мостах знаменует начало создания теории графов. На рис. 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 0 и пойдем по некоторому ранее не использованному ребру к следующей вершине и так до тех пор, пока не вернемся в x 0 и не замкнем цикл. Если все ребра использованы, то ЭЦ построен. Если некоторые ребра не использованы, то процесс продолжается. Пусть Ф ─ построенный цикл (рис. 2.3) и Ф1 ─ цикл с не использованными ребрами.
Рис. 16.3. Пример построения эйлерова цикла
Так как G связен, то Ф должен проходить через вершину, являющуюся концом неиспользованного ребра.
Если удалить ребра Ф, то в оставшемся графе вершины по-прежнему будут иметь четную степень, так как в Ф должно быть четное число ребер, инцидентных каждой вершине. Начиная с xi, получаем цикл Ф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 1, x 3 ─ нечетны. Граф G также не является эйлеровым, если он не связен, хотя его компоненты могут являться эйлеровыми графами.
Заметим, что связный граф G является полуэйлеровым, когда в нем не более двух вершин имеют нечетные локальные степени. Причем одна из этих вершин будет начальной, а другая конечной.
Запишем алгоритм Флери построения Сэ в связном графе G = (X, U), локальные степени которого четны.
1°. Пусть начальная вершина цикла xk = x 1. Число ребер U графа G равно |U| = n, а xs – произвольно выбранная вершина графа. Эйлеров цикл Ci = Æ.
2°. Определяем множество ребер, смежных вершине xs.
3°. Выбираем ребро, удаление которого не приведет к разбиению графа на два компонента связности (кроме изолированных вершин). Пусть это будет ребро uk = (xs, xp).
4°. Тогда добавляем это ребро в эйлеров цикл Ck = Ck È uk и удаляем его из графа G.
5°. Если выполняется условие | Ck | = n, то переход к п. 7°, иначе переход к п. 6°.
6°. Присваиваем k = k + 1, s = p и переходим к п. 2°.
7°. Эйлеров цикл построен, конец работы алгоритма.
Также можно привести еще один вариант записи алгоритма Флери.
1°. Выбирается произвольная вершина xi, i Î I = {1, 2,..., n}.
2°. Определяется произвольное ребро (xi, xj) j ¹ i, j Î I, инцидентное вершине xi, ему присваивается номер 1. Это ребро заносится в список Lэ и вычеркивается из графа G.
3°. Рассматривается вершина xj, если есть возможность другого выбора, не выбираются ребра (xj, xk), ему присваивается номер, оно заносится в список Lэ и вычеркивается из G.
4°. Производится проверка |Lэ| = m. Если да, то переход к п. 5°, если нет, то п. 3° повторяется для вершин xb,..., xn.
5°. Построен эйлеров цикл Сэ, конец работы алгоритма.
На рис. 16.7 стрелками показан пример работы алгоритма
Сэ = (x 1, x 2), (x 2, x 6), (x 6, x 3), (x 3, x 2), (x 2, x 4), (x 4, x 5), (x 5, x 3), (x 3, x 1).
Цикл, проходящий по всем вершинам графа G один раз, называется гамильтоновым, а G называется гамильтоновым графом. Например, граф G (рис. 16.7) не имеет гамильтонова цикла (ГЦ), а граф G (рис. 16.5) имеет Gг = (x 1, x 2), (x 2, x 5), (x 5, x 4), (x 4, x 3), (x 3, x 1). В отличие от эйлеровых циклов для ГЦ неизвестен общий критерий существования. В основном известны только теоремы, дающие достаточные условия существования ГЦ.
Теорема 16.2. Если в графе G с n вершинами для любой пары несмежных вершин xi, xj верно: r (xi) + r (xj) ³ n, то G имеет ГЦ.
Из теоремы следует результат Дирака, что граф имеет ГЦ, если для каждой его вершины
r (xi) ³ n/2. (16.1)
