Page 32 - 4336
P. 32

2.3.2 Знаходження зворотного транзитивного замикання


                   Алгоритм            знаходження            зворотного           транзитивного

            замикання  по  матриці  суміжності  A  для  вершини  v   полягає  в
                                                                                       i
            наступному.

                                                                -
                   Крок 1.  Формується  вектор  Т (v )  з  n  елементів,  де  n –
                                                                   i
            кількість вершин графа. Даний вектор визначає довжини шляхів

            від  усіх  вершин  графа  до  i-ї  вершини.  Приймається  d=0.  В  i-й
                                     -
            елемент вектора Т (v )  заноситься значення d. j=i.
                                        i i
                   Крок 2. Переглядається j-й стовпчик матриці суміжності A і

            визначаються елементи a  (i=1, 2, …, n) рівні 1.
                                               i,j
                   Крок 3.  Якщо  жодний  з  елементів  a ≠1,  то  алгоритм
                                                                             i,j
                                                                                                  -
            завершується.  Усім  незаповненим  елементам  вектора  Т (v )
                                                                                                     i
            присвоюється  значення  ∞ –  це  означає  що  від  даних  вершин

            графа  немає  шляхів  до  вершини  v .  В  іншому  випадку
                                                                     i
            здійснюється перехід до кроку 4.

                   Крок 4. Якщо є один або більше елементів a =1, то d=d+1,
                                                                                   i,j
            j=i (крім  тих  значень  i,  яким  відповідають  уже  заповнені
                                         -
            елементи  вектора  Т (v ))  та  відповідним  i-м  елементам  вектора
                                            i
              -
            Т (v )  (крім уже заповнених елементів) присвоюється значення d.
                 i i
            Це означає що від даних вершин існують шляхи довжиною d до
                                                                             -
            вершини  v .  Якщо  усі  елементи  вектора  Т (v )  заповнені,  то
                            i
                                                                                i
            алгоритм завершує свою роботу. В іншому випадку здійснюється

            перехід до кроку 5.

                   Крок 5.  Переглядаються  відповідні  j-ті  стовпчики  матриці

            суміжності A і визначаються елементи a  (i=1, 2, …, n) рівні 1.
                                                                      i,j
            Здійснюється перехід до кроку 3.

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

            матриці  суміжності,  наведеної  на  рис. 2.2,  а,  для  вершини  v
                                                                                                      3
            графа, наведеного на рис. 2.2, б.

                                                        32
   27   28   29   30   31   32   33   34   35   36   37