Структуры данных и алгоритмы (1021739), страница 51
Текст из файла (страница 51)
Отсюда следует, что процедура topsort распечатывает все вершины в обратном топологическом порядке.Эта процедура работает вследствие того, что в ациклическом орграфе нет обратных дуг. Рассмотрим, что происходит, когда поиск в глубину достигает конечной202ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫвершины ж. Из любой вершины могут исходить только дуги дерева, прямые и поперечные дуги. Но все эти дуги направлены в вершины, которые уже пройдены(посещались до достижения вершины х), и поэтому предшествуют вершине х.6.7. Сильная связностьСильно связной компонентой ориентированного графа называется максимальноемножество вершин, в котором существуют пути из любой вершины в любую другуювершину.
Метод поиска в глубину можно эффективно использовать для нахождениясильно связных компонентов ориентированного графа.Дадим точную формулировку понятия сильной связности. Пусть G = (V, Е) —ориентированный граф. Множество вершин V разбивается на классы эквивалентности V,, 1 < i < г, так, что вершины v и w будут эквивалентны тогда и только тогда,когда существуют пути из вершины и в вершину w и из вершины w в вершину и.Пусть Е,, 1 < i < г, — множество дуг, которые начинаются и заканчиваются в множестве вершин V,, Тогда графы G, = (V,, Е,) называются сильно связными компонентами графа G. Ориентированный граф, состоящий только из одной сильно связнойкомпоненты, называется сильно связным.Пример 6*.17.
На рис. 6.23 представлен ориентированный граф с двумя сильносвязными компонентами, которые показаны на рис. 6.24. DОтметим, что каждая вершина ориентированного графа G принадлежит какойлибо сильно связной компоненте, но некоторые дуги могут не принадлежать никакойсильно связной компоненте. Такие дуги идут от вершины одной компоненты к вершине, принадлежащей другой компоненте. Можно представить связи между компонентами путем создания редуцированного (приведенного) графа для графа G.
Вершинами приведенного графа являются сильно связные компоненты графа G. В приведенном графе дуга от вершины С к вершине D существует только тогда, когда вграфе G есть дуга от какой-либо вершины, принадлежащей компоненте С, к какойлибо вершине, принадлежащей компоненте D. Редуцированный граф всегда являетсяациклическим орграфом, поскольку если бы существовал цикл, то все компоненты,входящие в этот цикл, в действительности были бы одной связной компонентой. Нарис. 6.25 показан редуцированный граф для графа из рис.
6.23.©Рис. 6.23. Ориентированный графРис. 624. Сильно связные компоненты орграфа из рис. 6.23Рис. 6.25. Редуцированный графТеперь рассмотрим алгоритм нахождения сильно связных компонент для заданного ориентированного графа G.1.2.Сначала выполняется поиск в глубину на графе G. Вершины нумеруются в порядке завершения рекурсивно вызванной процедуры dfs, т.е.
присвоение номеров вершинам происходит после строки (4) в листинге 6.8.Конструируется новый ориентированный граф G, путем обращения направлениявсех дуг графа G.6.7. СИЛЬНАЯ СВЯЗНОСТЬ2033.Выполняется поиск в глубину на графе Gr, начиная с вершины с наибольшимномером, присвоенным на шаге 1. Если проведенный поиск не охватывает всехвершин, то начинается новый поиск с вершины, имеющей наибольший номерсреди оставшихся вершин.4.
Каждое дерево в полученном остовном лесу является сильно связной компонентой графа G.Пример 6.18. Применим описанный алгоритм к ориентированному графу, представленному на рис. 6.23. Прохождение вершин графа начнем с вершины а и затемперейдем на вершину Ъ. Присвоенные после завершения шага 1 номера вершин показаны на рис. 6.26. Полученный путем обращения дуг граф G, представлен нарис. 6.27.Выполнив поиск в глубину на графе G,, получим глубинный остовный лес, показанный на рис.
6.28. Обход остовного леса мы начинаем с вершины а, принимаемойв качестве корня дерева, так как она имеет самый высокий номер. Из корня а можнодостигнуть только вершины с и Ь. Следующее дерево имеет только корень d, поскольку вершина d имеет самый высокий номер среди оставшихся (но она и единственная оставшаяся вершина). Каждое из этих деревьев формирует отдельную сильносвязанную компоненту исходного графа G. П—-0Рис.
6.26. Номера вершин после выполненияшага 1 алгоритмаРис. 6.27. Граф GrРис. 6.28. Глубинныйостовный лесВыше мы утверждали, что вершины строго связной компоненты в точности соответствуют вершинам дерева в остовном лесу, полученном при применении поиска вглубину к графу G,. Докажем это.Сначала покажем, что если вершины v и w принадлежат одной связной компоненте, то они принадлежат и одному остовному дереву. Если вершины v и w принадлежат одной связной компоненте, то в графе G существует путь от вершины v к вершине w и путь от вершины w к вершине v. Допустим, что поиск в глубину на графе<?, начат от некоторого корня х и достиг или вершины v, или вершины и>.
Посколькусуществуют пути (в обе стороны) между вершинами v и w, то обе они принадлежатостовному дереву с корнем х.Теперь предположим, что вершины v и w принадлежат одному и тому же остовному дереву в глубинном остовном лесу графа G. Покажем, что они принадлежат одной и той же сильно связной компоненте. Пусть х — корень остовного дерева, которому принадлежат вершины v и w. Поскольку вершина v является потомком вершины х, то в графе G, существует путь от вершины х к вершине и, а в графе G — путьот вершины v к вершине х.В соответствии с прохождением вершин графа G, методом поиска в глубину вершина v посещается позднее, чем вершина х, т.е. вершина х имеет более высокий номер, чем вершина v.
Поэтому при обходе графа G рекурсивный вызов процедуры dfsдля вершины v заканчивается раньше, чем вызов dfs для вершины х. Но если приобходе графа G вызывается процедура dfs для вершины и, то из-за наличия пути от204ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫвершины v к вершине ж процедура dfs для вершины х начнется и закончится доокончания процедуры dfs(v), и, следовательно, вершина х получит меньший номер,чем вершина и. Получаем противоречие.Отсюда заключаем, что при обходе графа G вершина v посещается при выполнении dfs(x) и поэтому вершина о является потомком вершины х.
Следовательно, вграфе G существует путь от вершины х к вершине и. Более того, так как существуети путь от вершины v к вершине х, то вершины х и v принадлежат одной сильносвязной компоненте. Аналогично доказывается, что вершины х и w принадлежат одной сильно связной компоненте. Отсюда вытекает, что и вершины и и w принадлежат той же сильно связной компоненте, так как существует путь от вершины и квершине w через вершину х и путь от вершины w к вершине и через вершину х.Упражнения6.1.
Представьте граф, изображенный на рис. 6.29, посредствома) матрицы смежности, содержащей стоимости дуг;б) связанных списков смежности, показывающих стоимость дуг.Рис. 6.29. Ориентированный граф с помеченными дугами6.2.6.3.6.4.6.5.Постройте математическую модель для следующей задачи составления календарного плана работ. Есть множество задач 5*i, T2, ..., Т,, для выполнения которых необходимо время t\, t2, ..., t,, и множество отношений вида "задача Т<должна закончиться до начала задачи Т".
Найдите минимальное время, необходимое для выполнения всех задач.Выполните реализацию операторов FIRST, NEXT и VERTEX для орграфов,представленных посредствома) матриц смежности;б) связанных списков смежности;в) списков смежности, показанных на рис. 6.5.Для графа, показанного на рис. 6.29, используйтеа) алгоритм Дейкстры для нахождения кратчайших путей от вершины а доостальных вершин;б) алгоритм Флойда для нахождения кратчайших путей между всеми парамивершин.Напишите законченную программу алгоритма Дейкстры, используя связанныесписки смежности и очередь с приоритетами, реализованную посредством частично упорядоченного дерева.УПРАЖНЕНИЯ205*6.6.Покажите, что алгоритм Дейкстры работает неправильно, если стоимости дугмогут быть отрицательными.**6.7.
Покажите, что алгоритм Флойда работает корректно, если некоторые дугиимеют отрицательную стоимость, но нет циклов, состоящих из дуг с отрицательными стоимостями.6.8. Полагая, что вершины графа из рис. 6.29 упорядочены как а, Ъ, ..., /, постройте глубинный остовный лес. Укажите дуги дерева, прямые, обратные и поперечные, а также подсчитайте глубинные номера вершин.*6.9. Пусть есть глубинный остовный лес и совершается обход составляющих егоостовных деревьев слева направо в обратном порядке. Покажите, что в этомслучае список вершин будет совпадать со списком вершин, полученных с помощью процедуры dfs, вызываемой при построении остовного леса.6.10. Корнем ациклического орграфа называется вершина г такая, что существуютпути, исходящие из этой вершины и достигающие всех остальных вершинорграфа. Напишите программу, определяющую, имеет ли данный ациклический орграф корень.*6.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
