Page 123 - 6197

2 3 5
3 8 M 0 



C   4  4 M 7 0 .
 
6 0 0 M 



  4
Здійснюємо процес розбиття C на дві множини G   4 і
1
5
G   4 . За формулою (2.22) знаходимо   і відповідно
2 0
 
L G 1   4  51 5 56  . Тепер знайдемо оцінку для G 2   4 . Для
8
цього обчислимо   ,   ,   і   . Отже,
7
8
7
35 45 62 63
8
5
3
r  7 max :    і i  , j  . Тому для розгалуження
4 ij 35 0 0
i,j
вибираємо пару (3, 5). Обчислюємо оцінку для матриці G   4 ,
2
 
тобто L G 2   4  56 8 64  .
До маршруту L долучимо (3,5). Тоді
    5 6,
L   1 4 , 2 1, , ,  3 5, , .
  4
Над матрицею h  h  0 C здійснюємо операцію
2 3
розгалуження шляхом вилучення рядка і стовпця відповідно
під номерами 3 і 5, а елемент (5,3) набуде значення M . У
результаті будемо матрицю
2 3
4 M 7 

C   5    .
6 0 M 

Знаходимо, що r  , r  , h  h  0 і відповідно
7
0
4 6 2 3
 
  7. Отже, L G   5  56 7 63  . Виконавши операцію
0 1
  5
приведення над матрицею C , отримуємо
2 3
123