Целостный метод - теория и практика

? (ikik+1) + ? (ik+1ik+2) + ? (ik+2ik+3) ?  ? (ikik+2) + ? (ik+2ik+1) + ? (ik+1ik+3).  (2)

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

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

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

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

Для каждого значения k

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

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

? (ik,ik+1, ..., ik+a-1) = ? (ik, ik+1) + ? (ik+1ik+2) + ... + ? (ik+a-2 ik+a-1).

? (ik, i?k+1, ..., i?k+a-2, ik+a-1) = ? (ik, i?k+1) + ? (i?k+1, i?k+2) + ... + ? (i?k+a-2, ik+a-1).

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

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

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

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

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

Для того, чтобы получить выражение для правой части условия (4), необходимо найти число появлений ребер графа вида (ic, ic+N

) в каждой системе из ((a-1)!-1) неравенств, задаваемых определенным значением k, а также во всех системах этих неравенств, получаемых при изменении ik от i1 до in.

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

ik, i?k+1, i?k+2, ..., i?k+a-2, ik+a-1   (5)

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

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

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

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

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

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