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

i  j	2	4	5	di
1	M	1	M	1
3	0	0	M	0
4	0	M	0	0
dj	0	0	0	1

Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d₅₁ заменяем на М, для исключения образования негамильтонова цикла. 
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения. 
Сумма констант приведения сокращенной матрицы: 
 
После операции приведения сокращенная матрица будет иметь вид:

i  j	2	4	di
3	0	0	0
4	0	M	0
dj	0	0	0

Нижняя граница подмножества (1,5) равна: 
H(1,5) = 83 + 0 = 83  <  84 
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут. 
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (4,2). 
В результате по дереву ветвлений гамильтонов цикл образуют ребра: 
(7,3), (3,4), (4,2), (2,6), (6,1), (1,5), (5,7), 
Длина маршрута равна F(Mk) = 83

---

Смотрите также файлы

• Lektsiya8.doc

• M51_21_-_kopia.pdf

• Zadachi.docx

• Communication theory.docx

• Computer games.docx