Page 28 - 4336

+1
+
+2
+
Г (v )=Г (Г (v ))=Г (v )={v };
3
2
5
2
+2
+3
+
+
Г (v )=Г (Г (v ))=Г (v )={v , v };
2
5
2
1
2
+
+3
+4
+
Г (v )=Г (Г (v ))=Г (v , v )={v , v }{v }={v , v }.
1
2
2
2
3
3
2
3
2
Відображення 4-го порядку містить ті ж вершини, що й
попередні відображення, отже, інші вершини в наступних
відображеннях не з'являться. Таким чином, пряме транзитивне
замикання для вершини v буде наступним:
1
+
Т (v )={v }{v }{v }{v , v }={v , v , v , v }.
1
3
1
5
3
1
2
1
2
5
+
Проаналізувавши множину вершин, що входять в Т (v ),
i
можна зробити висновок, що пряме транзитивне замикання
містить вершини, в які існують шляхи з вершини v . Таким чином
i
можна дати друге визначення прямому транзитивному
замиканню.
+
Пряме транзитивне замикання деякої вершини v Т (v ) – це
i
i
множина вершин, в які існують шляхи з вершини v , тобто
i
+
Т (v )={v :  шлях з v в v }. (2.4)
i
j
j
i
2.2.2 Зворотні транзитивні замикання
Зворотним транзитивним замиканням деякої вершини v
i
-
Т (v ) є об'єднання самої вершини v із зворотним відображенням
i
i
1-го порядку, 2-го порядку і т.д., тобто
-2
-1
-
Т (v )={v }Г (v )Г (v )… . (2.5)
i
i
i
i
Іншими словами, зворотне транзитивне замикання для
-
деякої вершини v Т (v ) це множина вершин, з яких існують
i
i
шляхи у вершину v , тобто
i
-
Т (v )={v :  шлях з v , в v }. (2.6)
j
i
i
j

28