АЛГОРИТМЫ ПОСТРОЕНИЯ ЭЙЛЕРОВА И ГАМИЛЬТОНОВА ЦИКЛА

Цель работы: изучение эйлеровых и гамильтоновых графов и алгоритмов построения эйлеровых и гамильтоновых циклов.

Теоретические сведения

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. Рассмотрим неориентированный граф, заданный следующим входным файлом. Построим графическое представление графа, определяемого этим файлом.

1 2

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 по механизму стека (в обратном порядке).

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.

Контрольные вопросы

1. Сформулируйте необходимые и достаточные условия существования эйлерова цикла и пути в ориентированном и неориентированных графах.

2. Объясните основную идею алгоритма построения эйлерова цикла и проиллюстрируйте работу алгоритма на примере.

3. Что называется гамильтоновым циклом в графе?

4. Объясните принцип выполнения алгоритмов с возвратом.

5. Постройте одну ветвь дерева решений построения гамильтонова цикла примера и продемонстрируйте на ней механизм возврата.

Задание для лабораторной работы.

1. Для неориентированного графа варианта, заданного файлом вида «таблица рёбер», определить, является ли данный граф эйлеровым (ответ обосновать). Если да, то построить эйлеров цикл в соответствии с алгоритмом (записи в списках инцидентности вершин полагать упорядоченными по возрастанию номеров вершин). Отчёт должен содержать:

a) текст входного файла и графическое представление графа;

b) результирующий и вспомогательный стеки построения эйлерова цикла;

c) порядок обхода вершин эйлерова цикла (если он существует).

2. Для неориентированного графа варианта, заданного файлом вида «таблица рёбер», определить, является ли данный граф гамильтоновым, используя алгоритм с возвратом. Если да, то достаточно ограничиться одним вариантом гамильтонова цикла (записи в списках инцидентности вершин полагать упорядоченными по возрастанию номеров вершин). Отчёт должен содержать:

a) текст входного файла и графическое представление графа;

b) дерево построения гамильтонова цикла;

c) порядок обхода вершин гамильтонова цикла (если он существует).

ПРИЛОЖЕНИЯ

Приложение 1

Вариант 1

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (A \ B) È (B \ C) È (C \ A) È (A Ç B Ç C) = A È B È C.

3. [(A₁\ A₂) D (B₁\ B₂)] Í [(A₁D B₁) È (A₂D B₂)].

4. Вытекает ли из A \ B = C, что A = B È C?

Вариант 2

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. A \ (BÈ C) = (A \ B)Ç (A \ C)

3. [(A₁È A₂ È ... È A_n) D (B₁È B₂È ... È B_n)] Í

Í [(A₁D B₁) È (A₂D B₂) È ... È (A_nD B_n)].

4. A Í B Þ (A \ C) Í (B \ C)

Вариант 3

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (A \ B)Ç (A \ C) = (A \ B) \ C

3. [( ) \ ( )] Í .

4. A Í B Þ (C \ B) Í (C \ A)

Вариант 4

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (A \ B) \ C = (A \ C) \ (B \C).

3. [(A È B) D (C È D)] Í [(A D C) È (B D D)].

4. A Í B Þ (A Ç C) Í (B Ç C)

Вариант 5

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (AÈ B) \ C = (A \ C) È (B \ C).

3. [(A È B) D F] Í [(A D F) È (B D F)];

4. A Í B Þ (A È C) Í (B È C)

Вариант 6

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. A \ (B \ C) = (A \ B) È (A Ç C).

3. A D B Í [(A D C) È (B D C)]

4. B Í A Þ (A \ B) È B = A

Вариант 7

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. .A \ B = A D (A Ç B).

3. A D B Í [(A D C) È (B D C)]

4. (A Ç B) È C = A Ç (B È C) Û C Í A

Вариант 8

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. A D (A D B) = B

3. [(A Ç C) È (B Ç D)] Í [(A È B) Ç (C È D)]

4. A Í (B È C) Û (A Ç C(B)) Í C

Вариант 9

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. A È B = A D B D (A Ç B)

3. A \ C Í [(A \ B) È (B \ C)]

4. Вытекает ли из A = B È C, что A \ B = C?

Вариант 10

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. A \ (BÈ C) =(A \ C) \ (B \C).

3. [ (B \ C) \ (B \ A) ] Í A \ C.

4. (A Ç B) Í C Û A Í C(B) È C

Вариант 11

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (AÇ B) È (CÇ D) = (AÈ C) Ç (BÈ C) Ç (AÈ D) Ç (BÈ D)

3. [(A₁Ç A₂ Ç ... Ç A_n) D (B₁Ç B₂Ç ... Ç B_n)] Í

Í [(A₁D B₁)È (A₂D B₂)È...È (A_nD B_n)]

4. A D B = Æ Û A = B

Вариант 12

1. , , . Найти:

a) ;

b) ;

, , . Найти:

c) ;

d) .

2. C[C(X È Y) Ç (C(X) È C(Y)) = X È Y

3. [(A₁È A₂ È ... È A_n) D (B₁È B₂È ... È B_n)] Í

Í [(A₁D B₁) È (A₂D B₂) È ... È (A_nD B_n)]

4. A Ç B = Æ Þ A È B = A D B

Вариант 13

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (A Ç B) È (A Ç C(B)) È (C(A) Ç B) = A È B

3. [(A₁Ç A₂ Ç ... Ç A_n) D (B₁Ç B₂Ç ... Ç B_n)] Í

Í [(A₁D B₁) È (A₂D B₂) È ... È (A_nD B_n)].

4. A D B = C Û B D C = A

Вариант 14

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. (A Ç B) È (A Ç C(B)) = (A È B) Ç (A È C(B)) = A

3. [(A₁\ A₂) D (B₁\ B₂)] Í [(A₁D B₁) È (A₂D B₂)].

4. B D C = A Û C D A = B

Вариант 15

1. , , . Найти:

a) ;

, , . Найти:

c) ;

2. C[C(C(X) È Y) È (X È C(Y))] = Y \ X

3. A D B Í [(A D C) È (B D C)]

4. A D B = C Û C D A = B

Приложение 2

Вариант 1

1. «Высокий».

2. «Надорогая марка»

X = {Lada, Audi, Toyota, Hyundai, Mazda, Renault}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/2	1/5	2/3	2/5
B	1/4		3/5	7/8
C		2/5	5/7	1/3	1/2

Найти:

a) ;

c) .

Вариант 2

1. «Нищий».

2. «Образовательный журнал»

X = {«Вокруг света», «Караван историй», «За рулем», «Наука и жизнь», «Cosmopolitan»}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 7		0, 3		0, 8
B		0, 3	0, 4	0, 6	0, 1
C	0, 7		0, 9	0, 8	0, 3

Найти:

a) ;

b) ;

Вариант 3

1. «Среднего возраста».

2. «Познавательный отдых»

X = {Анталья, Афины, Хельсинки, Санкт-Петербург, Париж, Москва}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/5		2/5	1/3	4/5
B	5/6	1/3		4/5	1/3
C		1/2	1/4	3/5	2/3

Найти:

a) ;

b) ;

Вариант 4

1. «Низкорослый».

2. «Немного»

X = {3, 5, 7, 10, 12, 15}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 1	0, 5	0, 9	0, 7	0, 3
B		0, 7	0, 8		0, 2
C	0, 7	0, 2	0, 4	0, 5

Найти:

a) ;

b) ;

Вариант 5

1. «Пора замуж».

2. «Высокоплачиваемая профессия»

X = {художник, учитель, адвокат, врач, инженер, менеджер}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	2/3	1/3	0, 1	5/7	4/7
B	1/4	1/2	7/8	5/6	2/5
C	4/5		4/7	1/3	2/7

Найти:

a) ;

c) .

Вариант 6

1. «Средний класс» (по доходам)».

2. «Экологичный отдых»

X = {Байкал, Москва, Анталья, Барселона, Камчатка, Сочи}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/2	1/5	2/9	2/5
B	1/7		3/5	5/8
C		2/5	5/7	1/3	1/2

Найти:

a) ;

c) .

Вариант 7

1. «Старый».

2. «Несколько»

X = {2, 3, 4, 5, 6, 7, 9}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 7		0, 5		0, 8
B	0, 1	0, 3	0, 4	0, 7	0, 1
C	0, 7		0, 9	0, 8	0, 6

Найти:

a) ;

c) .

Вариант 8

1. «Малооплачиваемый».

2. «Престижный автомобиль»

X = {Renault Logan, Mazda 6, Lada Priora, Lexus GS, Audi S4, Chevrolet Cruse}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/5		2/5	1/4	4/5
B	1/6	1/3		4/5	1/4
C		1/2	1/4	3/5	2/3

Найти:

a) ;

b) ;

Вариант 9

1. «Среднего роста».

2. «Сторожевая собака»

X = {пудель, колли, чау-чау, московская сторожевая, питбультерьер, пекинес}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 1	0, 5	0, 9	0, 7	0, 3
B		0, 7	0, 3		0, 2
C	0, 7	0, 2		0, 8

Найти:

a) ;

b) ;

Вариант 10

1. «Высокооплачиваемый».

2. «Престижная профессия»

X = {художник, учитель, адвокат, врач, инженер, менеджер}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	2/3	1/3	0, 2	5/7	4/7
B	1/4	1/2	7/8	5/6	3/5
C	4/5		4/7	1/3	2/7

Найти:

a) ;

b) ;

Вариант 11

1. «Пора жениться».

2. «Женский автомобиль»

X = {Daewoo Matiz, УАЗ Patriot, Ford Focus, Mazda 6, Hundai Gets, Lexus Lx}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/2	1/5	2/3	2/5
B	1/4		3/5	7/8
C		2/5	5/7	1/3	1/2

Найти:

a) ;

c) .

Вариант 12

1. «Пожилой».

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 7		0, 3		0, 8
B		0, 3	0, 4	0, 6	0, 1
C	0, 7		0, 9	0, 8	0, 3

Найти:

a) ;

c) .

Вариант 13

1. «Большая квартира»

2. «Популярный писатель»

X = {Н. Гоголь, Ф. Достоевский, В. Набоков, А. Дюма, Д. Дефо, В. Гюго}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	1/5		2/5	1/3	4/5
B	5/6	1/3		4/5	1/3
C		1/2	1/4	3/5	2/3

Найти:

a) ;

b) ;

Вариант 14

1. «Близко»

2. «Дорогая марка»

X = {Audi, Land Rover, Renault, Lexus, Ford, Mercedes-Benz}

Множество	Степень принадлежности элемента
x₁	x₂	x₃	x₄	x₅
A	0, 1	0, 5	0, 9	0, 7	0, 3
B		0, 7	0, 8		0, 2
C	0, 7	0, 2	0, 4	0, 5

Найти:

a) ;

b) ;

Приложение 3

Варианты заданий

1. Написать программу разгадки числового ребуса

П Р О П: О = Р Ц И Я

2. Написать программу разгадки числового ребуса

С С С Р = Р ^Ф

3. Написать программу разгадки числового ребуса

(М + О + С + К + В + А) ⁴ = М О С К В А

4. Написать программу генерации m-последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число единиц должно быть чётно (включая 0 единиц);

2) число нулей должно быть не меньше числа единиц.

5. Написать программу генерации m-последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число единиц должно быть не меньше m / 2 - 2;

2) хотя бы 2 единицы шли подряд.

6. Написать программу генерации m-последовательностей 0 и 1, удовлетворяющих обоим требованиям:

1) число нулей должно быть не больше m / 2 + 2;

2) никакие 2 нуля не шли подряд.

7. Написать программу, которая генерирует все k-значные числа, не содержащие одинаковых цифр, кратные 2 и 3 (k£ 10).

8. Написать программу, которая генерирует все k-значные числа, не содержащие цифр 5 и 7 (k£ 10).

9. Написать программу, которая генерирует все k-значные числа, не содержащие одинаковых цифр и имеющие цифры 3, 5 и 7 (k£ 10).

10. Составить программу вычисления определённого интеграла произвольной кратности по прямоугольной области по формуле правых прямоугольников. С её помощью вычислить

11. Написать программу раскрытия полиномиальной формулы .

12. Написать программу для формулы включения и исключения. С её помощью определить количество натуральных чисел меньше или равных m, не делящихся ни на одно из заданных k чисел .

13. Написать программу, которая генерирует слова, содержащие k букв из последних k букв алфавита, допускающие повторения букв, но никакие 2 соседние буквы не повторяются и 1-я не совпадает с последней.

14. Написать программу, которая генерирует слова, содержащие k различных букв из первых k+5 букв алфавита таких, что код 1-й буквы не превосходит кода последней.

15. Дана матрица расстояний между населенными пунктами. Решить задачу коммивояжера, т. е. построить маршрут, проходящий точно 1 раз через все населенные пункты и возвращающийся в начальный, суммарное расстояние которого минимально.

Приложение 4

Вариант 1

Задание 1.

x₁	x₂	x₃	f

Вариант 2

Задание 2.

x₁	x₂	x₃	f

Вариант 3

Задание 3.

x₁	x₂	x₃	f

Вариант 4

Задание 4.

x₁	x₂	x₃	f

Вариант 5

Задание 1.

x₁	x₂	x₃	f

Вариант 6

Задание 2.

x₁	x₂	x₃	f

Вариант 7

Задание 3.

x₁	x₂	x₃	f

Вариант 8

Задание 4.

x₁	x₂	x₃	f

Вариант 9

Задание 1.

x₁	x₂	x₃	f

Вариант 10

Задание 2.

x₁	x₂	x₃	f

Вариант 11

Задание 3.

x₁	x₂	x₃	f

Вариант 12

Задание 4.

x₁	x₂	x₃	f

Вариант 13

Задание 1.

x₁	x₂	x₃	f

Вариант 14

Задание 2.

x₁	x₂	x₃	f

Вариант 15

Задание 3.

x₁	x₂	x₃	f

Приложение 5

X = {2, 3, 5, 6, 7, 10, 12, 13, 14, 17, 18, 20} – для нечетных вариантов,

X = {1, 3, 4, 5, 6, 8, 9, 11, 12, 15, 16, 17, 18} – для четных вариантов.

Варианты заданий

a) нижние срезы четных элементов;

b) антисимметричность и слабая полнота.

a) верхние срезы элементов, номера которых четны;

b) асимметричность и полнота.

a) нижние срезы элементов, номера которых нечетны;

b) антирефлексивность и негатранзитивность.

a) верхние срезы нечетных элементов;

b) рефлексивность и транзитивность.

a) нижние срезы элементов, кратных 3;

b) симметричность и полнота.

a) верхние срезы элементов, номера которых являются удвоенными четными;

b) слабая полнота и транзитивность.

a) нижние срезы элементов, номера которых кратны 3;

b) антисимметричность и негатранзитивность.

⇐ Предыдущая 1 2 34