Граф достижимости

Один из первых вопросов, возникающих при изучении графов, это вопрос о существовании путей между заданными или всеми парами вершин. Ответом на этот вопроc - введенное выше отношение достижимости на вершинах графа G=(V, E): вершина wдостижима из вершины v, если v = w или в G есть путь из v в w. Иначе говоря, отношение достижимости является рефлексивным и транзитивным замыканием отношения E. Для неориентированных графов это отношение также симметрично и, следовательно, является отношением эквивалентности на множестве вершин V. В неориентированном графе классы эквивалентности по отношению достижимости называются связными компонентами. Для ориентированных графов достижимость, вообще говоря, не должна быть симметричным отношением. Симметричной является взаимная достижимость.

Определение 9.8. Вершины v и w ориентированного графа G=(V, E) называются взаимно достижимыми, если в G есть путь из v в w и путь из w в v.

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

Рассмотрим вначале вопрос о построении отношения достижимости. Определим для каждого графа его граф достижимости (называемый иногда также графом транзитивного замыкания), ребра которого соответствуют путям исходного графа.

Определение 9.9. Пусть G=(V, E) - ориентированный граф. Граф достижимости G^*=(V, E^*) для G имеет то же множество вершин V и следующее множество ребер E^* ={ (u, v) | в графе G вершина v достижима из вершины u}.

Пример 9.3. Рассмотрим граф G из примера 9.2.

Рис. 9.2. Граф G

Тогда можно проверить, что граф достижимости G* для G выглядит так (новые ребра -петли при каждой из вершин 1-5 не показаны):

Рис. 9.3. Граф G*

Каким образом по графу G можно построить граф G^*? Один способ заключается в том, чтобы для каждой вершины графа Gопределить множество достижимых из нее вершин, последовательно добавляя в него вершины, достижимые из нее путям и длины 0, 1, 2 и т.д.

Мы рассмотрим другой способ, основанный на использовании матрицы смежности A_G графа G и булевых операций. Пусть множество вершин V={v₁,..., v_n}. Тогда матрица A_G - это булева матрица размера n x n.

Ниже для сохранения сходства с обычными операциями над матрицами мы будем использовать " арифметические" обозначения для булевых операций: через + будем обозначать дизъюнкцию а через x - конъюнкцию

Обозначим через E_n единичную матрицу размера n x n. Положим . Пусть . Наша процедура построения G^* основана на следующем утверждении.

Лемма 9.2. Пусть . Тогда

Доказательство проведем индукцией по k.

Базис. При k=0 и k=1 утверждение справедливо по определению и .

Индукционный шаг. Пусть лемма справедлива для k. Покажем, что она остается справедливой и для k+1. По определению имеем:

Предположим, что в графе G из v_i в v_j имеется путь длины < = k+1. Рассмотрим кратчайший из таких путей. Если его длина < = k, то по предположению индукции a_{ij}^{(k)}=1. Кроме того, a_jj⁽¹⁾=1. Поэтому a_ij^(k) a_jj⁽¹⁾=1 и a_ij^(k+1)=1. Если длина кратчайшего пути из из v_i в v_j равна k+1, то пусть v_r - его предпоследняя вершина. Тогда из v_i в v_r имеется путь длины k и по предположению индукции a_ir^(k)=1. Так как , то a_{rj}^{(1)}=1. Поэтому a_ir^(k) a_rj⁽¹⁾=1 и a_ij^(k+1)=1.

Обратно, если a_ij^(k+1)=1, то хотя бы для одного r слагаемое a_ir^(k) a_rj⁽¹⁾ в сумме равно 1. Если это r=j, то a_ij^(k)=1 и по индуктивному предположению в G имеется путь из v_i в v_j длины < = k. Если же , то a_ir^(k)=1 и a_rj⁽¹⁾=1. Это означает, что в G имеется путь из v_i в v_r длины < = k и ребро . Объединив их, получаем путь из v_i в v_j длины < = k+1.

Из лемм 9.1 и 9.2 непосредственно получаем

Следствие 1. Пусть G=(V, E) - ориентированный граф с n вершинам и, а G^* - его граф достижимости. Тогда A_{G*} = . Доказательство. Из леммы 5.1 следует, что, если в G имеется путь из u в , то в нем имеется и простой путь из u в v длины < = n-1. А по лемме 5.2 все такие пути представлены в матрице .

Таким образом процедура построения матрицы смежности A_G* графа достижимости для G сводится к возведению матрицы в степень n-1. Сделаем несколько замечаний, позволяющих упростить эту процедуру.

1. Для возведения матрицы в произвольную степень n достаточно выполнить возведений в квадрат:

где k - это наименьшее число такое, что 2^k > = n.

2. Так как на диагонали в матрице стоят единицы, то для любых i < j все единицы матрицы сохраняются в матрице , в частности, и в матрице .

3. Если при вычислении элемента a_ij⁽²⁾ матрицы по стандартной формуле

обнаруживается такое r, что a_ir = 1 и a_rj =1, то и вся сумма a_ij⁽²⁾ =1. Поэтому остальные слагаемые можно не рассматривать.

Пример 9.3. Рассмотрим в качестве примера вычисление матрицы графа достижимости A_G* для графа G, представленного на рис.9.2. В этом случае

Так как у G имеется 6 вершин, то . Вычислим эту матрицу:

и (последнее равенство нетрудно проверить). Таким образом,

Как видим, эта матрица действительно задает граф , представленный на рис.9.3.