Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 [ 78 ] 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


Рис. 9.14. (а) - граф G. (б) - реберный граф б;.

Задача выяснения существования у данного неориентированного графа G гамильтонова цикла, а также нахождения такого цикла, если он существует, является важной задачей теории графов как с практической, так и с теоретической точек зрения. Если ребрам гпафа G приписаны некоторые веса [cij] и граф G



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

6. Задачи

1. Для неориентированного графа, изображенного на рис. 9.15, найти цикломатическое и коцикломатическое числа, а также фундаментальные циклы относительно некоторого остовного дерева.


Рис. 9.15.

2. Для графа, изображенного на рис. 9.15, выписать соответственно матрицы Ф и К фундаментальных циклов и фундаментальных разрезов и на этом примере проверить справедливость теорем 2 и 3.

3. Используя теорему 2, получить выражение для матрицы фундаментальных циклов в терминах матрицы инциденций В.

4. Доказать, что множество К ребер неориентированного графа, такое, что К имеет четное число ребер, общих с каждым циклом, является разрезом (не необходимое свойство).

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

6. Если столбцы матриц В, Ф и К записаны с использованием одного и того же порядка ребер (относительно некоторого остовного дерева, по которому образованы фундаментальные циклы и разрезы) и затем представлены в виде В = [Вц, Bij], Ф =



= [I, Ф12] И К = [Кц, I], ТО

= Ф*, = .Ф = [Ф* I] = вг, .в.

Следовательно, по любой из трех матриц В, Ф и К можно найти остальные.

7. Показать, что алгоритм Флёри всегда позволяет найти эйле ров цикл графа, если таковой существует.

8. Написать алгоритм, основанный на алгоритме Флёри и позволяющий найти все эйлеровы циклы графа.

9. Показать, что для ориентированного графа G = (X, А) с полустепенями {Xi) = df{Xi), Vx 6 X, число различных эйле ровых циклов дается выражением

Аг- П {do{Xi)-i)l,

где - число ориентированных остовных деревьев графа G с корнем Хг- Эта величина не зависит от выбора Хг (см. [24]).

10. Используя понятие эйлерова цикла, построить алгоритм обхода лабиринта от начальной точки s до конечной точки t.

ю 35

Рис. 9.16.

не проходящий ни по какому коридору дважды в одном направлении. Предполагается, что при обходе лабиринта пройденный путь не запоминается (память у путешественника отсутствует). Разрешается только использовать два типа меток (например, О и 1), чтобы помечать ими входы и выходы коридоров. (См. [23], [13] и ]14]).

11. Решить задачу китайского почтальона для взвешенного неориентированного графа, показанного на рис. 9.16. (Воспользоваться алгоритмом гл. 8 для нахождения кратчайшей цепи и решить задачу о паросочетании с помощью полного перебора.)



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 [ 78 ] 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95