Page 11 - 4387

Крок 5. Переглядаємо 5-й рядок матриці А:

a =1, a =1. Переходимо до кроку 3. Т (v )
+
5,4
5,1
Крок 3. Оскільки існують елементи a =1, то v 2 2
i,j
1
переходимо до кроку 4. v 0
2
Крок 4. d=d+1=2, j={1, 4}, i=j={1, 4}, v 3
3
+
+
Т (v ) →d, Т (v ) →d. v 2
4
2 1
2 4
Крок 5. Переглядаємо 1-й та 4-й рядки v 1
5
матриці А: a =1, a =1, a =1. Переходимо до v ∞
6
4,3
1,3
1,2
кроку 3. Рисунок 1.3.
Крок 3. Оскільки існують елементи a =1, то переходимо до
i,j
кроку 4.
+
Крок 4. d=d+1=3. Оскільки 2-й елемент вектора Т (v ) уже
2 2
+
заповнений, то j=3, i=j=3, Т (v ) →d.
2 3
Крок 5. Переглядаємо 3-й рядок матриці А: жодний із

елементів a ≠1. Переходимо до кроку 3.
i,j
Крок 3. Оскільки жодний із елементів a ≠1, то процес
i,j
формування прямого транзитивного замикання завершується.

+
Усім незаповненим елементам вектора Т (v ) присвоюється
2
значення ∞.

+
Таким чином, у векторі Т (v ) стоять числа рівні довжинам
2
шляхів від вершини v до відповідних вершин графа. Отже, дані
2
вершини входять у пряме транзитивне замикання вершини v –
2
+
Т (v )={v , v , v , v , v }.
3
4
2
2
1
5
Алгоритм знаходження зворотного транзитивного
замикання по матриці суміжності A для вершини v полягає в
i
наступному.
-
Крок 1. Формується вектор Т (v ) з n елементів, де n –
i
кількість вершин графа. Даний вектор визначає довжини шляхів

10