Матрица м данного графа имеет вид

a b c d e f

1. b c a c c a

2. - e d f d b

3. - - - - - c

В качестве отправной вершины рассмотрим а. Множество S формируется следующим образом:

Но-мер	Множество S	Комментарии
1	a	Добавляем первую возможную вершину в столбце а (т.е. вершину b).
2	а,b	Добавляем первую возможную вершину в столбце b (т.е. вершину с)
3	a,b,c	Первая вершина а в столбце с не является возможной (аS), добавляем следующую вершину в столбце (т.е. вершину d).
4	a,b,c,d	Добавляем вершину f.
5	a,b,c,d,f	В столбце f нет возможной вершины. Возвращение.
6	a,b,c,d	В столбце d не существует возможной вершины, следующей за f. Возвращение.
7	a,b,c	Аналогично предыдущему. Возвращение.
8	а,b	Добавляем вершину е.
9	a,b,e	Добавляем вершину с.
10	a,b,e,c	Добавляем вершину d.
11	a,b,e,c,d	Добавляем вершину f.
12	a,b,e,c,d,f	Гамильтонов путь. Дуга (f,a) дает гамильтонов контур. Возвращение.
13	a,b,e,c,d	Возвращение.
14	a,b,e,c	Возвращение.
15	a,b,e	Добавляем вершину d.
16	a,b,e,d	Добавляем вершину f.
17	a,b,e,d,f	Добавляем вершину c.
18	a,b,e,d,f,c	Гамильтонов путь. Путь замыкается дугой (c,a). Возвращение.
19	a,b,e,d,f	Возвращение.
20	a,b,e,d	Возвращение.
21	a,b,e	Возвращение.
22	а,b	Возвращение.
23	a	Возвращение.
24		Конец поиска.

В результате работы алгоритма определены гамильтоновы пути ₁=[a,b,e,c,d,f], ₂=[a,b,e,d,f,c] и контуры [a,b,e,c,d,f,a], [a,b,e,d,f,c,a].

4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров

Замечание. «Внутреннее произведение вершин» пути [x₁,…,x_k] определяется как формальное выражение вида x₂x₃…x_k-1, не содержащее две концевые вершины x₁ и x_k.

Шаг 1. G – данный орграф на n вершинах; А – матрица смежности с нулевыми элементами на диагонали; – модифицированная матрица смежности, в которой b_ij=bij)=x_j, если существует дуга из x_i в x_j и 0 в противном случае. Положить k=1,  ^k=A.

Шаг 2. Положить k=k+1. Найти P ^k=BP ^k-1.

Шаг 3. Если k=n, то диагональные элементы матрицы P ⁿ дают внутренние произведения вершин, которые соответствуют гамильтоновым контурам графа. Получить гамильтоновы контуры. Останов. Иначе перейти к шагу 4.

Шаг 4. Сделать все пути простыми, обнулив в матрице P^k все диагональные элементы, которые содержат сомножителями вершины, соответствующие данной строке. Перейти к шагу 5.

Шаг 5. Если k=n-1, то элементы матрицы P^k дают внутренние произведения вершин, которые соответствуют гамильтоновым путям графа G. Получить гамильтоновы пути. Перейти к шагу 2.

П ример. Рассмотрим граф, изображенный на рис. 4.44.

Рис. 4.44

Матрица смежности А этого графа имеет вид

a b c d e

a 0 1 0 1 0

A = b 0 0 0 1 1

c 0 1 0 0 1

d 0 0 1 0 0

e 1 0 1 0 0

а модифицированная матрица смежности В выглядит следующим образом:

a b c d e

a 0 b 0 d 0

b 0 0 0 d e

B = c 0 b 0 0 e

d 0 0 c 0 0

e a 0 c 0 0

Положим P₁=A. Матрица P₂’=B₁ получается равной

a b c d e

a 0 0 d b b

b e 0 d+e 0 0

P₂’ = c e 0 e b b

d 0 c 0 0 c

e 0 a+c 0 a c

Матрица P₂ почти такая же, как P₂’, только подчеркнутые элементы в P₂’ надо заменить нулями. Матрица P₃’=BP₂ равна

a b c d e

a be dc bd+be 0 dc

b 0 dc+ea+ec 0 ea dc

P₃’= c be ea+ec bd+be ea 0

d ce 0 0 cb cb

e ce 0 ad ab+cb ab+cb

Матрица Р₃ получается из P₃’ после замены подчеркнутых элементов нулями. Матрица Р₄’=BP₃

a b c d e

a dce 0 0 bea bdc+dcb

b dce 0 ead eab+ecb dcb

P₄’= c 0 0 ead bea+eab+ecb bdc

d cbe cea 0 cea 0

e cbe adc+cea abd+abe cea adc

Гамильтоновы пути можно определить по матрице Р₄, которая имеет вид

a b c d e

a 0 0 0 0 bdc+cdb

b dce 0 ead 0 0

P₄= c 0 0 0 bea+eab 0

d cbe cea 0 0 0

e 0 adc abd 0 0

Гамильтоновы пути abdce и adcbe, соответствующие элементу (1,5) матрицы Р₄ дают гамильтоновы контуры abdcea и adcbea, если добавить замыкающую дугу (е,а). Все другие гамильтоновы пути в Р₄ приводят к тем же самым контурам, и потому в графе G есть только два таких контура.

Пример. Математическая постановка задачи нахождения оптимальной последовательности выпуска изделий.

Введем некоторые обозначения. Пусть {a₁…a_L} - множество всевозможных последовательностей выпуска изделия L модификаций; - количество оборудования в группе , где =1,…,N; - время, необходимое на переналадку единицы оборудования -ой группы при переходе с выпуска i-ой модификации на выпуск j-ой модификации.

Пусть G - ориентированный граф, вершины которого представляют изделия, а существование дуги (х_i, х_i) означает, что изделие j может следовать за изделием i без перенастройки оборудования. Тогда, если в этом графе есть гамильтонов цикл (ориентированный цикл, проходящий через каждую вершину графа), то существует последовательность выпуска изделий, не требующая перенастройки оборудования. Если не существует циклической последовательности выпуска изделий, не требующей перенастройки оборудования, то задача сводится к нахождению последовательности выпуска изделий, требующих наименьших затрат на перенастройку оборудования.

Пусть х_ij =1, если после изделия i-ой модификации выпускается изделие j-ой модификации; х_ij=0, если после изделия i-ой модификации изделие j-ой модификации не выпускается.

С так введенными переменными ставим задачу:

Минимизировать функцию

(1)

при условиях

, , . (2)

В качестве дополнительных ограничений необходимо наложить условие «петель», для устранения подконтуров в задаче

(3)

Задача (1)-(3) полностью аналогична классической задаче коммивояжера:

(4)

при условиях

, , . (5)

условие «петель»

(6)

В задаче коммивояжера (4)-(6) ищется оптимальная последовательность обхода «городов», а в задаче (1)-(3) оптимальная последовательность выпуска изделий. В задаче (4)-(6) матрица D с элементами является матрица расстояний между N «городами», этой матрице соответствует матрица В в задаче (1)-(3) с элементами , которая является матрицей времени переналадки оборудования

Таким образом, задачу оптимизации последовательности выпуска изделий можно решить методами решения задачи коммивояжера.