Page 31 - 4336

+
Крок 4. d=d+1=1, j=5, i=j=5, Т (v ) Т (v )
+
2
1
+
Т (v ) d. v 1 2 0
2 5
Крок 5. Переглядаємо 5-й рядок v 2 0 1
матриці А: a =1, a =1. Переходимо до v 3 3 1
5,4
5,1
кроку 3. v 4 2 3
v 5 1 2
Крок 3. Оскільки існують елементи
v 6 ∞ ∞
a =1, то переходимо до кроку 4. а б
i,j
Крок 4. d=d+1=2, j={1, 4}, i=j=
+
+
={1, 4}, Т (v ) d, Т (v ) d. Рисунок 2.3.
2 1
2 4
Крок 5. Переглядаємо 1-й та 4-й рядки матриці А: a =1,
1,2
a =1, a =1. Переходимо до кроку 3.
4,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
2
5
4
2
1
На рис. 2.3, б показано побудову прямого транзитивного
+
замикання для вершини v – Т (v )={v , v , v , v , v }.
1
1
3
2
5
1
4
31