Page 10 - 4387

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

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

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

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

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

матриці суміжності, наведеної на рис. 1.2 а, для вершини v
2
графа, наведеного на рис. 1.2 б.

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

v v v v v v
4
2
3
1
6
5
v 0 1 1 0 0 0
1
v 0 0 0 0 1 0
2
v 0 0 0 0 0 0
A= 3
v 0 0 1 0 0 0
4
v 1 0 0 1 0 0
5
v 1 0 0 0 1 0
6
а б

Рисунок 1.2.

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

+
Крок 4. d=d+1=1, j=5, i=j=5, Т (v ) →d.
2 5

9