Целостный метод системной технологии и системная экология

Здесь i΄₂, i΄₃,…, i΄_a-1 — одна из перестановок чисел i₂, i₃, …, i_a-1, P — множество всех перестановок этих чисел.

Очевидно, что если это условие не выполняется для каких-либо значений a и i, то существует гамильтонов цикл с меньшей длиной пути обхода вершин i₁, i₂, i₃, …, i_a-1,i_a . Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i₁, i₂, i₃, …, i_a для любого a, имеющего значения в пределах от 4-х до n.

Значения a не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины поcледовательно в одном из двух возможных вариантов обхода: i₁,i₂,i₃,i₄ или i₁,i₃,i₂,i₄ .

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

i₁, i₂, i₃, …, i_n, i₁. (1.а)

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

μ (i_ki_k+1) + μ (i_k+1i_k+2) + μ (i_k+2i_k+3) ≤

≤ μ (i_ki_k+2) + μ (i_k+2i_k+1) + μ (i_k+1i_k+3).

Условие (2) необходимо проверить для всех i_k = i₁, i₂, …, i_n и, если оно для всех i_k справедливо, то это необходимое и достаточное условие того, что гамильтонов цикл 4-оптимален. Просуммировав левые и правые части неравенств, получающихся при значениях i_k = i₁, i₂, …, i_n, получаем необходимое условие 4-оптимальности в виде:

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

Если гамильтонов цикл a₁-оптимален, то он a₂-оптимален для любого a₂1.

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

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

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

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

μ (i_k,i_k+1, …, i_k+a-1) = μ (i_k, i_k+1) + μ (i_k+1i_k+2 ) + … + μ (i_k+a-2 i_k+a-1).

μ (i_k, i΄_k+1, …, i΄_k+a-2, i_k+a-1) = μ (i_k, i΄_k+1) + μ (i΄_k+1, i΄_k+2) + … + μ (i΄_k+a-2, i_k+a-1).

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

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

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

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

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

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

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

i_k, i΄_k+1, i΄_k+2, …, i΄_k+a-2, i_k+a-1 (5)

задаваемых (a-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+a-1:

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

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