Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 26 + 16 + 35 + 18 + 5 + 23 = 123
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j	1	2	3	4	5	6	di	
1	M	26	42	15	29	25	15	
2	7	M	16	1	30	25	1	
3	20	13	M	35	5	0	0	
4	21	16	25	M	18	18	16	
5	12	46	27	48	M	5	5	
6	23	5	5	9	5	M	5	

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i  j	1	2	3	4	5	6	
1	M	11	27	0	14	10	
2	6	M	15	0	29	24	
3	20	13	M	35	5	0	
4	5	0	9	M	2	2	
5	7	41	22	43	M	0	
6	18	0	0	4	0	M	
dj	5	0	0	0	0	0	

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i  j	1	2	3	4	5	6	
1	M	11	27	0	14	10	
2	1	M	15	0	29	24	
3	15	13	M	35	5	0	
4	0	0	9	M	2	2	
5	2	41	22	43	M	0	
6	13	0	0	4	0	M	

Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
i  j	1	2	3	4	5	6	di	
1	M	11	27	0(10)	14	10	10	
2	1	M	15	0(1)	29	24	1	
3	15	13	M	35	5	0(5)	5	
4	0(1)	0(0)	9	M	2	2	0	
5	2	41	22	43	M	0(2)	2	
6	13	0(0)	0(9)	4	0(2)	M	0	
dj	1	0	9	0	2	0	0	

Наибольшая сумма констант приведения равна (10 + 0) = 10 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
i  j	1	2	3	4	5	6	di	
1	M	11	27	M	14	10	10	
2	1	M	15	0	29	24	0	
3	15	13	M	35	5	0	0	
4	0	0	9	M	2	2	0	
5	2	41	22	43	M	0	0	
6	13	0	0	4	0	M	0	
dj	0	0	0	0	0	0	10	

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	2	3	5	6	di	
2	1	M	15	29	24	1	
3	15	13	M	5	0	0	
4	M	0	9	2	2	0	
5	2	41	22	M	0	0	
6	13	0	0	0	M	0	
dj	1	0	0	0	0	2	

Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
i  j	1	2	3	5	6	di	
2	0(16)	M	15	29	24	15	
3	14	13	M	5	0(5)	5	
4	M	0(2)	9	2	2	2	
5	1	41	22	M	0(1)	1	
6	12	0(0)	0(9)	0(2)	M	0	
dj	1	0	9	2	0	0	

Наибольшая сумма констант приведения равна (15 + 1) = 16 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
i  j	1	2	3	5	6	di	
2	M	M	15	29	24	15	
3	14	13	M	5	0	0	
4	M	0	9	2	2	0	
5	1	41	22	M	0	0	
6	12	0	0	0	M	0	
dj	1	0	0	0	0	16	

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i  j	2	3	5	6	di	
3	13	M	5	0	0	
4	0	9	2	2	0	
5	41	22	M	0	0	
6	0	0	0	M	0	
dj	0	0	0	0	0	

Чтобы исключить подциклы, запретим следующие переходы: (4,2), 
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
i  j	2	3	5	6	di	
3	13	M	5	0(5)	5	
4	M	7	0(0)	0(0)	0	
5	41	22	M	0(22)	22	
6	0(13)	0(7)	0(0)	M	0	
dj	13	7	0	0	0	

Наибольшая сумма констант приведения равна (22 + 0) = 22 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).
Нижняя граница гамильтоновых циклов этого подмножества:
i  j	2	3	5	6	di	
3	13	M	5	0	0	
4	M	7	0	0	0	
5	41	22	M	M	22	
6	0	0	0	M	0	
dj	0	0	0	0	22	

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i  j	2	3	5	di	
3	13	M	5	5	
4	M	7	0	0	
6	0	0	M	0	
dj	0	0	0	5	

Чтобы исключить подциклы, запретим следующие переходы: (4,2), 
Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
i  j	2	3	5	di	
3	8	M	0(8)	8	
4	M	7	0(7)	7	
6	0(8)	0(7)	M	0	
dj	8	7	0	0	

Наибольшая сумма констант приведения равна (8 + 0) = 8 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
i  j	2	3	5	di	
3	8	M	M	8	
4	M	7	0	0	
6	0	0	M	0	
dj	0	0	0	8	

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i  j	2	3	di	
4	M	7	7	
6	0	0	0	
dj	0	0	7	

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

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