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

Как уже отмечалось выше, любой неориентированный граф 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 (⁺(x_j) = ^–(x_j)).

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

Теорема 17.8. Пусть D — сильно связный граф. Если x_i  X (⁺(x_j)  n / 2 и ^–(x_j)  n / 2)  D, то D – гамильтонов граф.

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

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

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

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

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

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

Пусть задан ориентированный граф 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 можно перевести в орграф путем замены каждого ребра двумя противоположно направленными дугами. В этой связи многие результаты для неорграфов могут быть интерпретированы на орграфы.