Практическая часть. Решение задачи о коммивояжере методом ветвей и границ
Из таких соображений выбираем дугу 
:
1. 
должно быть как можно меньше;
2. желательно выбрать , чтобы максимально возросла 
, следовательно, для дальнейшего разбиения выберем y.
Это приведет к возможному нахождению гамельктонова цикла, а, следовательно, к коррекции величины 
.
Чтобы выбрать дугу необходимо иметь матрицу 
, следовательно, прежде всего рассмотрим как можно получить, зная , матрицы соответствующие 
и 
.
Схема получения 
:
т. к. входит в любой гамельктоновый цикл из множества y, Поэтому вычеркиваем k – строку и l-столбец в матрице , т. к. больше не можем въезжать в город l и выезжать из города k.
Из всех дуг уже зафиксированных для множества y составляем связный путь, который обязательно включает в себя последнюю зафиксированную дугу . Этот связный путь может состоять из одной дуги . Полагаем, что в матрице 
, где m – конец, а p – начало, т.е. запрещаем подциклы.
Приводим 
, в результате получим с 
– константа приведения.
Схема получения 
в матрице полагаем, что , т.е. запрещаем.
В результате получаем 
, приводим , получаем и 
Схема выбора дуги 
просматривая все нулевые элементы , и для каждого такого элемента рассчитываем величину 
– сумма минимального элемента i-ой строки и минимального элемента j-го столбца матрицы , исключая сам нулевой элемент. 
.
выбираем из условия 
для всех 
можно не получать, а сразу получать .
Если же в процессе решения задачи придется разбивать , а соответствующей матрицы нет, то её нужно восстановить из исходной матрицы.
Схема восстановления для любого X из исходной матрицы 
:
Пусть вершина X такова, что для неё уже зафиксированы 
.
Шаг 1: для каждой фиксированной дуги 
для каждой .
Шаг 2: для каждой фиксированной дуги составляет связный путь, который содержит обязательную дугу ; и запрещает переезд из 
в 
, т.е. 
, где m – коней и p – начало.
Шаг 3: для каждой запрещенной дуги полагаем, что 
