Page 28 - 4336
P. 28

+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
   23   24   25   26   27   28   29   30   31   32   33