БЛОКСХЕМА

- система подмножеств конечного множества, удовлетворяющая нек-рым условиям, связанным с частотой появления пар элементов множества в подмножествах системы. Понятие Б.-с. возникло в теории планирования эксперимента в 20-30-х гг. 20 в., однако под названием тактических конфигураций Б.-с. изучались уже в сер. 19 в. Понятие Б.-с. является вариантом понятий гиперграфа, сети, комплекса. Обычно в Б.-с. на семейства подмножеств накладывается целый ряд дополнительных ограничений. Б.-с. можно задать парой множеств (F, В), где

БЛОКСХЕМА фото №1

Элементы множества Vназ. элементами Б.-с., а элементы множества В - ее блоками. Элемент БЛОКСХЕМА фото №2 гг блок БЛОКСХЕМА фото №3 инцидентны, если БЛОКСХЕМА фото №4 . Число БЛОКСХЕМА фото №5 элементов, инцидентных блоку БЛОКСХЕМА фото №6 , обозначается обычно через БЛОКСХЕМА фото №7 , а число блоков, инцидентных элементу БЛОКСХЕМА фото №8 , - через БЛОКСХЕМА фото №9 . Через БЛОКСХЕМА фото №10 обозначается число

БЛОКСХЕМА фото №11

Числа БЛОКСХЕМА фото №12 наз. параметрами Б.-с. Если БЛОКСХЕМА фото №13 для всех БЛОКСХЕМА фото №14 БЛОКСХЕМА фото №15 для всех БЛОКСХЕМА фото №16 есть уравновешенная не полная Б.-с., или BIB-схема (от английского balanced incomplete block design) с параметрами БЛОКСХЕМА фото №17 Слово "уравновешенный" характеризует одинаковую частоту появлений элементов и пар элементов в блоках, а слово "неполный" служит для указания того, что, вообще говоря, не все k-элементные подмножества входят в В.

Пусть среди чисел БЛОКСХЕМА фото №18 встречается ровно БЛОКСХЕМА фото №19 различных: БЛОКСХЕМА фото №20 и пусть на элементах множества БЛОКСХЕМА фото №21 введено БЛОКСХЕМА фото №22 симметричных отношений связанности так, что выполнены следующие условия:

а) множество БЛОКСХЕМА фото №23 всех пар элементов множества БЛОКСХЕМА фото №24 разбивается на БЛОКСХЕМА фото №25 непересекающихся подмножеств БЛОКСХЕМА фото №26 БЛОКСХЕМА фото №27 причем если БЛОКСХЕМА фото №28 то говорят, что элементы БЛОКСХЕМА фото №29 -связаны;

БЛОКСХЕМА фото №30

причем в силу симметричности Б.-с.со свойствами а) - г) наз. БЛОКСХЕМА фото №31 частично уравновешенной Б .-с. с ттипами связей, или PBIB(m)-cхемой (от английского partially balanced incomplete block design). Правило, задающее отношение связанности, наз. схемой связанности. BIB-схема является PBIB (1)-схемой. Примером PBIB (2)-схемы является Б.-с., к-рую можно представить в виде таблицы

БЛОКСХЕМА фото №32

где любые два числа из одного столбца 1-связаны, а любые два числа, не принадлежащие одному столбцу, - 2-связаны. Здесь БЛОКСХЕМА фото №33 n₁=9, n₂=2,

БЛОКСХЕМА фото №34

Всякой Б.-с. с БЛОКСХЕМА фото №35 элементами и bблоками соответствует матрица инцидентности где БЛОКСХЕМА фото №36 , если БЛОКСХЕМА фото №37 в противном БЛОКСХЕМА фото №38 случае, БЛОКСХЕМА фото №39 БЛОКСХЕМА фото №40 В теории Б.-с. рассматриваются вопросы существования, классификации и вопросы, связанные с построением Б.-с. с заданными параметрами. Параметры Б.-с. связаны определенными соотношениями. Для BIB-схем справедливы равенства:

БЛОКСХЕМА фото №41

Для параметров PBIB (m)-схем справедливы равенство (1) и следующие соотношения:

БЛОКСХЕМА фото №42

Матрица инцидентности BIB-схемы удовлетворяет основному матричному соотношению

БЛОКСХЕМА фото №43

где Е - единичная матрица порядка v,a J - матрица порядка БЛОКСХЕМА фото №44 , составленная сплошь из единиц. Существование (0,1)-матрицы, удовлетворяющей условию (2), является достаточным условием существования BIB-схемы с заданными параметрами. Из (2) вытекает неравенство БЛОКСХЕМА фото №45 . BIB-схема, для к-рой БЛОКСХЕМА фото №46 (и значит r=k), наз. симметричной Б.-с., или БЛОКСХЕМА фото №47 -конфигурацией. Для симметричных BIB-схем справедлива теорема: если существует симметричная BIB-схема с параметрами БЛОКСХЕМА фото №48 то: а) при БЛОКСХЕМА фото №49 четном БЛОКСХЕМА фото №50 есть квадрат, б) при vнечетном уравнение

БЛОКСХЕМА фото №51

имеет решение в целых числах х, у, z, не равных одновременно нулю. Условия этой теоремы достаточны для существования рациональной матрицы А, удовлетворяющей (2).

Специальный Круг вопросов, относящихся к существованию BIB-схем, возникает в связи с задачей: даны b блоков; каковы Условия того, чтобы эти блоки можно было дополнить др BIB-схемы? В наиболее общем виде эти условия выражаются как требования положительной определенности нек-рой квадратичной формы Q, а также возможности представить Qв виде суммы квадратов линейных форм с неотрицательными коэффициентами.

Среди BIB-схем различают как наиболее изученные следующие подклассы: системы Штейнера (BIB-схемы с БЛОКСХЕМА фото №52 ), в частности системы троек Штейнера ( БЛОКСХЕМА фото №53 ); адамаровы конфигурации ( БЛОКСХЕМА фото №54 ), матрица инцидентности к-рых получается из Адамара матрицы;аффинные конечные геометрии и проективные копечные геометрии (см. [1]). В классе PBIB-схем наиболее изучены PBIB (2)-схемы, среди к-рых по виду схемы связанности выделяют так наз. Б.-с. с делимостью на группы, треугольные Б.-с., Б.-с. типа латинского к-в адрата, циклические Б.-с. и т. д. (см. [3]).

Методы построения Б.-с. принято разделять на прямые и рекурсивные. Рекурсивные методы позволяют строить с помощью схем с меньшими значениями параметров схемы с большими значениями параметров. В прямых методах обычно используются свойства конечных полей "или какие-либо геометрические свойства.

Помимо планирования экспериментов, Б.-с. применяются также в теории игр, теории графов и при построении кодов, исправляющих ошибки.

Лит.:[1] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [2] Холл М., Комбинаторика, пер. с англ., М., 1970; 13] Широкова С. А., "Успехи матем. наук", 1968, т. 23, Л? 5, с. 51-98. В. Е. Тараканов.

Синонимы:

схема

Смотреть больше слов в «Математической энциклопедии»

БЛОКСХЕМА

Смотреть что такое БЛОКСХЕМА в других словарях:

Рекомендуем посмотреть: