Page 30 - 4336

+
елементти вектоора Т (vv )) та віідповіднним i-м елементтам векттора
i
+
Т (v ) (ккрім ужее заповннених еллементів)) присвооюється значенння d.
i i
Це ознаачає щоо від верршини vv існуюють шляххи довжжиною dd до
i
+
відповіддних j-хх вершинн графа.. Якщо уусі елемменти веектора ТТ (v )
i
заповнеені, то аллгоритм завершуує свою роботу.. В іншоому випаадку

здійснююється пеерехід до кроку 5.

Кррок 5. Перегляядаютьсяя відпоовідні i--ті рядкки матрриці

суміжноості A і визначааються еелементии a (j=1, 2, …,, n) рівнні 1.
i,j
Здійснююється пперехід ддо кроку 3.

Прриклад 2.5. Зннайти прряме трранзитиввне заммикання по

матриціі суміжнності, наведеної на рис. 2.2, аа, для ввершинии v2

графа, ннаведеноого на риис. 2.2, бб.

Маатриця ссуміжноссті

v v v 3 v v v 6
4
1
2
5
v 0 1 10 0 0
11
v 0 0 00 1 0
22
v 0 0 00 0 0
33
A=
v 0 0 10 0 0
44
v 1 0 01 0 0
55
v 1 0 00 1 0
66
а а б

Рисуунок 2.2.

Роозв'язок.

+
Кррок 1. ФФормуєтьься векттор Т (vv ) з шессти елемментів (ррис.
2
+
2.3, а). dd=0, i=22, Т (v ) d.
2 2
Кррок 2. Пеереглядааємо і-й ррядок матриці АА (2-й ряядок): a =1.
2,5
Кррок 3. Осскільки існуютьь елеменнти a =1, то перреходимоо до
i,j
кроку 44.

30