Матрица достижимости r(u,V) задается следующим образом:

Р ешение проблемы достижимости диграфа требует полиномиального времени, т.е. относится к Р-классу.

Построить матрицу достижимости можно с помощью алгоритма BFS, выполнив его из каждой вершины диграфа D(V,E).

Сложность – О(n(n+m).

• Начало BFS – вершина 1.

• Исследуются все вершины {1,y} A. Из вершины 1 доступны вершины 2 и 4. Эти вершины заносятся в специальную запись

String={2,4}.

• Затем исследуются все вершины {2,y} A. Из вершины 2 доступны вершины 3 и 5, которые заносятся в специальную запись:

String= {2,3,4,5}.

• Исследуются все вершины {4,y} A. Из вершины 4 доступна только вершина 5. Т.к. такая вершина уже есть в специальном списке, то запись остается неизменной.

• Следующими вершинами будут {3,y} A. Из вершины 3 доступна вершина 6. Эта вершина заносится в специальный список:

String={2,3,4,5,6}.

• Рассматриваются вершины {5,y} A. Доступными будут вершины 2 и 6, которые есть в специальном списке.

• Следующие вершины будут {6,y} A. Доступная вершина – вершина 5, которая имеется в специальном списке.

• BFS из вершины 1 завершен. В результате выполнения BFS сформирована специальная запись

String={2,3,4,5,6},

которая показывает вершины, доступные из вершины 1.

• Данная запись позволяет записать первую строку матрицы достижимости:

(0 1 1 1 1 1).

• Если повторить BSF из всех оставшихся вершин диграфа, то результатом будет следующая матрица достижимости:

Матрицу смежности A(D) диграфа можно рассматривать как булевскую матрицу, т.к. элементы A(D) равны нулю или единице.

Матрица достижимости вычисляется следующим образом:

R(D) = A(D)  A²(D)  …  A^n-1, |V|=n,

где  - операция поэлементного булевского сложения строк матриц A(D),

A²(D), … , A^n-1;

Для облегчения вычисления степеней матриц A²(D), … , A^n-1 осуществляется с использованием булевских операций (умножение заменяется на , а сложение – на ).

Сложность алгоритма – О(n⁴).

Замечание

Правомочность использование булевских операций в данном алгоритме доказывается в целом ряде книг по диграфам.

Пусть [A(D)] – матрица смежности диграфа D=(V,E), n=|V|.

1. Пусть [Q₀]=[A(D)].

2. Сложить (булевская операция ) строку 1 матрицы [Q₀] к каждой строке [Q₀], которая имеет 1 в первом столбце. В результате получится матрица [Q₁]. Если первый столбец имеет только 0, тогда [Q₁]= [Q₀].

3. Сложить строку матрицы [Q₁] к каждой строке этой матрицы, которая имеет 1 во втором столбце. В результате получится матрица [Q₂]. Если втором столбце имеет только 0, тогда [Q₂]= [Q₃].

4. Для каждого j=3,…,n рассматривается матрица [Q_j-1]. Сложить строку j к каждой строке матрицы [Q_j-1], у которой j-ый столбец имеет 1. В результате получится матрица [Q_j]. Если j-ый столбец имеет только 0, тогда [Q_j]= [Q_j-1].

5. Записать [R(D)]=[Q_n].

С ложность алгоритма – O(n³).

• [Q₀]=[A(D)].

• Первая строка [Q₀] не имеет 1 в первом столбце. Поэтому [Q₁]=[Q₀].

• Строка 2 суммируется со строками 1 и 5 (имеют 1 во втором столбце):

• Строка 3 суммируется со строками 1,2 и 5:

• Сложить строку 4 со строкой 1. Результат – [Q₃]=[Q₄].

• Сложить строку 5 со строками 1,2,4,5 и 6:

• Сложить строку 6 со всеми строками: