Page 35 - 4336
P. 35

Оскілььки будьь-яка верршина гррафа, якка досяжжна з v , пповиннаа
                                                                                               i
                  бутти досяжжна з виккористаннням шляяху (абоо шляхів)) довжинни 0 абоо

                  1, аабо 2, ... , або k,, то мноожина веершин, ддосяжниих з вершшини v ,,
                                                                                                           i
                  можжна подаати у виггляді

                                                                  +2
                                                       +1
                                                                                  +k
                                      R(v )=={v }ГГ (v )ГГ (v )Г (v ).                        (3.1))
                                                i
                                          i
                                                                       i
                                                            i
                                                                                       ii
                         Як  баачимо,  ммножинаа  досяжних  верршин  R((v )  преддставляєє
                                                                                         i
                                                                                                       +
                  пряяме  траннзитивнее  замиккання  вершини  v ,  тоббто  R(v )=Т (v )..
                                                                                                          i
                                                                                i
                                                                                                 i i
                  Отжже,  дляя  побуддови  маатриці  ддосяжноості  неообхідно  знайтии
                  доссяжні  мнножини  R(v )  длля  всіх  ввершин  v V,  ввважаючии,  r =1,,
                                                                                                       i,j
                                                                              i
                                                 i
                  якщщо v R(v ) та r ==0 у іншшому виппадку.
                                   i
                                          i,j
                           j
                         Прикллад 3.1.  Для  граафа,  навведеногоо  на  рисс. 3.1,  а,,  знайтии
                  маттрицю доосяжноссті R.
                                                                         Маатриця сусуміжноссті
                                                                             v 1  v 2  vv  v  v  v    6  v 7
                                                                                                 5 5
                                                                                        3
                                                                                            4
                                                                        v 1  01 00 0 1  00
                                                                        v 2  00 00 1 0  00
                                                                        v 3  00 00 1 0  00
                                                                  A= v    4  00 00 0 1  00

                                                                        v 5  00 00 0 0  00
                                                                        v 6  00 11 0 0  01
                                                                        v 7  00 00 1 0  10

                                       а                                              бб
                          Матрииця досяяжності                       Матрииця конттрдосяжжності
                             v   v  2   v   v  v  5  vv 6  v 7               v 1  v 2  vv  v  v  v    6  v 7
                                              4
                                         3
                                1
                                                                                        3
                                                                                             4
                                                                                                 5 5
                          v   1  10  1 1 00 0                            v 1  10 00 0  0 00
                           1
                          v   0  10  1 1 00 0                            v 2  11 00 0  0 00
                           2
                          v   0  01  1 1 00 0                            v 3  00 1 0  0 11
                           3
                   R==  v   0  00  1 1 00 0                       Q= v    4   11 1 1  0 11
                           4
                          v   0  00  0 1 00 0                            v 5  11 1 1 1 11
                           5
                          v   0  01  1 1 11 1                            v 6  00 00 0  0 11
                           6
                          v   0  01  1 1 11 1                            v 7  00 00 0  0 11
                           7
                                       в                                              гг
                                                       Рисунокк 3.1.

                                                              35
   30   31   32   33   34   35   36   37   38   39   40