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

3. Выполняется поиск в глубину на графе начиная с вершины с наибольшим номером, присвоенным на шаге 1. Если проведенный поиск не охватывает всех вершин, то начинается новый поиск с вершины, имеюшей наибольший номер среди оставшихся вершин.

4. Каждое дерево в полученном остовном лесу является сильно связной компонентой графа G.

Пример 6.18. Применим описанный алгоритм к ориентированному графу, представленному на рис. 6.23. Прохождение вершин графа начнем с вершины а и затем перейдем на вершину Ъ. Присвоенные после завершения шага 1 номера вершин показаны на рис. 6.26. Полученный путем обрашения дуг граф G, представлен на рис. 6.27.

Выполнив поиск в глубину на графе получим глубинный остовный лес, показанный на рис. 6.28. Обход остовного леса мы начинаем с вершины а, принимаемой в качестве корня дерева, так как она имеет самый высокий номер. Из корня а можно достигнуть только вершины с и Ь. Следующее дерево имеет только корень d, поскольку вершина d имеет самый высокий номер среди оставшихся (но она и единственная оставшаяся вершина). Каждое из этих деревьев формирует отдельную сильно связанную компоненту исходного графа G. □



Рис. 6.26. Номера вершин после выполнения шага 1 алгоритма

Рис. 6.27. Граф

Рис. 6.28. Глубинный остовный лес

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

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

Теперь предположим, что вершины v и w принадлежат одному и тому же остовному дереву в глубинном остовном лесу графа G. Покажем, что они принадлежат одной и той же сильно связной компоненте. Пусть х - корень остовного дерева, которому принадлежат вершины v и w. Поскольку вершина v является потомком вершины X, то в графе <3, сушествует путь от вершины х к вершине i>, а в графе G - путь от вершины V к вершине х.

В соответствии с прохождением вершин графа G, методом поиска в глубину вершина V посешается позднее, чем вершина х, т.е. вершина х имеет более высокий номер, чем вершина v. Поэтому при обходе графа G рекурсивный вызов процедуры dfs для вершины V заканчивается раньше, чем вызов dfs для вершины х. Но если при обходе графа G вызывается процедура dfs для вершины о, то из-за наличия пути от



вершины V к вершине х процедура dfs для вершины х начнется и закончится до окончания процедуры dfs(v), и, следовательно, вершинах получит меньший номер, чем вершина и. Получаем противоречие.

Отсюда заключаем, что при обходе графа G вершина v посещается при выполнении dfs(x) и поэтому верщина о является потомком вершины х. Следовательно, в графе G существует путь от вершины х к вершине v. Более того, так как существует и путь от вершины v к вершине х, то вершины х и v принадлежат одной сильно связной компоненте. Аналогично доказывается, что вершины х и ц> принадлежат одной сильно связной компоненте. Отсюда вытекает, что и вершины d и w принадлежат той же сильно связной компоненте, так как существует путь от вершины v к верщине w через вершину х и путь от вершины w к вершине v через вершину х.

Упражнения

6.1. Представьте граф, изображенный на рис. 6.29, посредством

а) матрицы смежности, содержащей стоимости дуг;

б) связанных списков смежности, показывающих стоимость дуг.


Рис. 6.29. Ориентированный граф с помеченными дугами

6.2. Постройте математическую модель для следующей задачи составления календарного плана работ. Есть множество задач 7*1, Т2, Т,, для выполнения которых необходимо время ti, t2, t,, и множество отношений вида "задача Т, должна закончиться до начала задачи Т". Найдите минимальное время, необходимое для выполнения всех задач.

6.3. Выполните реализацию операторов EIRST, NEXT и VERTEX для орграфов, представленных посредством

а) матриц смежности;

б) связанных списков смежности;

в) списков смежности, показанных на рис. 6.5.

6.4. Для графа, показанного на рис. 6.29, используйте

а) алгоритм Дейкстры для нахождения кратчайших путей от вершины а до остальных верщин;

б) алгоритм Флойда для нахождения кратчайших путей между всеми парами верщин.

6.5. Напищите законченную программу алгоритма Дейкстры, используя связанные списки смежности и очередь с приоритетами, реализованную посредством частично упорядоченного дерева.



*6.6. Покажите, что алгоритм Дейкстры работает неправильно, если стоимости дуг могут быть отрицательными.

**6.7. Покажите, что алгоритм Флойда работает корректно, если некоторые дуги имеют отрицательную стоимость, но нет циклов, состоящих из дуг с отрицательными стоимостями.

6.8. Полагая, что вершины графа из рис. 6.29 упорядочены как а, Ъ, /, постройте глубинный остовный лес. Укажите дуги дерева, прямые, обратные и поперечные, а также подсчитайте глубинные номера вершин.

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

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

*6.И. Пусть ациклический орграф имеет е дуг. Зафиксируем две различные вершины * и f этого графа. Постройте алгоритм с временем выполнения 0(е) для нахождения максимального множества вершин, составляющих пути от вершины S к вершине t.

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

6.13. Постройте алгоритм чтения, арифметических выражений, представленных в виде ациклического орграфа.

6.14. Напишите программу нахождения самого длинного пути в ациклическом орграфе. Какова временная сложность этого алгоритма?

6.15. Найдите сильно связные компоненты графа, представленного на рис. 6.29.

*6.16, Докажите, что редуцированный граф строго связных компонент (см. раздел 6.7) обязательно должен быть ациклическим орграфом.

6.17. Нарисуйте первый остовный лес, обратный граф и второй остовный лес в процессе определения сильно связных компонент орграфа, показанного на рис. 6.29.

6.18. Реализуйте алгоритм нахождения сильно связных компонент, рассмотренный в разделе 6.7.

*6.19. Покажите, что алгоритм нахождения сильно связных компонент требует времени порядка 0(e) на ориентированном графе, имеющем е дуг и п вершин, если п < е.

*6.20. Напишите программу, на входе которой задается орграф и две его вершины. Программа должна распечатывать все простые пути, ведущие от одной вершины к другой. Какова временная сложность (время вьшолнения) этой программы?

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

*6.22. Напишите программу нахождения транзитивной редукции орграфа. Какова временная сложность этой программы?





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

0.0019