Page 118 - 6197

  1
Переходимо до другого рядка матриці C . Нульовим
2
  1
елементом у другому рядку матриці є елемент c . Тому
24
  1
  1
  min :c  min :c  1 0 1  .
24 2 j 4 i
j 4 i 2
Аналізуючи потім рядки 3, 4, 5 і 6, знаходимо
  1   1
  min :c  min :c  5 0 5  ,
36 3 j 6 i
j 6 i 3
  1   1
  min :c  min :c  0 1 1  ,
41 4 j 1 i
j 1 i 4
  1   1
0
  min :c  min :c  0 0  ,
42 4 j 2 i
j 2 i 4
  1   1
2
  min :c  min :c  2 0  ,
56 5 j 6 i
j 6 i 5
  1
  1
  min :c  min :c  0 0 0  ,
62 6 j 2 i
j 2 i 6
  1
  1
  min :c  min :c  0 9 9  ,
63 6 j 3 i
j 3 i 6
  1
  1
2
  min :c  min :c  0 2  .
65 6 j 5 i
j 5 i 6
Знаходимо   max :  max 10 1 5 1 0 2 0 9 2, , , , , , , ,  10 .
i 0 0 j   1 ij
ij c  0
Значенню   10 відповідає  . Отже, i  , j  і
1
4
i 0 0 j 14 0 0
  1
відповідно   10. Пара (1,4) включаємо до множини C і є
14 1
  1
забороненою для множини C .
2
1
Оскільки i  і j  , то розгалуження початкової
4
0 0
  0
множини G відбувається за переходом   4, . У результаті
1
1
розгалуження отримуємо дві множини G   1    4, і
1
  1
1
G    4, .
2
За формулою (2.19) знаходимо, що
 
L G 2   1  d   .
14
0
118