- •Министерство образования и науки российской федерации
- •Лабораторная работа №1 операции над множествами
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Примеры записи нечеткого множества
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №3 бинарные отношения
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа № 4 комбинаторные алгоритмы
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа № 5 Машинное представление графа
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №6 алгоритмы построения кратчайших путей в графе и кратчайшего остова графа
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №7 алгоритмы построения эйлерова и гамильтонова цикла
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №8 совершенные нормальные формы булевых функций
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Библиографический список
Лабораторная работа №7 алгоритмы построения эйлерова и гамильтонова цикла
Цель работы: изучение эйлеровых и гамильтоновых графов и алгоритмов построения эйлеровых и гамильтоновых циклов.
Теоретические сведения
1. Построение эйлерова цикла.
Эйлеровым циклом называется замкнутый маршрут (путь) в графе, проходящий через каждое его ребро (дугу) точно один раз.
Необходимым и достаточным условием существования эйлерова цикла в неориентированном графе является связность графа и чётность степеней всех вершин графа. Если это условие выполнено, то построить эйлеров цикл можно с помощью следующего алгоритма, который полностью повторяет доказательство достаточности теоремы. В алгоритме используются обозначения:
C – вспомогательный стек;
CE – результирующий стек, содержащий эйлеров цикл;
–начальная вершина цикла.
; ; ; ;
while ( )
{ ;
if ()
{ ; ;
;
;
;
}
else { ;
}
}
Построение цикла начинается с произвольной начальной вершины, которая заносится в промежуточный стек. Далее, пока стек C не пуст, выполняется обработка его верхушки v. Если список вершины, являющейся верхушкой стека, не пуст (что означает наличие ребра, инцидентного v), то вершина списка u заносится в промежуточный стек, а ребро удаляется из графа. В противном случае вершинаv переносится из промежуточного стека в результирующий.
После окончания работы алгоритма стек CE содержит эйлеров цикл.
2. Построение гамильтонова цикла.
Так как не существует необходимого и достаточного условия гамильтоновости графа, то вопрос о существовании гамильтонова цикла решается после попытки его построения. Для построения такого цикла воспользуемся вариантом алгоритма с возвратом, который использует механизм рекурсии.
Построение цикла начинается с произвольной начальной вершины
Обозначим:
x – массив, содержащий гамильтонов цикл;
Dop – массив логических переменных, означающих возможность использования вершины в цикле.
Gamilt ( k )
{ for ()
if ( () () ) вывод массива x и ;
else if ()
{ ; ;
Gamilt ( k +1);
;
}
}
for () ;
; ;
Gamilt (2);
Данный алгоритм выводит все существующие гамильтоновы циклы графа.
Пример выполнения работы.
1. Рассмотрим неориентированный граф, заданный следующим входным файлом. Построим графическое представление графа, определяемого этим файлом.
12
1 3
2 3
2 7
2 8
3 4
3 5
4 5
5 6
5 8
6 8
6 7
6 9
7 8
7 9
Так как степени всех вершин графа чётны и граф является связным, то в нём существует эйлеров цикл. Построим его, выбрав начальной вершину 1 и считая записи в списках инцидентности вершин упорядоченными по возрастанию номеров вершин. Построим в соответствии с алгоритмом стеки C и CE. Серым цветом в стеке С выделены вершины, которые были перенесены из стека C в стек CE. Белым цветом с стеке С отмечены вершины, находящиеся с стеке на момент окончания его заполнения. Так как списки всех вершин на этом этапе пусты, то далее все они переносятся в стек CE по механизму стека (в обратном порядке).
8 |
|
1 |
7 |
|
2 |
9 |
|
3 |
6 |
|
4 |
5 |
|
5 |
8 |
|
6 |
2 |
|
7 |
7 |
|
2 |
6 |
|
8 |
3 |
|
6 |
5 |
|
9 |
4 |
|
7 |
1 |
|
8 |
3 |
|
5 |
2 |
|
3 |
1 |
|
1 |
C CE
Таким образом, эйлеров цикл имеет вид:
1 2 3 4 5 6 7 2 8 6 9 7 8 5
3 1.
2. Определим, является ли граф из задания 1 гамильтоновым. Для этого воспользуемся алгоритмом с возвратом, работу алгоритма проиллюстрируем построением дерева решений. Вершинами данного дерева являются вершины графа, ветвями – просматриваемые варианты пути. Дерево будем заполнять в порядке просмотра вершин алгоритмом, варианты пути заполнять слева направо, т.е. ранее присмотренные варианты путей располагаются левее. Построение дерева закончим, найдя 1 вариант гамильтонова цикла или исчерпав все варианты.
Рис.
Следовательно, граф является гамильтоновым, а гамильтонов цикл имеет вид: 1 2 7 9 6 8 5 4 3 1.