Системная технология

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

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

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

А ≤ В.

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

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

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

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

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

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

i_k, i'_k+1, i'_k+2, …, i'_k+a-2, i_k+a-1 (9.2.5.)

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

Следует учесть также, что одна из этих последовательностей, а именно i₁, i₂, i₃, …, i_k+a-1 находится в левой части этих неравенств.

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

а) i_ci_c+N при с ≠ k; с+п < к+а-1; п>1, п ≤ а-2; это пары элементов в (9.2.5), не содержащие элементов i_k, i_k+а-1 и тех элементов (i₁, i₂, i'₂ , i₃, i'₃, i₄ и т.д.), которые входят в гамильтонов цикл (9.2.1а).

Каждая из пар этого вида появится в системе неравенств (9.2.4) для определенного значения i_k=i₁,i₂, …, i_n, точно (а-3)(а-4)! раз – по числу (а-4)! перестановок (а-4) элементов, т.е. элементов последовательности (9.1.5) за вычетом элементов i_k, i_k+a-1, i_c, i_c+N для каждого из (а-3) возможных положений пары i_c, i_c+N в последовательности (9.2.5).

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

Каждая из этих пар появится в системе неравенств (9.2.4) для определенного значения i_k=i₁,i₂, …, i_n, точно (а-3)! раз по числу возможных перестановок (а-3) элементов, т.к. элементы i_k, i_k+N, i_k+a-1 для этих пар «неподвижны».

Кроме этого, в совокупностях пар обоих видов надо выделить пары i_c, i_c+1, т.е. пары элементов гамильтонова цикла (9.2.1а). Тогда можно считать, что каждая из этих пар появится в системе неравенств (9.2.4) для определенного значения i_k=i₁,i₂, …, i_n точно ((a-3)!-1) раз по числу появлений пар вида а) или б) и за вычетом появлений одной пары, находящейся в левой части неравенства (9.2.4).

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

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

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

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