Главная Промышленная автоматика.



Рис. 5.35.

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

5.5. Постройте с помощью поиска в глубину остовный лес для ориентированного графа на рис. 5.34. Затем найдите сильно связные компоненты.

5.6. Найдите двусвязные компоненты графа на рис. 5.36.

5.7. С помощью поиска в глубину разработайте эффективные алгоритмы, которые

(а) разбивают неориентированный граф на его связные ко...-поненты,

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


Рис. 5.36.



(в) Проверяют, ацикличен ли ориентированный граф,

(г) находят такой порядок узлов ациклического ориентированного графа, при котором v<.w, если из v в w ведет путь ненулевой длины,

(д) выясняют, можно ли так ориентировать ребра связного неориентированного графа, чтобы получить сильно связный ориентированный граф. Указание: Покажите, что это можно сделать тогда и только тогда, когда удаление из G любого ребра оставляет граф связным.

5.8. Пусть G== (У, Е) - мультиграф (т. е. ориентированный граф, у которого между двумя данными узлами может быть более одного ребра). Напишите алгоритм сложности 0(£), который удаляет каждый узел v степени 2 (заменяя ребра (и, v) и (у, w) ребром {и, w)) и уничтожает кратные ребра (заменяя их одним ребром). Заметим, что замена кратных ребер одним ребром может привести к образованию узла степени 2, который затем следует удалить. Аналогично удаление узла степени 2 может привести к образованию кратных ребер, которые затем надо уничтожить.

5.9. Эйлеровым циклом в неориентированном графе называется путь, который начинается и кончается в одном и том же узле и проходит по каждому ребру точно один раз. Связный неориентированный граф G имеет эйлеров цикл тогда и только тогда, когда степень каждого узла четна. Постройте алгоритм сложности 0(e) для нахождения эйлерова цикла в графе с е ребрами при условии, что такой цикл существует.

*5.10. Пусть 0=(У, £) - двусвязный неориентированный граф и (у, w) - его ребро. Пусть G=- ({у, w), {(у, хю)}). Укажите способ выполнения в префиксном режиме последовательности операций НАЙТИ ПУТЬ (s, t), где s - узел графа G, а (s, t) - ребро графа G, но неО. НАЙТИ ПУТЬ (s, t) выполняется так: находим простой путь в G, начинающийся с ребра (s, t) и кончающийся в некотором узле графа G, отличном от s, и добавляем узлы и ребра этого пути к G. Время выполнения любой последовательности должно быть 0(£).

5.11. Для ориентированного графа G на рис. 5.37 найдите

(а) транзитивное замыкание,

(б) длину кратчайшего пути между каждой парой узлов (стоимости ребер приведены на рис. 5.37;

*5.12. Найдите замкнутое полукольцо из четырех элементов.

*5.13. Транзитивная редукция ориентированного графа G=(y, Е) определяется как произвольный граф G=(y, Е) с минимально возможным числом узлов, транзитивное замыкание которого совпадает с транзитивным замыканием графа G. Покажите, что если граф G ацикличен, то его транзитивная редукция единственна.




Рис. 5.37.

**5.14. Покажите, что время R(n) вычисления транзитивной редукции ациклического графа с п узлами имеет тот же порядок, что и время Т{п) вычисления транзитивного замыкания, если принять (разумное) допущение, что 8R in)R i2n)iR (п) и 8Т(п)>Т(2п)> >4Т(п).

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

*5.16. Докажите то же, что и в упр. 5.15, для транзитивного замыкания.

*5.17. Пусть А будет (/гХп)-матрицей над замкнутым полукольцом {О, 1}. Не используя интерпретации на графах, докажите, что

(а) Л* = /„ + Л+ + -f Л», [А Ву /А* Л*БC*

Указание: Покажите, что

/Л А-В + А1-ВС+...+ВС-\ \0 С

Го ch





0 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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021