1.Формирование подструктур-вершин первого яруса путем конкретизации в СКТ S2 переменных первой компактной тройки в соответствии со значениями, указанными в одноименных вершинах базисного графа G1 . Если первый ярус отсутствует (все подструктуры пусты), то искомая ГС Г = 0 (раннее завершение процедуры), иначе - переход к п. 2, описывающему цикл.

2.Для каждого из значений j = 1, ... , n - 3 - выполнение следующих двух пунктов, при условии, что очередной построенный ярус не пуст (что обнаруживается в п. 2.2).

2.1.Продвижение подструктур-вершин j -го яруса по ребрам, указанным в базисном графе, с формированием подструктур-ребер, соединяющих вершины j -го и (j + 1)-го ярусов.

2.2.Формирование подструктур-вершин (j + 1)-го яруса гиперструктуры с использованием подструктур-ребер, определенных в п. 2.1. Если (j + 1)-й ярус пуст - завершение процедуры с результатом Г = 0 . Если (n - 2) -й ярус не пуст - завершение процедуры с результатом Г ^ 0 .

3.В процессе построения гиперструктуры базисный граф корректируется в соответствии с изменениями каркаса ГС, что сохраняет изоморфизм графов G1 и G2 .

На рис. 2 представлена гиперструктура для СКТ S1 и S2 , заданных таблицей 3. Совпадающие подструктуры смежных вершин каркаса записаны по одному разу.

Рассмотрим общий случай, когда на основе СКТ S1 и S2 сформирована непустая ГС. Особенность гиперструктуры состоит в том, что допустимый маршрут (далее маршрут) в ней определяется двумя факторами: а) наличием последовательности вершин и ребер; б) возможностью продвижения подструктуры первого яруса по этой последовательности.

Будем говорить, что маршрут ц в гиперструктуре Г существует, если некоторая выделенная подструктура п1 первого яруса продвигается по ц , т. е. для последовательности вершин каркаса v1, v2 , ... , vn-2 , соединенных ребрами, пересечение подструктур-вершин п1 n п2 п ... n nn-2 - не пусто. Отметим, что каждый шаг продвижения п1 по маршруту ц сопряжен с добавлением одного операнда в формируемое (n - 2)-пересечение, а промежуточным продуктом продвижения п1 (на j -й ярус) является j -пересечение л) = п1 n п2 п ... n л .

ПРЕДЛОЖЕНИЕ. В результате продвижения подструктуры л1 по любому маршруту ц гиперструктуры Г, в конечной подструктуре nn-2 значения всех переменных формулы F становятся определенными и задают выполняющий набор, сопряженный с ц , общий для СКТ S1 и S2 .

ДОКАЗАТЕЛЬСТВО. По построению ГС, в каждой подструктуре первого яруса по меньшей мере три переменных имеют определенные значения. При каждом продвижении подструктуры по ребру определяется значение одной новой переменной, если оно до этого шага еще не было определенным. В части маршрута ц , заканчивающейся на j -м ярусе, определенными являются значения по меньшей мере j + 2 переменных продвигаемой ПС. Таким образом, на (n - 2)-м ярусе значения всех n перемен-

ных определены, и nn-2 содержит в точности n - 2 строки, т. е. является элементарной СКТ. С другой стороны, те же значения переменных определены конкатенацией троек, записанных в вершинах базисного графа, включенных в д . Итак, полученные значения переменных задают СВН для S1 и S2 и, следовательно, каждому маршруту в гиперструктуре Г соответствует СВН.

h g b i

00 0

11 0

00 1

10 1

0 1 0 1 0 0 1 0 1 0 0 1 0 1 1

01

11 1 1

f c d

a b c

0 0 1

h g b e a f c d

00 0

11 0

00 1

10 1

0 1 0 0 1 1 1 0 1

1 1 1

01 1

11 1

1 1 0

h g b e a f c d

00 0

11 0

00 1

10 1

0 1 0 0 1 1 1 0 1

1 1 1

01 1

11 1

1 1 0

b c d

0 1 0

c d e

1 0 1

d e f

0 1 1

h g b e a

0 0 0

0 0 1

0 10

0 11

10 1

1 1 1

01 1

11 1 1 1 1 1

f c d

g 0

f g h

1 0 0

h g b e a f c d

00 0

11 0

00 1

10 1

0 1 1

1 1 1

1 11

11

11

h g b e a f c d

00 0

11 0

00 1

10 1

0 10

0 11

10 0

10 1

1 1 1

0 0 1

01 1

11 1

01 1

11 1

h g b e a f c d

00 0

11 0

00 1

10 1

0 1 0 0 1 1 1 0 1

1 1 1

01 1

11 1

1 1 1

a b c 1 0 1

b c d 0 1 1

c d e

1 1 1

d e f

1 1 1

h g b e a f c d

00 0

11 0

00 1

10 1

0 1 0d e f

1 0 0 1 1 0 0 0 1 0 1 1

h g b e a f c d

1 1 0

1 0 1 0 1 0 1 0 0 0 0 1 0 1 1

e f g

1 0 1

f g

h

0 1 1

Рис. 2. Гиперструктура

Из приведенных рассуждений следует и обратное утверждение: каждому СВН для S1 и S2 в гиперструктуре Г соответствует сопряженный с этим СВН допустимый маршрут. Действительно, СВН в форме элементарной СКТ (подструктуры СКТ S2) продвигается без изменения по единственному маршруту, который определяется общими для S1 и S2 значениями переменных.

СЛЕДСТВИЕ 1. Множество маршрутов и, соответственно, (n - 2)-пересечений, существующих в гиперструктуре, взаимно однозначно отображается на множество выполняющих наборов, общих для СКТ S1 и S2 .

СЛЕДСТВИЕ 2. Подструктура первого яруса гиперструктуры, не содержащая совместных выполняющих наборов для СКТ S1 и S2 , не продвигается на (n - 2)-й ярус ни по какой последовательности вершин и ребер и, следовательно, не может формировать никакого маршрута.

Для рассматриваемого примера по гиперструктуре, представленной на рис. 2, можно определить пять маршрутов и, соответственно, пять СВН:

h g b e a f c d 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0

00 0 1 1 1 1 1

11 0 1 0 0 1 1 .

Из следствия 1 вытекает, что существование непустой гиперструктуры является необходимым условием существования СВН.

Подход к доказательству достаточности этого условия базируется на концепции оптимальной гиперструктуры. Оптимальная ГС - продукт эффективной процедуры, примененной к оптимальным СКТ S10 и S20 , определение которых дано в начале раздела. Как и СКТ S10 и S20 , оптимальная ГС - потенциально существующий комбинаторный объект, по построению непустой тогда и только тогда, когда СВН для исходных СКТ S1 и S2 существуют. Главным свойством оптимальной ГС является то, что каждая подструктура-вершина любого яруса, также по построению, представляет собой объединение (n - 2)-пересечений. Поставим задачей формирование на основе СКТ S1 и S2 гиперструктуры, к подструктурам-вершинам которой предъявлены менее жесткие требования: каждая подструктура-вершина j -го яруса должна представлять собой объединение j -пересечений и, соответственно, каждая подструктура-вершина (n - 2)-го яруса - объединение (n - 2)-пересечений. Ясно, что цель обеспечения достаточного условия существования СВН будет при этом достигнута. Для доказательства того, что поставленная задача решается эффективной процедурой, служит следующая теорема.