Page 29 - 4336

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

вершини v графа, зображеного на рис. 2.1.
2
Розв'язок.

-1
Г (v )={v , v };
5
1
2
-
-
-2
-1
Г (v )=Г (Г (v ))=Г (v , v )={v }{v , v }={v , v , v };
2
5
1
2
3
5
4
4
3
5
Оскільки зворотні відображення 1-го та 2-го порядку
містять усі вершини графа, то пошук зворотних замикань
припиняється. Таким чином, зворотне транзитивне замикання для
вершини v буде наступним:
2
-
Т (v )={v }{v , v }{v , v , v }={v , v , v , v , v }.
2
1
5
4
3
3
5
4
1
5
2
2
2.3 Знаходження транзитивних замикань по матриці
суміжності
2.3.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, яким відповідають уже заповнені

29