Решение стандартных графовых задач с использованием орграфов

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

Маршрутом графа D считается чередующаяся последовательность вершин и дуг (x ₀, u ₁, x ₁, u_n, х_n), в которой каждая дуга u_i есть кортеж u_i = < x_{i -1}, x_i >. Маршрут, в котором все вершины различны, называется путем. Замкнутый маршрут, у которого все вершины различны, за исключением первой и последней, называется контуром. Если существует путь из x_i в x_j, то говорят, что x_j достижима из x_i.

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

Неорграф G называется ориентируемым, если каждое его ребро можно ориентировать так, что полученный граф D будет сильно связным. Такой процесс обычно называют заданием ориентации графа G. Очевидно, что произвольный эйлеров граф может быть ориентируем, так как достаточно пройти по любой эйлеровой цепи, ориентируя ребра графа в направлении движения.

Граф D называется эйлеровым, если в нем существует замкнутая цепь, содержащая каждую его дугу.

Необходимым условием существования эйлерова орграфа является его сильная связность.

Связный граф D = (X, U) является эйлеровым, когда " x_i Î X (r ⁺(x_j) = r ^–(x_j)).

Орграф называется гамильтоновым, если в нем существует контур, содержащий каждую вершину орграфа.

Теорема 17.8. Пусть D — сильно связный граф. Если " x_i Î X (r ⁺(x_j) ³ n / 2 и r ^–(x_j) ³ n / 2) Þ D, то D – гамильтонов граф.

Рассмотрим алгоритм построения дерева на ориентированном графе D = (X, U).

1. Выбираем произвольную вершину x_i и по матрице смежности определяем все смежные ей вершины (т. е. определяем вершины, соответствующие стрелкам, исходящим из x_i). В результате образуется подмножество вершин X’ = { x_i, x_j,..., x_u }, смежных с х_i. В случае, если X’ = X, то переходим к пункту 4, в противном случае переходим к пункту 2.

2. Выбираем произвольную вершину x_j Î X’, такую, что x_j ¹ x_i. Снова определяем все смежные с x_j вершины, за исключением вершин, уже вошедших в X’.

3. Проверка условия çX’ï = çXï, если условие выполняется - то переход к пункту 4, в противном случае - переход к пункту 2.

4. Конец работы алгоритма, построено дерево Т.

Выделение сильносвязных компонент

Пусть задан ориентированный граф D = (X, U), где X, U - соответственно множество вершин и множество ребер графа. Граф D называется сильносвязным, если любые две его вершины взаимно достижимы. Подграфом D’ графа D называется граф, все вершины которого и инцидентные им ребра принадлежат D, т.е. D’ = (X’, U’), X’ Í X и U’ Í U, и ребра D’ инцидентны только вершинам из X’.

Граф G, полученный из графа D заменой каждой дуги u_i = < x_k, x_l > на соответствующее ребро u_i = (x_k, x_l), т.е. устранением стрелок, называется основанием D.

Тогда максимально сильносвязный подграф графа D будем называть сильной компонентой графа D. Отметим, что в ориентированном графе существует одна и только одна сильная компонента, содержащая данную вершину x_i.

Множество вершин R(x_i) графа D, достижимых из некоторой вершины x_i, состоит из таких элементов x_j, для которых (i, j) элемент в матрице достижимости R = || r_ij || равен 1. Матрица контрдостижимости определяется как Q = R^t, где R^t - матрица, транспонированная к матрице достижимости R.

Если вершина x_i одновременно является начальной и конечной вершиной пути, то множество вершин некоторого цикла, содержащего x_i, совпадает с пересечением [R(x_i) Ç Q(x_i)] и все они взаимно достижимы.

В случае удаления этих вершин из исходного графа, в оставшемся порожденном графе D’ = < x - R(x_i) Ç Q(x_i)> таким же способом выделяется новая сильная компонента, содержащая x_j Î < x - R(x_i) Ç Q(x_i)>. Этот процесс продолжается до тех пор, пока весь исходный граф не будет разбит на сильные компоненты.

Граф D^* = (X^*, U^*) называется конденсацией графа D и определяется следующим образом: каждая его вершина представляет множество вершин некоторой сильной компоненты графа D, дуга < x_i ^*, x_j ^*> существует в D^* тогда и только тогда, когда в графе D существует дуга < x_i, x_j >, такая, что x_i принадлежит компоненте, соответствующей вершине x_i ^*, а x_j - компоненте, соответствующей вершине x_j ^*. Очевидно, что конденсация графа D не содержит циклов, поскольку наличие цикла означает, что любые вершины этого цикла взаимно достижимы.

Определим прямое и обратное транзитивные замыкания. Прямым транзитивным замыканием Г⁺(x_i) называют подмножество вершин Х' Í Х, в которые можно попасть из вершины x_i по некоторому пути. Обратным транзитивным замыканием называют подмножество вершин, из которых можно попасть в x_i по некоторому пути, и обозначают Г^–(x_i).

Прямое и обратное транзитивное замыкания можно найти из соотношений:

Г⁺(x_i) = { х_i } È Г⁺(x_i) È Г⁺²(x_i) È Г⁺³(x_i) È...,

Г^–(x_i) = { x_i } È Г^-1(x_i) È Г^-2(x_i) È Г^-3(x_i) È...,

Г⁺²(x_i) = Г⁺{Г(x_i)};

Г⁺³(x_i) = Г⁺{Г⁺²(x_i)} = Г⁺{Г⁺{Г⁺(x_i)}}.

Аналогично определяем для Г^–2(x_i), Г^–3(x_i) и т.д.

Опишем алгоритм Мальгранжа разбиения графа D на максимально связные подграфы.

Идея алгоритма заключается в следующем. Выбирается произвольная вершина x_i Í Х в графе D, для которой определяются прямое и обратное транзитивные замыкания Г⁺(x_i), Г^–(x_i). Их пересечение C(x_i) = Г⁺ х_i Ç Г^– х_i является сильной компонентой графа D, т.е. максимально связным подграфом. Далее выбирается следующая вершина x_j Ï C(x_i) и процесс продолжается.

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