Системная технология - Марат Телемтаев

9.2. Условие оптимальности

Для оптимального гамильтонова цикла справедливо следующее условие оптимальности: для любого простого маршрута, являющегося участком оптимального гамильтонова цикла и проходящего вершины графа в последовательности i1, i2, i3, ...,ia, (a=4,5, ...,n; i1=1,2,...,n) сумма весов входящих в него ребер ?(i1i2i3...ia) является минимальной в сравнении с любой другой суммой вида

?(i1i'2i'3...i'a-1ia):

при a =4,5, ... , n; i=1,2, ... , n; i'2 ,i'3 ,...,i'a-1, ? P

Здесь i'2, 'i3,..., i'a-1 — одна из перестановок чисел i2, i3,..., ia-1, P — множество всех перестановок этих чисел.

Очевидно, что если это условие не выполняется для каких – либо значений а и i, то существует гамильтонов цикл с меньшей длиной пути обхода вершин i1 ,i2 ,i3 ,..., ia-1,ia. Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i1, i2, i3,..., ia для любого а, имеющего значения в пределах от 4-х до п.

Значения а не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины последовательно в одном из двух возможных вариантов обхода: i1, i2, i3, i4 или i1, i3, i2, i4.

Пусть оптимальный гамильтонов цикл обходит вершины графа в последовательности

i1,i2,i3,..., in,i1. (9.2.1.a)

Гамильтонов цикл, оптимальный для определенного значения а, назовем а-оптимальным. Для а = 4 справедливо неравенство:

Условие (9.2.2) необходимо проверить для всех ik = i1 , i2,..., in и, если оно для всех 4 справедливо, то это необходимое и достаточное условие того, что гамильтонов цикл 4-оптимален. Просуммировав левые и правые части неравенств, получающихся при значениях ik = i1,i2,..., in, получаем необходимое условие 4-оптимальности в виде:

Справедливо следующее условие:

Если гамильтонов цикл a1-оптимален, то он а2-оптимален для любого a2<a1.

Если это условие не выполняется, т.е. a1-оптимальный гамильтонов цикл не является a2-оптимальным, то какой-то из простых путей длины a1 можно улучшить изменением обхода каких-то а2 вершин, что противоречит условия a1-оптимальности.

Перейдем к определению условия а-оптимальности, получаемого аналогично тому, как условие (9.2.3) получено из (9.2.2), из системы неравенств вида (9.2.2,), для любого a=const суммированием для всех ik=1,2, ... , п

Для каждого значения k будет иметь место система из ((а-2)!-1) неравенств по числу элементов множества Р, состоящего из (а-2)! перестановок чисел i'k+1, i'k+2, ..., i'k+a-2

При этом мы полагаем, что

Обозначим левую и правую части условия (9.2.4) буквами А и В, соответственно:

А ? В.

В левой части неравенства вес каждого ребра, принадлежащего проверяемому участку гамильтонова цикла, участвует точно по одному разу в каждом неравенстве системы из ((а-2)!-1) неравенств, задаваемых перестановками, принадлежащими множеству Р, при фиксированной начальной вершине.

Кроме этого, при заданном a=const, если производить проверку выполнения условия (9.2.4), изменяя последовательно номер начальной вершины от i1 до in, то любое ребро гамильтонова цикла появится точно в (а-1) системах из этих ((а-2)!-1) неравенств как первое по счету, второе, третье и т.д. (а-1)-е ребро в проверяемых участках гамильтонова цикла.

Следовательно, левая часть неравенства (9.2.4) имеет вид:

Выражение для правой части условия (9.2.4) можно записать в виде:

Для того, чтобы получить выражение для правой части условия (9.1.4), необходимо найти число появлений ребер графа вида (ic, ic+N ) в каждой системе из ((а-1) !-1) неравенств, задаваемых определенным значением k, а также во всех системах этих неравенств, получаемых при изменении ik от i1 до in.

Очевидно, что число появлений пар (ic, ic+N) в правых частях неравенств вида (9.2.4) равно числу появлений пар (ic, ic+N) в последовательностях:

ik, i'k+1, i'k+2, ..., i'k+a-2, ik+a-1 (9.2.5.)

задаваемых (а-2)! перестановками чисел i'k+1, i'k+2,..., i'k+a-2

Следует учесть также, что одна из этих последовательностей, а именно i1, i2, i3, ..., ik+a-1 находится в левой части этих неравенств.

Пары icic+N можно разделить на следующие виды по признаку, содержат они или нет «неподвижные» вершины ik и ik+а-1:

а) icic+N при с ? k; с+п < к+а-1; п>1, п ? а-2; это пары элементов в (9.2.5), не содержащие элементов ik, ik+а-1 и тех элементов (i1, i2, i'2 , i3, i'3, i4 и т.д.), которые входят в гамильтонов цикл (9.2.1а).

Каждая из пар этого вида появится в системе неравенств (9.2.4) для определенного значения ik=i1,i2, ..., in, точно (а-3)(а-4)! раз – по числу (а-4)! перестановок (а-4) элементов, т.е. элементов последовательности (9.1.5) за вычетом элементов ik, ik+a-1, ic, ic+N для каждого из (а-3) возможных положений пары ic, ic+N в последовательности (9.2.5).

б) ic, ic+N при n>1, с=k и ic+N ic+a-1 при n < а-2, с=k это пары элементов в (9.2.5), содержащие элементы ik или ik+a-1 и элементы гамильтонова цикла (9.2.1а).

Каждая из этих пар появится в системе неравенств (9.2.4) для определенного значения ik=i1,i2, ..., in, точно (а-3)! раз по числу возможных перестановок (а-3) элементов, т.к. элементы ik, ik+N, ik+a-1 для этих пар «неподвижны».

Кроме этого, в совокупностях пар обоих видов надо выделить пары ic, ic+1, т.е. пары элементов гамильтонова цикла (9.2.1а). Тогда можно считать, что каждая из этих пар появится в системе неравенств (9.2.4) для определенного значения ik=i1,i2, ..., in точно ((a-3)!-1) раз по числу появлений пар вида а) или б) и за вычетом появлений одной пары, находящейся в левой части неравенства (9.2.4).

Аналогично и для любой пары вида ic+N ic число появлений в системе неравенств (9.2.4) для определенного значения ik равно (а-3)!. Здесь надо учесть то обстоятельство, что ik и ik+a-1 «неподвижны», т.е. они не могут участвовать в парах вида ic+N ic.

Таким образом, каждая пара элементов вида ic ic+N, не образующая ребро, инцидентное гамильтонову циклу, а также каждая пара вида ic+N ic появятся в правой части системы неравенств, записанных для определенного значения ik, точно (а-3)! раз, а ребра, инцидентные гамильтонову циклу, точно ((а-3)!-1) раз.

Задавая последовательно значения ik от i1 до in, мы получаем каждый раз новые системы неравенств. При этом относительно любого ребра ic, ic+N участок ik, ik+1, ... , ik+a-1 «передвигается», вследствие чего любые пары ic+N ic или ic, ic+N участвуют в a-N(k+a-1-n-k+1=a-N) системах неравенств (9.2.4). То обстоятельство, что пары вида (ic+N, ic) с участием элементов ik и ik+a-1 в каждой системе неравенств невозможны, приводит к уменьшению числа появлений каждого такого вида пар ic+N ic в системе (9.2.4) для данного N на две.

Ребра ic ic+1 участвуют, таким образом, в (а-1) системах неравенств, если, конечно, (а-3)!-1 ? 1 или а ? 5, т.е., если они по условию вообще появляются в правой части системы неравенств для любого ik.

Отсюда очевидно, что любое ребро ?(ikik+N), N ? 1, графа будет повторяться в правых частях п систем неравенств (9.2.4) (а – N) раз для ik= i1, i2, ..., in.

Следовательно, правая часть системы (9.2.4) примет вид: