Page 31 - 4336
P. 31

+
                         Крок 4.  d=d+1=1,  j=5,  i=j=5,                          Т (v )    Т (v )
                                                                                     +
                                                                                         2
                                                                                                      1
                    +
                  Т (v ) d.                                                   v 1     2            0
                       2 5
                         Крок 5.  Переглядаємо 5-й  рядок                      v 2     0            1
                  матриці А: a =1, a =1. Переходимо до                         v 3     3            1
                                             5,4
                                    5,1
                  кроку 3.                                                     v 4     2            3
                                                                               v 5     1            2
                         Крок 3. Оскільки існують елементи
                                                                               v 6    ∞             ∞
                  a =1, то переходимо до кроку 4.                                         а               б
                    i,j
                         Крок 4.  d=d+1=2,  j={1, 4},  i=j=
                                              +
                               +
                  ={1, 4}, Т (v ) d, Т (v ) d.                                   Рисунок 2.3.
                                   2 1
                                                  2 4
                         Крок 5.  Переглядаємо 1-й  та 4-й  рядки  матриці  А:  a =1,
                                                                                                      1,2
                  a =1, a =1. Переходимо до кроку 3.
                             4,3
                    1,3
                         Крок 3. Оскільки існують елементи a =1, то переходимо до
                                                                             i,j
                  кроку 4.
                                                                                               +
                         Крок 4. d=d+1=3. Оскільки 2-й елемент вектора Т (v )  уже
                                                                                                   2 2
                                                       +
                  заповнений, то j=3, i=j=3, Т (v ) d.
                                                           2 3
                         Крок 5.  Переглядаємо 3-й  рядок  матриці  А:  жодний  із

                  елементів a ≠1. Переходимо до кроку 3.
                                  i,j
                         Крок 3.  Оскільки  жодний  із  елементів  a ≠1,  то  процес
                                                                                       i,j
                  формування  прямого  транзитивного  замикання  завершується.

                                                                                 +
                  Усім  незаповненим  елементам  вектора  Т (v )  присвоюється
                                                                                     2
                  значення ∞.
                                                              +
                         Таким чином, у векторі Т (v ) стоять числа рівні довжинам
                                                                  2
                  шляхів від  вершини  v  до відповідних вершин графа. Отже, дані
                                                 2
                  вершини  входять  у  пряме  транзитивне  замикання  вершини  v   –
                                                                                                         2
                    +
                  Т (v )={v , v , v , v , v }.
                                      3
                                  2
                                               5
                                           4
                       2
                              1
                         На  рис. 2.3,  б  показано  побудову  прямого  транзитивного
                                                           +
                  замикання для вершини v  – Т (v )={v , v , v , v , v }.
                                                                      1
                                                               1
                                                                              3
                                                                          2
                                                                                      5
                                                     1
                                                                                  4
                                                              31
   26   27   28   29   30   31   32   33   34   35   36