Двумя естественными примерами отношений частичного порядка могут служить отношение "меньше чем" (обозначается знаком "<"), заданное на множестве целых чисел, и отношение строгого включения (с) множеств.

Пример 6.14. Пусть S = {1, 2, 3} и P(S) - множество всех подмножеств множества S, т.е. P(S) = {0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3), {1, 2, 3}}. Отношение строгого включения (с) является отношением частичного порядка на множестве P{S). Очевидно, включение А сА не выполняется для любого множества А из Р (антирефлексивность), и при выполнении А с В и В <zC выполняется А с С (транзитивность). □

Ациклические орграфы можно использовать для графического изображения отношения частичного порядка между какими-либо объектами. Для начала можно представить отношение R как одноименное множество пар (дуг) таких, что пара (а, Ь) принадлежит этому множеству только тогда, когда выполняется aRb. Если отношение R определено на множестве элементов S, то ориентированный граф G = (S, R) будет ациклическим. И наоборот, пусть G = (S, R) является ациклическим орграфом, а R* - отношение, определенное следующим образом: aR*b выполняется тогда и только тогда, когда сушествует путь (длиной не менее 1) от вершины а к вершине Ь. Тогда - отношение частичного порядка на S. (Отношение J? является транзитивным замыканием отношения R.)

Пример 6.15. На рис. 6.20 показан ациклический орграф (P(S), R), где S = {1, 2, 3}. Здесь i? - отношение строгого включения на множестве P(S). □

{1,2}

{2,3}

Рис. 6.20. Ациклический орграф, представляющий отношение строгого включения

Проверка ацикличности орграфа

Предположим, что есть ориентированный граф G = (V, Е) и мы хотим определить, является ли он ациклическим, т.е. имеет ли он циклы. Чтобы ответить на этот вопрос, можно использовать метод поиска в глубину. Если при обходе орграфа G методом поиска в глубину встретится обратная дуга, то ясно, что граф имеет цикл. С другой стороны, если в орграфе есть цикл, тогда обратная дуга обязательно встретится при обходе этого орграфа методом поиска в глубину.

Чтобы доказать это, предположим, чт9 орграф G имеет цикл. Пусть при обходе данного орграфа методом поиска в глубину вершина v имеет наименьшее глубинное число среди всех вершин, составляюших цикл. Рассмотрим дугу м -> у, принадлежащую этому циклу. Поскольку верщина и входит в цикл, то она должна быть потомком верщины V в глубинном остовном лесу. Поэтому дуга и -> i? не может быть поперечной дугой. Так как глубинный номф вершины и больше глубинного номера верщины V, то отсюда следует, что эта дуга не может быть дугой дерева и прямой дугой. Следовательно, дуга и v является обратной дугой, как показано на рис. 6.21.

Топологическая сортировка

Большие проекты часто разбиваются на совокупность меньших задач, которые выполняются в определенном порядке и обеспечивают полное завершение целого проекта. Например, план учебного заведения требует определенной последовательности в чтении учебных курсов. Ациклические орграфы могут служить естественной моделью для таких ситуаций. Например, мы создадим дугу от учебного курса С к учебному курсу D тогда, когда чтение курса С предшествует чтению курса D.

Пример 6.16. На рис. 6.22 показан ациклический орграф, представляющий структуру предшествований пяти учебных курсов. Чтение учебного курса СЗ, например, требует предварительного чтения курсов С1 и С2. □

Рис. 6.21. Каждый цикл Рис. 622. Ациклический орграф, представ

содержит, обратную дугу ляющий структуру предшествований

Топологическая сортировка - это процесс линейного упорядочивания вершин ациклического орграфа таким образом, что если существует дуга от вершины г к вершине /, то в упорядоченном списке вершин орграфа вершина i предшествует вершине j. Например, для орграфа из рис. 6.22 вершины после топологической сортировки расположатся в следующем порядке: С1, С2, СЗ, С4, С5.

Топологическую сортировку легко выполнить с помощью модифицированной процедуры листинга 6.8, если в ней после строки (4) добавить оператор вывода на печать:

procedure topsort ( v-. вершина ) ;

{ печать в обратном топологическом порядке вершин, достижимьк из вершины v }

w, вершина ,-begin

marklv] := visited;

for каждая вершина w из списка L[v] do if jnaric[ftr] = unvisited then topsort (1с) ; viti teln (v) end; { topsort }

Когда процедура topsort заканчивает поиск всех вершин, являющихся потомками вершины V, печатается сама вершина V. Отсюда следует, что процедура topsort рас-печатьтает все вершины в обратном топологическом порядке.

Эта процедура работает вследствие того, что в ациклическом орграфе нет обратных дуг. Рассмотрим, что происходит, когда поиск в глубину достигает конечной

вершины X, Из любой вершины могут исходить только дуги дерева, прямые и поперечные дуги. Но все эти дуги направлены в вершины, которые уже пройдены (посешались до достижения вершины х), и поэтому предшествуют вершине х.

6.7. Сильная связность

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

Дадим точную формулировку понятия сильной связности. Пусть G = (V, Е) - ориентированный граф. Множество вершин V разбивается на классы эквивалентности V,, \ < i < г, так, что вершины v и и> будут эквивалентны тогда и только тогда, когда существуют пути из вершины v в вершину w и из вершины w в вершину v. Пусть Е,, 1 < i < г, - множество дуг, которые начинаются и заканчиваются в множестве верщин У,. Тогда графы G, = (У,, Е,) называются сильно связными компонентами графа 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. Сначала выполняется поиск в глубину на графе G. Вершины нумеруются в порядке завершения рекурсивно вызванной процедуры dfs, т.е. присвоение номеров верщинам происходит после строки (4) в листинге 6.8.

2. Конструируется новый ориентированный граф путем обращения направления всех дуг графа G.