Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Глава девятая: общий оборот авансированного капитала. Циклы оборотов
  2. Замкнутый и разомкнутые термодинамические циклы.
  3. Маршруты, цепи, циклы
  4. Связь между эйлеровыми и гамильтоновыми графами
  5. Теоретические циклы
  6. Тренировочные циклы
  7. Циклы в JavaScript

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

Постановка задачи о Кенигсберских мостах знаменует начало создания теории графов. На рис. 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)


Дата добавления: 2015-10-26; просмотров: 184 | Нарушение авторских прав


Читайте в этой же книге: Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 3 страница | Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 4 страница | Графический способ. | Теорема о функциональной полноте | КРИТЕРИИ ОЦЕНКИ | Способы задания графов | Примеры РЕШЕНИЯ ЗАДАЧ | Маршруты, цепи, циклы | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Алгоритм Форда |
<== предыдущая страница | следующая страница ==>
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ| Связь между эйлеровыми и гамильтоновыми графами

mybiblioteka.su - 2015-2024 год. (0.007 сек.)