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

6 / 13

Г.П. Можаров
46 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
либо  6 3 n t (если    2 1 3(2 1).r t Следовательно, для троек Штейнера
имеем [1]
 2 6 , b t t  6 1, n t  3 , r t  3, k   1, (8)
либо
  2 6 5 1, b t t  6 3, n t  3 1, r t  3, k   1. (9)
Верно и обратное: для любого числа n вида  6 1t или  6 3t существует си-
стема троек Штейнера с n элементами и параметрами (8) или (9). Из системы
троек Штейнера S с n элементами можно построить мультипликативную си-
стему M для n элементов системы S, полагая  2 x x для каждого x и  xy z
(при условиях, что  x y и x, y, z — единственная тройка из S, содержащая па-
ру x, y). Эта система может быть описана следующим образом:
a)  2 x x — для каждого  ; x M
б) если  , x y то  xy z  единственный элемент в M и  , z x  , z y а так-
же  , yx z   , xz zx y   . yz zy x
Можно проверить, что если дана система M с умножением, удовлетворя-
ющим (1) и (2), то тройки x, y, z, определенные соотношениями  , x y  , xy z
образуют систему троек Штейнера с числом элементов, равным числу элементов
в . M
Если 1 M — мультипликативная система для системы троек Штейнера 1 S
с 1 n элементами, а 2 M — мультипликативная система для 2 S с 2 n элементами,
то можно построить систему  1 2 , M M M в которой элементами являются
1 2 n n упорядоченных пар  
1 2, , x x 
1 1, x M 
2 2 . x M Если определить операцию
умножения в M по правилу
     

1 2 1 2 1 1 2 2 , , , , x x y y x y x y
то отсюда немедленно следует, что умножение в  1 2 M M M имеет свойства (1)
и (2), и, следовательно, из M можно образовать систему троек Штейнера с
 1 2 n n n элементами. Таким образом, если существует система троек Штейнера
2 S с 2 n элементами и другая система троек Штейнера 2 S с 2 n элементами, то
существует система троек Штейнера  1 2 S S S с 1 2 n n элементами. Отметим, что
в системах (8), (9) подсистемы с фиксированным 1 x или 2 x соответствуют под-
системам системы , S изоморфным 2 S и 1 S соответственно.
Топология сети блок-дизайнов. 1. Если задан BIB-дизайн, то его граф
строится следующим образом:  n b вершин графа соответствуют элементам и
блокам BIB-дизайна, при этом две вершины смежныe тогда и только тогда, ко-
гда одна из них соответствует блоку, а другая  элементу, содержащемуся в этом
блоке [1, 2, 11]. Ясно, что граф является двудольным, причем каждая его верши-
на имеет степень r или k в зависимости от того, соответствует ли она элементу
или блоку.