Задача по системному анализу

После операции приведения сокращенная матрица будет иметь  вид: 

 

 

 

 

 

Нижняя граница подмножества (1,4) равна: 
H(1,4) = 33 + 11 = 44 ≤ 46 
Чтобы исключить подциклы, запретим следующие переходы: (5,1),  
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей

H = 44

Шаг 3 - определим ревброветвления. 
Разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ (бесконечность) и определим сумму образовавшихся констант приведения. 

i j	1	2	3	di
2	0(10)	∞	4	4
3	6	0(6)	∞	6
5	∞	0(0)	0(4)	0
dj	6	0	4	0

 

d(2,1) = 4 + 6 = 10;

d(3,2) = 6 + 0 = 6;

d(5,2) = 0 + 0 = 0;

d(5,3) = 0 + 4 = 4;  
Наибольшая сумма констант приведения равна (4 + 6) = 10 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*). 
Нижняя граница гамильтоновых циклов этого подмножества: 
H(2*,1*) = 44 + 10 = 54 
Исключение ребра (2,1) проводим путем замены элемента d₂₁ = 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу. 

i j	1	2	3	di
2	∞	∞	4	4
3	6	0	∞	0
5	∞	0	0	0
dj	6	0	0	10

 

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d₁₂заменяем на ∞, для исключения образования негамильтонова цикла.

В результате получим  другую сокращенную матрицу (2 x 2), используем операцию приведения. 
Сумма констант приведения сокращенной матрицы: 
∑d_i + ∑d_j = 0 
После операции приведения сокращенная матрица будет иметь вид: 

i j	2	3	di
3	0	∞	0
5	0	0	0
dj	0	0	0

 

Нижняя граница подмножества (2,1) равна:

H(2,1) = 44 + 0 = 44 ≤ 54

Поскольку нижняя граница этого  подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей

H = 44

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,2) и (5,3).

В результате по дереву ветвлений  гамильтонов цикл образуют ребра: 
(4,5), (5,3), (3,2), (2,1), (1,4), 

Длина маршрута равна F(Mk) = 44