Page 34 - 4336
P. 34

3  ДОСЯЖНІСТЬ І КОНТРДОСЯЖНІСТЬ НА ГРАФАХ.

                  МАТРИЧНИЙ МЕТОД ЗНАХОДЖЕННЯ ШЛЯХІВ У

                                                   ГРАФАХ



                   Задач, в яких використовується поняття досяжності, досить
            багато.  При  розгляді  графа  в  якості  моделі  деякої  дорожньої


            мережі можна поставити питання, чи можливо від перехрестя v
                                                                                                      i
            досягти  перетин  вулиць  v ,  тобто  чи  існує  шлях,  що  веде  від
                                                  j
            вершини v  до вершини v . Якщо такий шлях існує, то говорять,
                           i
                                                j
            що вершина v  досяжна з вершини v .
                                                              i
                               j

                                      3.1 Досяжність на графах


                   Досяжність  у  графі  описується  матрицею  досяжності

            R=[r ],  i, j=1, 2, ..., n,  де  n –  кількість  вершин  графа,  а  кожний
                  i,j
            елемент визначається наступним чином:

                   1)  r =1, якщо вершина v  досяжна з v ;
                                                      j
                         i,j
                                                                       i
                   2)  r =0 у іншому випадку.
                         i,j
                   Множина  вершин  R(v )  графа  G,  досяжних  із  заданої
                                                     i
            вершини v , складається з таких елементів v , для яких елемент r
                                                                                                     i,j
                                                                         j
                           i
            в матриці досяжності дорівнює 1. Очевидно, що всі діагональні
            елементи  в  матриці  R  дорівнюють 1,  оскільки  кожна  вершина

            досяжна  з  себе  самої  шляхом  довжини 0.  Оскільки  пряме

                                                     +1
            відображення 1-го порядку Г (v ) є множиною таких вершин v ,
                                                                                                      j
                                                          i
            які досяжні з вершини v  з використанням шляхів довжини 1, то
                                               i
                                            +2
                            +
                                 +1
            множина  Г (Г (v ))=Г (v )  складається  з  вершин,  досяжних  з
                                                 i
                                     i
                                                                                                 +k
            вершини v  з використанням шляхів довжини 2. Аналогічно Г (v )
                                                                                                     i
                           i
            є  множиною  вершин,  які  досяжні  з  вершини  v   за  допомогою
                                                                                 i
            шляхів довжини k.


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