Page 122 - 6197

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