Известия РАН. Теория и системы управления, 2021, № 4, стр. 84-93

Введение. В системном анализе используются двухуровневые и трехуровневые структурные модели систем, построенных из однотипных элементов и образованных блоками, характеризуемыми одинаковыми количествами вхождений в них элементов, а также одинаковыми количествами блоков, в которые входят определенные совокупности элементов. Такие модели изучаются в комбинаторном анализе, как так называемые комбинаторные блок-схемы. Теория комбинаторных блок-схем возникла при организации сравнительных экспериментов в аграрной науке: по определенной схеме выбирались наименования культур для их совместного выращивания на определенных полях. Этим достигалось совмещение по времени их испытаний в различных условиях. Далее комбинаторные блок-схемы применялись для тестирования групп крови, в настоящее время подобные исследования практикуются в генетике. В компьютерных науках на их основе изучаются распределенные вычислительные системы и схемы распределения ключей в них. На основе этих моделей отслеживаются связи между элементами сложной системы и при необходимости прогнозируются цепочки таких связей. Теория комбинаторных блок-схем отражена в монографии [1] и учебнике [2], в англоязычных изданиях наиболее востребованы книги [3, 4]. Комбинаторная блок-схема задается множеством элементов и множеством блоков, состоящих из элементов. Множество имен ее блоков принимается в качестве множества элементов двойственной по отношению к ней блок-схемы, множество блоков которой находится во взаимно-однозначном соответствии с множеством элементов исходной блок-схемы, а сами ее блоки являются множествами имен блоков исходной блок-схемы, содержащих элемент, который соответствует блоку двойственной блок-схемы. Например, если элементами выступают индексы сельскохозяйственных культур, а блоки состоят из индексов культур, возделываемых на наделах определенного поля, то каждый блок двойственной блок-схемы (дуальный блок) содержит имена полей, на наделах которых возделывается соответствующая ему культура. В иной интерпретации элементами могут быть компьютеры компьютерной сети, блоками – совокупности компьютеров отдельных локальных сетей, тогда дуальные блоки содержат локальные сети, в которых присутствует соответствующий дуальному блоку компьютер. Описанное соответствие комбинаторной и двойственной комбинаторной блок-схемы называется в данной работе правилом двойственности. Наряду с явными представлениями совокупностей блоков перечислением входящих в них элементов применяются представления комбинаторных блок-схем бинарными матрицами инцидентности и двудольными мультиграфами. Строки матрицы соответствуют элементам, а столбцы – блокам комбинаторной блок-схемы. Соответственно вершины одной доли двудольного графа суть элементы, а вершины другой доли – блоки. Ребра графа соответствуют вхождениям элементов в блоки. Матричные и графовые представления двойственной комбинаторной блок-схемы получаются транспонированием матрицы инцидентности или перестановкой долей двудольного графа исходной блок-схемы. В российской литературе данное направление прикладного комбинаторного анализа представлено, например, работами [5–7], где изучаются в основном симметричные комбинаторные схемы, в которых количества элементов и узлов совпадают, или так называемые квазиполные двудольные графы. Подобные работы важны для поиска алгоритмов вычисления комбинаторных блок-схем данного вида, инвариантных для применения в других областях. В [5, 7] даются матричные способы построения комбинаторных блок-схем, в любых двух блоках которых имеется единственный общий элемент и каждая пара элементов присутствует точно в одном блоке. Такие комбинаторные блок-схемы называются проективными плоскостями размерности два. В более сложных проективных плоскостях размерности три любые два элемента присутствуют в большем количестве блоков. Этим достигается моделирование множественных связей в сложных системах. Графовые представления таких проективных плоскостей даны в [6]. Трехуровневыми по построению являются линейные и квадратичные трансверсальные комбинаторные блок-схемы [1, 8], применяемые, например, в беспроводных сенсорных сетях [8].

Порядок n = p^l и размерность d комбинаторной блок-схемы являются основными параметрами проективных плоскостей. По ним определяются мощности v множеств элементов и блоков, числа k элементов в блоке, а также количество блоков, в которые входит любая выбранная пара элементов; оно же – число элементов в пересечении любых двух блоков, а также число блоков, всегда имеющих единственный общий элемент. При синтезе трансверсальных блок-схем параметр k, определяющий число элементов в блоке, выбирается независимо, но при ограничении d ≤ k ≤ n. По порядку n = p^l и размерности d трансверсальной блок-схемы определяются мощность множества элементов и мощность множества блоков, а также порог пересечения – наибольшее возможное число элементов в пересечении двух блоков.

Применение комбинаторных блок-схем позволяет совмещать изучение отдельных элементов параллельно в составе определенным образом собранных их подмножеств. Примером может служить осуществление 376 тестов с комбинаторными блоками, состоящими примерно из 5000 клонов вместо индивидуальных тестов с 220 000 клонами, в Лос-Аламосcкой национальной лаборатории [9]. На основе комбинаторных блок-схем строятся комбинаторные библиотеки кодов аминокислот [10]. Применение комбинаторных методов для синтеза криптографических протоколов отражено в [11, 12]. Применению комбинаторных блок-схем в вычислительной технике посвящены упомянутые выше [5, 6]. В [7] дана интерпретация симметричной комбинаторной блок-схемы при моделировании многокомпонентной системы связи и подчеркнут универсальный характер таких моделей, допускающих подобные интерпретации в различных приложениях. Отметим также, что, согласно [12], изучаемые в настоящей работе алгоритмы синтеза трансверсальных комбинаторных схем применимы к синтезу ортогональных массивов и множественных латинских квадратов.

Приведенные в статье численные примеры получены с использованием системы компьютерной алгебры Sage [13] посредством алгебраического процессора МЭИ [14].

В разд. 1 дана постановка задачи настоящей работы. Раздел 2 является расширенным изложением доклада [15] на XIX Международной конференции “Проблемы теоретической кибернетики”. Здесь рассматриваются числовая и алгебраическая формализации и аналитические решения задач вычисления блоков для циклических и ациклических проективных плоскостей, линейной и квадратичной трансверсальных блок-схем и двойственных схем. В заключениe обсуждаются особенности предложенного метода синтеза сложных систем определенного класса и возможности использования предлагаемых методов для решения производных задач.

1. Постановка задачи. Разнообразие технических и иного рода систем, моделируемых комбинаторными блок-схемами, требует единого подхода к их формализации. Универсальным методом унификации представлений систем перечислительного характера является нумерация элементов и блоков. Тогда в качестве множеств элементов, как и номеров блоков, можно принять множества начальных неотрицательных целых чисел. Такая нумерация будет удовлетворять отмеченному выше правилу двойственности, если по номеру блока однозначно вычисляется множество входящих в этот блок элементов (чисел), а по элементу (числу) однозначно вычисляется дуальный блок, т.е. множество номеров блоков, содержащих этот элемент. В настоящей работе описаны нумерации такого рода применительно к циклическим и ациклическим плоскостям, а также трансверсальным схемам, порядок которых есть простое число или степень простого числа. Они несколько различаются, но в каждом случае реализуются на основе алгебраического подхода, когда элементам и блокам взаимно-однозначно сопоставляются просто вычисляемые их алгебраические образы, числовые прообразы которых также легко рассчитываются. Применение нумерации элементов и блоков комбинаторных блок-схем позволяет сделать их представления более наглядными, скрыв особенности их алгебраической природы, а также создать условия для независимого и параллельного вычисления блоков на основе (беспереборного) построения алгебраических идентификаторов блоков по заданному номеру блока. В роли таких идентификаторов блоков циклических проективных плоскостей выступают разностное множество Зингера и номер блока. В качестве идентификаторов блоков ациклических проективных плоскостей используются нормированные базисы двумерных или соответственно трехмерных подпространств векторного пространства размерности три или четыре над конечным полем порядка p^l, множества числовых образов нормированных элементов которых как раз и являются блоками проективной плоскости. В качестве элементов выступают числовые нормированные образы базисов одномерных подпространств. Алгебраическими идентификаторами блоков трансверсальных комбинаторных блок-схем являются d-наборы (т.е. пары или тройки) элементов поля порядка p^l. Использование алгебраических идентификаторов позволяет строить блоки распределенно, т.е. независимо один от другого, избегая необходимости анализа их матричных или графовых представлений в полном объеме, как в работах [5–7]. Этим предлагаемый алгебраический подход отличается и от алгебраического метода в публикации [3], где в качестве элементов ациклической проективной плоскости рассматриваются одномерные подпространства, а блоками являются совокупности соответствующих элементам блока одномерных подпространств, объединение которых есть соответствующее блоку двумерное пространство.

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

2. Алгебраические методы построения некоторых комбинаторных блок-схем. Рассмотрим некоторые разновидности комбинаторных блок-схем, используемых в качестве структурных моделей ряда технических или иного рода систем. Уравновешенная неполная блок-схема (УНБС) [1, 2] определяется на конечном множестве элементов X мощности ${v}$ и образована как множество A собственных подмножеств, называемых блоками. Каждый блок состоит из k элементов, каждый элемент из X присутствует в r блоках, а каждая пара различных элементов встречается в λ блоках. УНБС имеют сокращенное обозначение (${v}$, k, λ)-УНБС. Остальные параметры восстанавливаются по нему на основе элементарных соотношений bk = ${v}$r и r(k – 1) = λ(${v}$ – 1), где b – число блоков УНБС. Вот некоторые УНБС: (n² + n + 1, n + 1, 1)-УНБС называется проективной плоскостью размерности два и порядка n. Она обозначается PP(2,n). Проективная плоскость размерности три и порядка n PP(3,n) – это (n³ + n² + n + 1, n² + n + 1, n + 1)-УНБС. Блоки таких УНБС попарно имеют λ общих элементов. Другой разновидностью комбинаторных блок-схем являются так называемые трансверсальные блок-схемы. Они характеризуются тем, что попарно блоки имеют не более одного общего элемента, но для любых двух непересекающихся блоков найдется μ, μ > 0, других блоков, имеющих по λ общих элементов с каждым из них. Формализованное описание трансверсальных блок-схем будет дано ниже.

2.1. Построение блоков и дуальных блоков циклических проективных плоскостей. Строение блоков циклической проективной плоскости PP(2,n) определяется (n² + n + 1, n + 1, 1)-разностным множеством − совокупностью n + 1 элементов группы ${{Z}_{{{{n}^{2}} + n + 1}}}$, такой, что любой ненулевой элемент этой группы можно получить как разность некоторых из этих элементов. Одну из разновидностей такого множества – разностное множество Зингера найдем как множество дискретных логарифмов элементов поля $F_{n}^{3}$, являющихся многочленами степени менее двух [1]. Для этого используется примитивный многочлен степени три над полем GF(n) и его корень x, т.е. примитивный элемент поля GF(n³). Разностное множество Зингера образуется из показателей степеней  j этого элемента, при которых степени многочленов x^j не превышают 1. Множество элементов проективной плоскости PP(2,n) есть множество из n² + n + 1 неотрицательных целых чисел, в качестве блока номер 0 можно принять множество чисел, составляющих разностное множество Зингера, а блок номер 0 двойственной проективной плоскости PP(2,n) образуется противоположными вычетами, т.е. числами, которые находятся вычитанием элементов нулевого блока проективной плоскости из 0 по модулю n² + n + 1. Тогда i-й блок, i ∈ {1, …, n² + n}, как проективной плоскости, так и двойственной проективной плоскости получается прибавлением единицы по модулю n² + n + 1 к каждому элементу их i – 1-го блока. Поэтому справедливо следующее утверждение.

Утверждение 1 [15]. Блок, имеющий номер j, циклической проективной плоскости PP(2, n) вычисляется последовательным прибавлением его номера по модулю n²+ n + 1 к элементам (n² + n + 1, n + 1, 1)-разностного множества Зингера. Блок, имеющий номер  j, циклической двойственной проективной плоскости DPP(2,n) получается последовательным вычитанием из его номера  j по модулю n²+ n + 1 элементов этого разностного множества.

Для вычисления блоков циклической проективной плоскости PP(3,n) и двойственной циклической проективной плоскости DPP(3,n) используется (n³ + n² + n + 1, n² + n + 1, n + 1)-разностное множество Зингера. Это совокупность n² + n + 1 элементов группы ${{Z}_{{{{n}^{3}} + {{n}^{2}} + n + 1}}}$, такая, что любой ненулевой элемент этой группы можно получить n + 1-кратно как разность по модулю n³ + + n² + n + 1 различных n + 1 пар некоторых из этих n² + n + 1 элементов. Вычисление этого разностного множества Зингера производится как множества дискретных логарифмов элементов поля $F_{n}^{4}$, являющихся многочленами степени менее трех [1]. Для этого используется примитивный многочлен степени четыре над полем GF(n) и его корень x, т.е. примитивный элемент поля GF(n⁴). Разностное множество Зингера образуется из показателей степеней  j этого элемента, при которых степени многочленов x  ^j не превышают двух. Алгебраическая среда для этих вычислений удобно образуется средствами системы компьютерной алгебры Sage. Вычисления блоков и дуальных блоков производятся по модулю n³ + n² + n + 1. Тогда множество элементов проективной плоскости PP(3,n) есть множество из n³ + n² + n + 1 неотрицательных целых чисел, в качестве блока номер 0 можно принять множество чисел, составляющих разностное множество Зингера. Нулевой блок двойственной проективной плоскости DPP(3,n) образуется противоположными вычетами, т.е. числами, которые получаются вычитанием элементов нулевого блока проективной плоскости PP(3,n) из 0 по модулю n³ + n² + n + 1. Тогда i-й блок, i ∈ {1, …, n³ + n² + n}, как проективной плоскости PP(3,n), так и двойственной проективной плоскости DPP(3,n) получается прибавлением единицы по модулю n³ + n² + n + 1 к каждому элементу их i–1-го блока. Поэтому справедливо следующее утверждение.

Утверждение 2 [15]. Блок, имеющий номер j, циклической проективной плоскости PP(3,n) вычисляется последовательным прибавлением его номера по модулю n³ + n² + n + 1 к элементам (n³ + n² + n + 1, n² + n + 1, n + 1)-разностного множества Зингера. Блок, имеющий номер  j, циклической двойственной проективной плоскости DPP(3.n) получается последовательным вычитанием из его номера  j по модулю n³ + n² + n + 1 элементов этого разностного множества.

Как видим, алгебраическими идентификаторами блоков циклической проективной плоскости размерности два или три выступают разностное множество Зингера и номер блока.

Пример 1. Циклическая проективная плоскость PP(3,2) – это (15,7,3)-УНБС:

Двойственная циклическая проективная плоскость DPP(3,2) имеет 15 дуальных блоков:

2.2. Построение блоков и дуальных блоков ациклических проективных плоскостей. Пусть F_n – поле порядка n = p^k, а x – его примитивный элемент, F(n^d + 1) – его алгебраическое расширение степени d + 1, рассматриваемое как векторное пространство V размерности d + 1, а также как поле, порождаемое примитивным полиномом степени d + 1 над полем F_n. Множество V* = V\{0} по отношению коллинеарности разбивается на классы эквивалентности. В качестве представителей этих классов удобно выбрать нормированные многочлены множества V*. Их совокупность $V{\text{'}}$ составляет проективное пространство размерности d. Его элементы являются проективными подпространствами нулевой размерности, или точками (представителями классов коллинеарности – подпространств единичной размерности векторного пространства V). Множества из d различных точек образуют базисы линий проективного пространства и одновременно нормированные базисы подпространств размерности d векторного пространства V. Имеется

точек и такое же количество линий. Множества точек и линий образуют проективную плоскость PP(d,n) размерности d и порядка n. Будем использовать следующие методы нумерации элементов векторных пространств размерности s и проективных пространств размерности s – 1. Номерами ненулевых элементов поля F_n считаются их индексы по основанию образующего элемента x, а нулевому элементу присваивается номер 0 (т.е. полагаем, что индекс нулевого элемента поля равен нулю: ind 0=0). Элементам e = (e₀, …, e_s – 2, e_s − 1) ∈ F(n^s) присвоим номера

При этом числовым образом векторного пространства $F_{n}^{s}$ будет множество $\{ \overline {0,{{n}^{s}} - 1} \} $.

Номер ψ(e) элемента e = (e₀, e₁, …, e_s – 2, 1) проективного пространства размерности s – 1 будем определять формулой

полагая, что $\hat {e}$ = (e₀, e₁, …, e_s − 2), ψ(1) = 0, N₀ = 1. Нумерации и являются биекциями и, следовательно, обратимы: где (i₀, …, i_s − 2, i_s – 1) есть набор коэффициентов разложения числа M по степеням числа n; где (i₀, …, i_s – 2) есть набор коэффициентов разложения по степеням n числа M = $M{\text{'}}$ – N_s – 2. При такой нумерации получаем каноническое представление проективной плоскости, т.е. (n² + n + 1, n + 1, 1)-УНБС как комбинаторной блок-схемы: множество X элементов – это множество неотрицательных целых чисел ${{\overline {0,\;{{n}^{2}} + n} }^{{}}}$ (образов точек), а множество B блоков – это множество наборов B номеров точек, составляющих линии,– образы линий. Ниже будет показано, что блоки также можно упорядочить, пронумеровав их начальными неотрицательными целыми числами $\overline {0,\;{{N}_{2}} - 1} $.

Для вычисления блоков будем использовать их алгебраические идентификаторы, базисы линий в проективном пространстве размерности два, образованные парами многочленов (e⁽¹⁾, e⁽²⁾). Пусть первыми элементами таких пар являются многочлен (1) нулевой степени или нормированные многочлены (e₀, 1) первой степени. Вторые элементы e⁽²⁾ базисов остальных блоков подберем из числа многочленов, не принадлежащих алгебраическим замыканиям других базисов с тем же первым элементом e⁽¹⁾. Пары многочленов, соответствующие базисам линий с номером t, представлены в табл. 1.

Алгебраические замыкания базисов в проективном пространстве суть его линии, а их образы – блоки проективной плоскости на множестве X. По номерам $\psi $(e⁽¹⁾) и $\psi $(e⁽²⁾) первого и второго элементов базиса можно определить порядковый номер N($\psi $(e⁽¹⁾), $\psi $(e⁽²⁾)) порождаемой им линии и, следовательно, номер ее числового образа, т.е. блока:

При этом блоки получают анонсированные выше номера $\overline {0,\;{{N}_{2}} - 1} $.

Алгебраическое замыкание 〈{e⁽¹⁾, e⁽²⁾}〉 базиса можно вычислить, добавляя линейные комбинации e⁽²⁾ + x^te⁽¹⁾, t = $\overline {1,n - 1} $, поскольку все элементы блока являются нормированными многочленами. В этом случае вычисляется и соответствующий блок

Пример 2. Представим числовые образы базисов линий проективной плоскости (21, 5, 1) списком пар элементов, упорядоченных по возрастанию номеров порождаемых базисами блоков:

Вычислим, например, блок B₁₂ по образу (2,8) линии (ψ^-1(2), ψ^-1(8)) как образ замыкания:

Отсюда

По номеру j блока можно определить образы (номера) первого n₁(j) и второго n₂(j) элементов базиса его прообраза:

Таким образом, доказано следующее утверждение.

Утверждение 3 [15]. Блок, имеющий номер  j, проективной плоскости можно получить по формуле

Заметим, что число 0 имеется в блоках ${{B}_{0}},{{B}_{1}},{{B}_{2}},\; \ldots ,\;{{B}_{n}}$, содержащих числа $\overline {0,n} $, а числа $i$, $1 < i < n$ включаются в блок B₀ и блоки ${{B}_{{tn + i}}}$, $t = \overline {1,n} $. Каждое из остальных чисел $j \in {\mathbf{X}}$присутствует в n + 1 блоках, каждый раз с одним из чисел $\overline {0,n} $. Если $j \leqslant 2n$, то  j есть второй элемент блока, т.е. числовой образ $\psi ({{{\mathbf{e}}}^{{(2)}}})$ второго элемента базиса, который можно определить по  j и числовому образу $\psi ({{{\mathbf{e}}}^{{(1)}}})$ первого элемента базиса:

Если $j > 2n$, то оно есть образ $3,4,\; \ldots n$-го или n + 1-го элемента блока. При знании первого элемента, применяя обращенное правило его вычисления по первому и второму элементам, получаем второй элемент блока.

Утверждение 4 [15]. Множество номеров блоков проективной плоскости, содержащих заданный элемент s, представимо формулой

где

Проективные плоскости большей размерности строятся аналогично. В частности, базисы прообразов блоков для PP(3,n) представлены в табл. 2.

Исходя из этого можно сформулировать утверждения, аналогичные рассмотренным в данном разделе применительно к проективным плоскостям PP(3,n).

2.3. Построение блока трансверсальной блок-схемы по его номеру и множества блоков, содержащих данный элемент. Линейная трансверсальная комбинаторная блок-схема TD(k,n) [1, 3] строится из элементов k попарно не пересекающихся множеств w_i, содержащих по n элементов, и состоит из n² множеств Y_j,  j = $\overline {1,{{n}^{2}}} $, содержащих по k элементов. При этом каждое множество Y_j  имеет точно один элемент из каждого множества w_i, i = $\overline {0,k - 1} $, и если j ≠ s, то Y_j и Y_s имеют не более одного общего элемента. Таким образом, комбинаторная блок-схема TD(k, n) определена на множестве мощности kn. Если n – простое число или степень простого числа, то TD(k, n) существует. Тогда в алгебраической интерпретации она определяется на множестве пар (x₁, y), x₁ ∈ X₁, где X₁ есть множество из k элементов поля F_n, y ∈ F_n; блоки линейной трансверсальной блок-схемы TD(k, n) определяются парой элементов (a, b) ∈ F(n²) [8]:

В числовой интерпретации [15] линейная трансверсальная блок-схема TD(k, n) над полем F_n задается на числовом множестве

где x – примитивный элемент поля. Ее блоками являются множества

Пусть номера блоков B_{a, b} представляются числами N⁽²⁾(B_{a, b}) = $\varphi $(a, b). Вычислим множество ${{G}_{{TD(k,n)}}}(t)$ номеров блоков B_{a, b}, содержащих элемент t ∈ X, т.е. дуальный блок с номером t. Заметим, что ${{\varphi }^{{ - 1}}}(t) = ({{x}^{{(t - \left\lfloor {t/n} \right\rfloor n)}}},{{x}^{{\left\lfloor {t/n} \right\rfloor }}}).$ Таким образом, получено следующее утверждение.

Утверждение 4 [8, 15]. Справедливы представления

Трансверсальная блок-схема TD(t, k, n) – это тройка (X, H, A), где X – конечное множество мощности kn, H – разбиение X на k частей, называемых группами, размера n, A – множество k-подмножеств множества X, называемых блоками, которая удовлетворяет следующим условиям:

(1) |H ∩ A| = 1 для каждого H ∈ H и каждого A ∈ A,

(2) каждое t-подмножество множества X из t различных групп оказывается точно в одном блоке из A.

Если n – простое число или его степень, то TD(t, k, n) существует. В алгебраической интерпретации в этом случае блоки квадратичной трансверсальной блок-схемы TD(3, k, n) определяются тройками элементов (a, b, c) ∈ F(n³):

где X₁ есть множество из k элементов поля F_n [8].

В числовой интерпретации [15] квадратичная трансверсальная блок-схема TD(t, k, n) над полем F_n также задается на числовом множестве

где x есть примитивный элемент поля.

Пусть номерами блоков B_{a, b, с}  являются числа N⁽³⁾(B_{a, b, c}) = φ(a, b, c). Множество ${{G}_{{\operatorname{TD} (3,k,n)}}}(t)$ номеров блоков B_{a, b, c}, содержащих элемент t ∈ X, также можно определить, учитывая, что ${{\varphi }^{{ - 1}}}(t) = ({{x}^{{{{r}_{0}}}}},{{x}^{{{{r}_{1}}}}},{{x}^{{{{q}_{1}}}}})$, где

Таким образом, получено следующее утверждение.

Утверждение 5 [8, 15]. Справедливы представления

Полученные аналитические представления блоков комбинаторных блок-схем и их двойственных аналогов легко трансформируются в алгоритмы. Они были протестированы с использованием системы компьютерной алгебры Sage [13], ассоциированной с алгебраическим процессором МЭИ [14].

Пример 3. Схема ячеистой связи по квадратичной трансверсальной блок-схеме TD(3,3,3) и двойственной такой блок-схеме. Здесь d = 3, k = 3, n = 3.

По умолчанию, элементами блок-схемы TD(3,3,3) являются числа $\overline {0,8} $, их количество есть kn = 9. В этой блок-схеме n³ = 27 блоков по три элемента:

0. [0, 3, 6], 1. [0, 4, 7], 2. [0, 5, 8], 3. [0, 5, 7], 4. [0, 3, 8], 5. [0, 4, 6], 6. [0, 4, 8], 7. [0, 5, 6], 8. [0, 3, 7], 9. [1, 4, 7], 10. [1, 5, 8], 11. [1, 3, 6], 12. [1, 3, 8], 13. [1, 4, 6], 14. [1, 5, 7], 15. [1, 5, 6], 16. [1, 3, 7], 17. [1, 4, 8], 18. [2, 5, 8], 19. [2, 3, 6], 20. [2, 4, 7], 21. [2, 4, 6], 22. [2, 5, 7], 23. [2, 3, 8], 24. [2, 3, 7], 25. [2, 4, 8], 26. [2, 5, 6].

Имеется kn = 9 блоков двойственной трансверсальной блок-схемы DTD(3,3,3), т.е. множеств номеров блоков из TD(3,3,3), содержащих элемент, являющийся номером дуального блока:

0. [0, 1, 2, 3, 4, 5, 6, 7, 8],

1. [9, 10, 11, 12, 13, 14, 15, 16, 17 ] ,

2. [18, 19, 20, 21, 22, 23, 24, 25, 26 ] ,

3. [0, 4, 8, 11, 12, 16, 19, 23, 24],

4. [1, 5, 6, 9, 13, 17, 20, 21, 25 ] ,

5. [2, 3, 7, 10, 14, 15, 18, 22, 26 ] ,

6. [0, 5, 7, 11, 13, 15, 19, 21, 26],

7. [1, 3, 8, 9, 14, 16, 20, 22, 24 ] ,

8. [2, 4, 6, 10, 12, 17, 18, 23, 25 ] .

Сеть построена из 27 узлов, каждый из которых представляет собой полносвязную сеть из трех компьютеров. Каждый компьютер при этом входит в одну из девяти полносвязных подсетей, включающих по 9 компьютеров, он помечается номером этой подсети. Эти номера суть элементы TD(3, 3, 3), а блоки – тройки номеров, пометки компьютеров узла. Дуальные блоки включают номера блоков, содержащих номер данного дуального блока. Любые два компьютера из разных узлов могут принадлежать одной полносвязной сети из девяти компьютеров (если имеют одинаковые пометки), тогда компьютеры связаны непосредственно. Если же они оба не принадлежат ни одной такой сети (имеют разные пометки), то в узлах, в которые они входят, могут быть компьютеры с одинаковыми пометками или общих пометок нет. Тогда в первом случае необходимы три шага для соединения, а во втором – четыре шага. Таким образом, любые два компьютера либо связаны непосредственно, либо через двух или трех посредников. Эта система трехуровневая: уровни компьютеров (по умолчанию), узлов и полносвязных сетей. Подсистемы второго и третьего уровней соответствуют классам двух разбиений элементов первого уровня. Эта же комбинаторная схема имеет еще одну интерпретацию, представляющую собой формализацию схемы предварительного распределения ключей в беспроводной сенсорной сети. При этом элементы – это номера различных ключей. Блоки соответствуют узлам сети и являются множествами номеров ключей, встроенных в память узла. Дуальные блоки содержат номера узлов, которые имеют ключ, номер которого есть номер дуального блока. Узлы, в блоках которых имеется элемент с данным номером, могут коммутировать с использованием ключа с этим номером. Иначе найдется узел, в блоке которого имеется элемент, содержащийся в блоке первого узла, и другой элемент, содержащийся в блоке второго узла. Тогда возможна коммутация между двумя узлами с использованием этих двух ключей третьего узла, например с зашифрованием в первом узле, расшифрованием и зашифрованием в третьем узле и расшифрованием во втором узле.

Возможны подобные интерпретации любых трансверсальных комбинаторных блок-схем TD(3, k, n) и DTD(3, k, n). Так TD(3, 3, 4) и DTD(3, 3, 4) имеют 64 блока по три элемента и 12 дуальных блоков по 16 элементов.

Заключение. В статье обоснован метод синтеза систем, структура которых соответствует комбинаторной блок-схеме одной из рассматриваемых разновидностей при условии, что порядок блок-схемы является простым числом или степенью простого числа, отличающийся применением числовой и алгебраической формализации таких систем с использованием алгебраических идентификаторов блоков.

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

Этот метод на содержательном уровне предполагает определение разновидности комбинаторной блок-схемы, которой соответствует структура синтезируемой системы, подбор основных параметров комбинаторной блок-схемы и ее двойственного аналога. Далее в соответствии с правилом двойственности осуществляется нумерация элементов, блоков и дуальных блоков комбинаторной блок-схемы. При этом строятся и используются характерные для данного типа комбинаторной блок-схемы алгебраические идентификаторы блоков. Вычисляются все или отдельные блоки и дуальные блоки. При реализации системы или ее подсистемы осуществляется предметная интерпретация построенной комбинаторной блок-схемы или отдельных блоков и анализируются свойства синтезированной системы, обусловленные свойствами комбинаторной модели. Различные предметные системы допускают одну и ту же формализацию в виде комбинаторной блок-схемы, и наоборот, конкретная комбинаторная блок-схема может иметь различные предметные интерпретации. Естественно, что рассмотренные подходы позволяют строить аффинные плоскости как остаточные комбинаторные блок-схемы. Наконец, синтез трансверсальных комбинаторных систем по существу эквивалентен построению ортогональных латинских квадратов и ортогональных массивов. Алгебраические идентификаторы блоков могут использоваться также для решения некоторых производных задач, связанных с вычислением пересечений блоков или дуальных блоков или определением блока, имеющего пересечения с каждым из двух данных блоков для выявления характера связей в системе.