Page 33 - 4336

Розв'язок.

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

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

-
-
Крок 4. d=d+1=2. i={5, 6}, j=i={5, 6}, Т (v ) d, Т (v ) d.
3 6
3 5
Крок 5. Переглядаємо 5-й та 6 стовпчики матриці А: a =1,
2,5
a =1. Переходимо до кроку 3.
6,5
Крок 3. Оскільки існують елементи a =1, то переходимо до
i,j
кроку 4.
-
Крок 4. d=d+1=3. Елемент вектора Т (v ) уже заповнений,
3 6
-
-
тому i=2, j=i=2, Т (v ) d. Оскільки усі елементи вектора Т (v )
3
3 2
заповнені, то процес формування зворотного транзитивного
замикання завершується.
-
Таким чином, у векторі Т (v ) стоять числа рівні довжинам
3
шляхів від відповідних вершин до вершини v . Отже, дані
3
вершини входять у зворотне транзитивне замикання вершини v –
3
-
Т (v )={v , v , v , v , v , v }.
3
2
1
4
6
5
3
На рис. 2.4, б показано побудову зворотного транзитивного
-
замикання для вершини v – Т (v )={v , v , v , v }.
1
1
1
6
5
2
33