Гамма-алгоритм (в общем виде) 2 страница

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

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

Пример. Граф, приведенный на рисунке 6.50, можно изобразить в виде последовательности вершин так: 1,2,4,2,1,3,2,3,4, откуда следует, что два раза карандаш прошел только по ребру {2,3}.

Теорема Эйлера. Граф содержит эйлеров цикл тогда и только тогда, когда он связен и степени всех его вершин – четные.

 

 

20.7 Алгоритм нахождения эйлерова цикла (алгоритм Флери)

Шаг 1. Начиная с произвольной вершины , присвоить произвольному ребру номер 1. Затем вычеркнуть ребро и перейти в вершину .

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

Шаг 3. Повторять шаг 2 пока не все ребра вычеркнуты.

 

20.8 Гамильтоновы графы

 

Определение. Гамильтонов путь (или гамильтонова цепь) – путь (цепь), содержащий каждую вершину графа ровно один раз.

Определение. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

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

исунок 20.15 – Додекаэдр

Задача нахождения гамильтонова цикла с наименьшим весом хорошо известна как задача коммивояжера.

Определение. Гамильтонов граф – это граф, содержащий гамильтонов цикл (рис. 20.16).

Рисунок 20.16 – Гамильтонов граф

 

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

Рисунок 20.17 – Полугамильтонов граф

 

20.9 Алгоритм Робертса-Флореса (метод перебора Робертса-Флореса) нахождения гамильтоновых циклов в графе

 

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

 

Рисунок 20.18 – Граф

 

Матрица М:

	a	b	c	d	e	f
	b	c	a	c	c	a
	–	e	d	f	d	b
	–	–	–	–	–	c

 

Все вершины по очереди записываем во множество .

Поиск всех гамильтоновых циклов производится так (вершина берется в качестве отправной вершины):

 

№	Множество	Комментарии
		Добавляем первую возможную вершину в столбце (вершину ).
		Добавляем первую возможную вершину в столбце (вершину ).
		Первая возможная вершина в столбце не является возможной (), добавляем следующую вершину в столбце (вершину ).
		Добавляем вершину .
		В столбце нет возможных вершин. Возвращение.
		В столбце нет возможных вершин. Возвращение.
		В столбце нет возможных вершин. Возвращение.
		Добавляем вершину .
		Добавляем вершину .
		Добавляем вершину .
		Добавляем вершину .
		Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение.
		Возвращение.
		Возвращение.
		Добавляем вершину .
		Добавляем вершину .
		Добавляем вершину .
		Гамильтонова цепь. Дуга дает гамильтонов цикл. Возвращение.
		Возвращение.
		Возвращение.
		Возвращение.
		Возвращение.
		Возвращение.
		Конец поиска.

В результате получаем два гамильтоновых цикла (рис. 20.19).

 

 

 

Рисунок 20.19– Гамильтоновы циклы в графе

 

Определение. Реберным графом графа называется граф, имеющий столько же вершин, сколько ребер у графа . Ребро между двумя вершинами графа существует тогда и только тогда, когда ребра графа , соответствующие этим двум вершинам, смежные (т. е. инцидентные одной и той же вершине графа ).

Пример. На рис. 20.20 изображен исходный граф, а на рис. 20.21 – соответствующий ему реберный.

 

Рисунок 20.20

Рисунок 20.21

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

 

20.10 Признаки существования гамильтоновых циклов, путей и контуров

Общий признак, при помощи которого для любого графа можно было бы определить, имеет он гамильтонов цикл или нет, не найден до сих пор. Существуют некоторые достаточные условия гамильтоновости графа (все графы предполагаются связными и простыми).

Если в графе есть висячая вершина (со степенью, равной единице), то гамильтонов цикл в нем отсутствует (рис. 20.22).

Рисунок 20.22

Теорема (условие Дирака). Если число вершин графа не менее трех и степень любой вершины не менее , то граф является гамильтоновым.

Теорема (условие Оре). Если в графе с вершинами () сумма степеней любых двух вершин и является не меньшей, чем (), то граф является гамильтоновым.

Теорема Бонди-Хватала. Пусть для упорядоченной по возрастанию последовательности степеней вершин , , графа выполнены импликации , , тогда – гамильтонов граф.

Теорема (условие Харари). Реберный граф гамильтонов тогда и только тогда, когда в существует цикл, содержащий хотя бы по одной вершине из каждого ребра графа .

Следствие. Если граф либо эйлеров, либо гамильтонов, то реберный граф гамильтонов.

Теорема (признак Кенига). В полном орграфе (любая пара вершин которого соединяется хотя бы в одном направлении) всегда существует гамильтонов путь.

 

20. 11 Контрольные вопросы и задания

 

1. Дайте определение связного и несвязного графов.

2. Что называется степенью связности графа?

3. Перечислите свойства связных графов.

4. Приведите примеры метрических характеристик связных графов.

5. Дайте определения эйлерова цикла (эйлеровой линии, замкнутой эйлеровой цепи, эйлеровой цепи).

6. Какой граф называется эйлеровым?

7. Для решения каких практических задач используется теорема Эйлера?

8. Дайте определение гамильтонова пути (гамильтоновой цепи), гамильтонова цикла.

9. Какой граф называется гамильтоновым?

10. Охарактеризуйте применение задачи коммивояжера.

11. Приведите алгоритм Робертса-Флореса. Для каких целей он используется?

12 Назовите основные признаки существования гамильтоновых циклов, путей и контуров.

13. Охарактеризуйте теорему (условие Дирака) для определения гамильтонова графа.

 

Лекция 21 Деревья

 

21.1 Определение и свойства деревьев

 

Определение. Связный граф, не содержащий циклов, называется деревом (рис. 21.1).

Рисунок 21.1 – Дерево

Несвязный граф, не содержащий циклов, называется лесом.

Пример. На рис. 21.2 приведен трехкомпонентный лес. Первую компоненту образует дерево с вершинами 1,2,3,4, вторую – 5,6,7,8,9, третью – 10,11.

Рисунок 21.2 – Лес

 

21.2 Свойства деревьев

 

Теорема 21.1. Всякое дерево содержит ребер, где – число вершин.

Теорема 21.2. Всякий лес содержит ребер, где – число компонент связности.

Теорема 21.3. Любые две вершины дерева соединены точно одной простой цепью.

Теорема 21.4. Если в дереве любые две вершины соединить ребром, то в графе появится один цикл.

 

21.3 Перечисление графов

 

Определение. Граф называется помеченным, если его вершинам присвоены фиксированные метки, например, номера .

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

Пример. На рис. 21.3 изображены все помеченные графы с числом вершин ; их количество равно 8.

 

Рисунок 21.3

Количество (неориентированных) помеченных графов (простых с вершинами и ребрами) равно числу сочетаний из множества различных неориентированных пар вершин по числу ребер .

,

Суммируя числа по всем возможным количествам ребер от случая безреберного графа до случая полного графа с вершинами, получаем число всех помеченных графов с вершинами:

Число неизоморфных графов без пометок (простых, неориентированных) найти значительно труднее. Среди восьми графов на рисунке 3 без учета пометок можно указать только четыре попарно неизоморфных друг другу, например, в квадратах 1, 2, 7, 8. Следовательно, , что вдвое меньше числа помеченных графов. Число помеченных четырехвершинных графов равно 64, в то время как различных неизоморфных четырехвершинных графов без пометок существует всего .

Если через обозначить число неизоморфных -вершинных графов с ребрами, то

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

 

 

21.4 Перечисление деревьев

 

Введем обозначения: – число помеченных деревьев с вершинами.

– число обычных (неизоморфных) деревьев с вершинами.

Пример. На рис. 21.4 изображены все помеченные четырехвершинные деревья. Их 16.

 

 

Рисунок 21.4

Формула А. Кэли. Число помеченных деревьев с вершинами равно , т.е. .

 

Числа обычных (неизоморфных) деревьев являются значительно меньшими, однако вычислить их существенно труднее. Современные алгоритмы нахождения значений и получения конфигураций неизоморфных деревьев с вершинами основаны на теории перечисления Д. Пойа.

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

Все корневые деревья с числом вершин изображены на рисунке 21.5.

Рисунок 21.5

 

Все корневые деревья с числом вершин изображены на рис. 21.6.

Рисунок 21.6

 

21.5 Остовы графа

 

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

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

Пример. Рассмотрим, например, граф, изображенный на рис. 21.7. Удалим из него ребра и и получим остов. Если удалить ребра и , то получим другой остов.

Рисунок 21.7

 

Два остова в считаются различными, если они отличаются хотя бы одним ребром.

Для того чтобы имел более одного остова, необходимо и достаточно существование хотя бы одного цикла в .

Для полного (простого) графа перечисление остовов есть перечисление всех помеченных деревьев с вершинами графа , так что число остовов равно .

В общем случае число остовов получил Кирхгоф.