ТЕОРЕМА 1. Существование непустой гиперструктуры Г , сформированной эффективной процедурой, является необходимым и достаточным условием существования СВН для СКТ S1 и S2 .

ДОКАЗАТЕЛЬСТВО. Необходимость условия теоремы доказана выше.

Достаточность сформулированного условия докажем индукцией по числу пройденных ярусов. Утверждение, подлежащее доказательству, относится к любой вершине vj j -го яруса гиперструктуры (j = 1, ... , n - 2) и выражается равенством:

dj j

П = U Bi,(1)

i=1

где 77j - подструктура в ГС, приписанная вершине Vj ; Bij - i -е j-пересечение подструктур ярусов 1, 2, ... , j ; dj - число j-пересечений, объединенных в 77 .

Словесная формулировка утверждения: подструктура 7 j является объединением j-пересечений.

База индукции. Для вершин первого, второго и третьего ярусов (j = 1, 2, 3) равенство (1) безусловно выполняется (начиная с третьего яруса подструктуры получены с применением процедуры фильтрации).

Индукционный шаг. Пусть равенство (1) выполняется для всех вершин Vj при j < t; покажем, что оно справедливо и для любой вершины Vj при j = t +1 (3 < t < n - 3).

Для выделенной вершины Vt+1 рассмотрим любую смежную вершину Vt . При вычислении подструктуры-ребра 7 t,t+1 конкретизируется значение переменной Xt+3 ; пусть конкретизированное значение xt+3 равно b (b g {0, 1}). Подструктура 77t, по предположению индукции, является объединением t-пересечений Bi ( i = 1, 2, ... , dt ). В 77t можно выделить подструктуры: nt (b) и nt (— b), объединяющие, соответственно, t-пересечения со значением xt+3 = b и t-пересечения со значением xt+3 = — b . Равенство (1), согласно индукционной гипотезе, выполняется для вершины Vt и в том частном случае, если переменная xt+3 = b во всех подструктурах, участвующих в формировании подструктуры 7 t . Следовательно, выделение подструктуры 7 t (b) достигается следующими средствами: а) конкретизация переменной в вершине Vt : 77t (xt+3 — b); б) проецирование ярусов 1, 2, ... , t - 1 на подструктуру nt с xt+3 = b .

Но действия, указанные в п. п. а и б, в точности совпадают с теми, которые используются при вычислении подструктуры-ребра 7 t,t+1 в принятой процедуре построения ГС, следовательно, 7 t,t+1 = 7 t (b). С другой стороны, по определению подструктуры-ребра nt;t+1 = 77t n nt+1 и, следовательно, в подструктуру-вершину nt+1 по ребру (Vt , Vt+1) продвинуто объединение (t + 1)-пересечений, сформированных в подструктуре 7 t (b) .

Все приведенные рассуждения сохраняют свою силу и по отношению ко второму, возможно, существующему, ребру ГС, которое соединяет вершину Vt+1 с вершиной Vt t -го яруса. Итак, равенство (1) верно для всех вершин гиперструктуры.

Таким образом, любая непустая подструктура-вершина (n - 2)-го яруса представляет собой объединение (n - 2)-пересечений, т. е. совместных выполняющих наборов для СКТ S1 и S2 . Этот вывод завершает доказательство достаточности существования непустой гиперструктуры Г для существования СВН при двух СКТ.

5. Решение задачи 3-ВЫП в общей постановке

Обобщение эффективной процедуры с целью отыскания СВН для k структур компактных троек заключается в следующем. Базисная СКТ S1 и сопряженный с ней базисный граф G1 используются для параллельного формирования системы гиперструктур (СГС): Г2 (на основе пары S1 и S2), Г3 (на основе пары S1 и S3), ... , Гк (на основе пары S1 и Sk). Каждая ГС Гг (г = 2, ... , к) строится по сформулированным выше правилам формирования гиперструктуры, которые дополняются согласующими правилами. Примем соглашение, что термин одноименные применим ко всем параллельно формируемым подструктурам в гиперструктурах Г2 , ... , Гк , относящимся к копиям одной вершины или одного ребра базисного графа, или к копиям пар подструктур-вершин при бинарных операциях, независимо от того, являются эти подструктуры промежуточными или результирующими при построении СГС. Промежуточные подструктуры появляются, в частности, при выполнении процедуры фильтрации. Назовем одноименными j-пересечениями j-пересечения множеств одноименных подструктур-вершин в ГС Г2 , ... , Гк . Параллельное формирование гиперструктур означает, что каждый шаг построения подструктур в ГС, предусмотренный процедурой, выполняется для каждой из к - 1 формируемых ГС, и только после этого осуществляется переход к следующему шагу. Согласующие правила формулируются следующим образом:

1.Все одноименные параллельно формируемые подструктуры (как промежуточные, так и результирующие) унифицируются.

2.Согласованное продвижение подструктуры-вершины 77j j -го яруса по ребру (vj , Vj+1) в каждой из ГС Г2 , ... , Гк заключается в конкретизации переменной Xj+3 —» b подструктуры 77j по значению b, указанному для этой переменной в вершине vj+1 базисного графа, и последующем выделении средствами фильтрации и унификации из 77j подструктуры, объединяющей одноименные для всех гиперструктур Г2 , ... , Гк j-пересечения с Xj+3 = b . В результате продвижения для ребра (vj , Vj+1) формируется подструктура-ребро 7 j,j+1 .

3.При построении гиперструктуры из базисного графа удаляются ребра и вершины, не имеющие копий.

Таким образом, гиперструктуры Г2 , Г3 , ... , Гк могут быть непустыми только одновременно. Эффективную процедуру, реализующую согласующие правила при формировании системы ГС, назовем системной эффективной процедурой.

Для обоснования согласующих правил обратимся к свойствам оптимальной системы гиперструктур. Концепция оптимальной СГС - потенциально существующего объекта, который является "идеальным" продуктом предлагаемого алгоритма - ключ к пониманию главной идеи работы и ее воплощения (аналогичный объект был рассмотрен в разделе 4). Каждая гиперструктура оптимальной СГС сопряжена с оптимальной

СКТ, объединяющей только СВН системы на основе индивидуальной перестановки переменных. Применение эффективной процедуры, сформулированной в разделе 4, для построения k - 1 гиперструктур на базе оптимальных СКТ (гипотетического, но логически очевидного) автоматически приводит к соблюдению сформулированных согласующих правил, поскольку во всех оптимальных ГС каждая подструктура-вершина любого яруса по построению является объединением (n - 2)-пересечений.

ТЕОРЕМА 2. Существование СГС - непустых гиперструктур Г2 , ... , Гк , сформированных системной эффективной процедурой, является необходимым и достаточным условием существования совместных выполняющих наборов для СКТ S1 , S2 Sk и, следовательно, необходимым и достаточным условием выполнимости формулы F .

ДОКАЗАТЕЛЬСТВО. Необходимость существования гиперструктур Г2 , ... , Гк обусловлена следствием 1 из раздела 4, так как, если в процессе формирования СГС обнаруживается хотя бы одна пустая гиперструктура, СВН системы, ассоциированные с одноименными маршрутами в ГС, по построению отсутствуют.

Достаточность сформулированного условия докажем индукцией по числу пройденных ярусов. Утверждение, подлежащее доказательству, относится к любым одноименным вершинам vj j -го яруса (j = 1, ... , n - 2) гиперструктур Г2 , ... , Гк и выражается соотношениями:

dj (Гг) .

nj (Гг) = U , r = 2, ... , к ,(2)

i =1

где:

Bij (Г2) о Bij (Г3) о ... о Bij (Гк ) ,(3)

dj (Г2) = dj (Г3) = ... = dj (Гк) .(4)

В соотношениях (2) - (4) используются обозначения: 7tj (Гг) , r = 2 , ... , к , - одноименные подструктуры вершин j -го яруса в системе ГС;

в/ (Гг ) - i -е j-пересечение подструктур ярусов 1, 2, ... , j в гиперструктуре Гг ; "о" - знак, обозначающий одноименность j-пересечений, стоящих слева и справа от него;

dj (Гг) - число j-пересечений, объединенных в nj (Гг) .

Словесная формулировка утверждения: одноименные подструктуры j -го яруса в гиперструктурах Г2 , ... , Гк являются объединениями одноименных j-пересечений.

База индукции. Для вершин первого, второго и третьего ярусов (j = 1, 2, 3) соотношения (2) - (4) безусловно выполняются.

Индукционный шаг. Пусть соотношения (2) - (4) выполняются для всех вершин Vj при j < t ; покажем, что они справедливы и для любой вершины vj при j = t + 1 (3 < t < n - 3).

Для выделенной вершины vt+1 в каждой из ГС Гг , r = 2 , ... , к , рассмотрим любую смежную вершину vt . При вычислении подструктуры-ребра nt;t+1 конкретизиру-