Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X0) = 35 + 17 + 2 + 10 + 10 = 74
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j	1	2	3	4	5	di	
1	M	35	45	20	11	11	
2	9	M	17	6	8	6	
3	21	31	M	2	11	2	
4	30	15	40	M	10	10	
5	10	9	8	7	M	7	

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j	1	2	3	4	5	
1	M	24	34	9	0	
2	3	M	11	0	2	
3	19	29	M	0	9	
4	20	5	30	M	0	
5	3	2	1	0	M	

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i  j	1	2	3	4	5	
1	M	24	34	9	0	
2	3	M	11	0	2	
3	19	29	M	0	9	
4	20	5	30	M	0	
5	3	2	1	0	M	
dj	3	2	1	0	0	

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i  j	1	2	3	4	5	
1	M	22	33	9	0	
2	0	M	10	0	2	
3	16	27	M	0	9	
4	17	3	29	M	0	
5	0	0	0	0	M	

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 11+6+2+10+7+3+2+1+0+0 = 42
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	4	5	di	
1	M	22	33	9	0(9)	9	
2	0(0)	M	10	0(0)	2	0	
3	16	27	M	0(9)	9	9	
4	17	3	29	M	0(3)	3	
5	0(0)	0(3)	0(10)	0(0)	M	0	
dj	0	3	10	0	0	0	

d(1,5) = 9 + 0 = 9; d(2,1) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(3,4) = 9 + 0 = 9; d(4,5) = 3 + 0 = 3; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 3 = 3; d(5,3) = 0 + 10 = 10; d(5,4) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (0 + 10) = 10 для ребра (5,3), следовательно, множество разбивается на два подмножества (5,3) и (5*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,3*) = 42 + 10 = 52
Исключение ребра (5,3) проводим путем замены элемента d53 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,3*), в результате получим редуцированную матрицу.
i  j	1	2	3	4	5	di	
1	M	22	33	9	0	0	
2	0	M	10	0	2	0	
3	16	27	M	0	9	0	
4	17	3	29	M	0	0	
5	0	0	M	0	M	0	
dj	0	0	10	0	0	10	

Включение ребра (5,3) проводится путем исключения всех элементов 5-ой строки и 3-го столбца, в которой элемент d35 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 3
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	2	4	5	di	
1	M	22	9	0	0	
2	0	M	0	2	0	
3	16	27	0	M	0	
4	17	3	M	0	0	
dj	0	3	0	0	3	

Нижняя граница подмножества (5,3) равна:
H(5,3) = 42 + 3 = 45  <  52
Поскольку нижняя граница этого подмножества (5,3) меньше, чем подмножества (5*,3*), то ребро (5,3) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	4	5	di	
1	M	19	9	0(9)	9	
2	0(16)	M	0(0)	2	0	
3	16	24	0(16)	M	16	
4	17	0(19)	M	0(0)	0	
dj	16	19	0	0	0	

d(1,5) = 9 + 0 = 9; d(2,1) = 0 + 16 = 16; d(2,4) = 0 + 0 = 0; d(3,4) = 16 + 0 = 16; d(4,2) = 0 + 19 = 19; d(4,5) = 0 + 0 = 0; 
Наибольшая сумма констант приведения равна (0 + 19) = 19 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(4*,2*) = 45 + 19 = 64
Исключение ребра (4,2) проводим путем замены элемента d42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.
i  j	1	2	4	5	di	
1	M	19	9	0	0	
2	0	M	0	2	0	
3	16	24	0	M	0	
4	17	M	M	0	0	
dj	0	19	0	0	19	

Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	4	5	di	
1	M	9	0	0	
2	0	M	2	0	
3	16	0	M	0	
dj	0	0	0	0	

Нижняя граница подмножества (4,2) равна:
H(4,2) = 45 + 0 = 45  <  64
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	4	5	di	
1	M	9	0(11)	9	
2	0(18)	M	2	2	
3	16	0(25)	M	16	
dj	16	9	2	0	

d(1,5) = 9 + 2 = 11; d(2,1) = 2 + 16 = 18; d(3,4) = 16 + 9 = 25; 
Наибольшая сумма констант приведения равна (16 + 9) = 25 для ребра (3,4), следовательно, множество разбивается на два подмножества (3,4) и (3*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,4*) = 45 + 25 = 70
Исключение ребра (3,4) проводим путем замены элемента d34 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,4*), в результате получим редуцированную матрицу.
i  j	1	4	5	di	
1	M	9	0	0	
2	0	M	2	0	
3	16	M	M	16	
dj	0	9	0	25	

Включение ребра (3,4) проводится путем исключения всех элементов 3-ой строки и 4-го столбца, в которой элемент d43 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	5	di	
1	M	0	0	
2	0	2	0	
dj	0	0	0	

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

Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера