Page 9 - 4387

Зворотним транзитивним замиканням деякої вершини v
i
-
Т (v ) є об'єднання самої вершини v із зворотним відображенням
i
i
1-го порядку, 2-го порядку і т.д., тобто
-2
-1
-
Т (v )={v } ∪Г (v ) ∪Г (v ) ∪… . (1.5)
i
i
i
i
Іншими словами, зворотне транзитивне замикання для
-
деякої вершини v Т (v ) це множина вершин, з яких існують
i
i
шляхи у вершину v , тобто
i
-
Т (v )={v : ∃ шлях з v , в v }. (1.6)
i
j
j
i
Так, зворотне транзитивне замикання для вершини v графа,
1
зображеного на рис. 1.1, буде таким:
-
Т (v )={v }∪{v }∪{v , v }∪{v , v , v }={v , v , v , v , v }.
5
3
1
4
3
2
4
4
2
1
1
5
1
Алгоритм знаходження прямого транзитивного замикання
по матриці суміжності для вершини v полягає в наступному.
i
+
Крок 1. Формується вектор Т (v ) з n елементів, де n –
i
кількість вершин графа. Даний вектор визначає довжини шляхів
від i-ї вершини графа до усіх інших вершин. Приймається d=0. В
+
i-й елемент вектора Т (v ) заноситься значення d.
i i
Крок 2. Переглядається i-й рядок матриці суміжності A і
визначаються елементи a (j=1, 2, …, n) рівні 1.
i,j
Крок 3. Якщо жодний з елементів a ≠1, то алгоритм
i,j
+
завершується. Усім незаповненим елементам вектора Т (v )
i
присвоюється значення ∞ – це означає що від вершини v нема
i
шляхів до даних вершин графа. В іншому випадку здійснюється
перехід до кроку 4.

Крок 4. Якщо є один або більше елементів a =1, то d=d+1,
i,j
i=j (крім тих значень j, яким відповідають уже заповнені

+
елементи вектора Т (v )) та відповідним i-м елементам вектора
i
+
Т (v ) (крім уже заповнених елементів) присвоюється значення d.
i i

8