Блок-схема

Система подмножеств конечного множества, удовлетворяющая нек-рым условиям, связанным с частотой появления пар элементов множества в подмножествах системы. Понятие Б.-с. возникло в теории планирования эксперимента в 20-30-х гг. 20 в., однако под названием тактических конфигураций Б.-с. изучались уже в сер. 19 в. Понятие Б.-с. является вариантом понятий гиперграфа, сети, комплекса. Обычно в Б.-с. на семейства подмножеств накладывается целый ряд дополнительных ограничений. Б.-с. можно задать парой множеств (F, В), где Элементы множества Vназ. элементами Б.-с., а элементы множества В — ее блоками. Элемент гг блок инцидентны, если . Число элементов, инцидентных блоку , обозначается обычно через , а число блоков, инцидентных элементу , — через . Через обозначается число Числа наз. параметрами Б.-с. Если для всех для всех есть уравновешенная не полная Б.-с., или BIB-схема (от английского balanced incomplete block design) с параметрами Слово "уравновешенный" характеризует одинаковую частоту появлений элементов и пар элементов в блоках, а слово "неполный" служит для указания того, что, вообще говоря, не все k-элементные подмножества входят в В. Пусть среди чисел встречается ровно различных: и пусть на элементах множества введено симметричных отношений связанности так, что выполнены следующие условия: а) множество всех пар элементов множества разбивается на непересекающихся подмножеств причем если то говорят, что элементы -связаны; причем в силу симметричности Б.-с. со свойствами а) — г) наз. частично уравновешенной Б .-с. с ттипами связей, или PBIB(m)-cхемой (от английского partially balanced incomplete block design). Правило, задающее отношение связанности, наз. схемой связанности. BIB-схема является PBIB (1)-схемой. Примером PBIB (2)-схемы является Б.-с., к-рую можно представить в виде таблицы где любые два числа из одного столбца 1-связаны, а любые два числа, не принадлежащие одному столбцу, — 2-связаны. Здесь n1=9, n2=2, Всякой Б.-с. с элементами и bблоками соответствует матрица инцидентности где , если в противном случае, В теории Б.-с. рассматриваются вопросы существования, классификации и вопросы, связанные с построением Б.-с. с заданными параметрами. Параметры Б.-с. связаны определенными соотношениями. Для BIB-схем справедливы равенства: Для параметров PBIB (m)-схем справедливы равенство (1) и следующие соотношения: Матрица инцидентности BIB-схемы удовлетворяет основному матричному соотношению где Е — единичная матрица порядка v,a J — матрица порядка , составленная сплошь из единиц. Существование (0,1)-матрицы, удовлетворяющей условию (2), является достаточным условием существования BIB-схемы с заданными параметрами. Из (2) вытекает неравенство . BIB-схема, для к-рой (и значит r=k), наз. симметричной Б.-с., или -конфигурацией. Для симметричных BIB-схем справедлива теорема: если существует симметричная BIB-схема с параметрами то: а) при четном есть квадрат, б) при vнечетном уравнение имеет решение в целых числах х, у, z, не равных одновременно нулю. Условия этой теоремы достаточны для существования рациональной матрицы А, удовлетворяющей (2). Специальный Круг вопросов, относящихся к существованию BIB-схем, возникает в связи с задачей: даны b блоков; каковы Условия того, чтобы эти блоки можно было дополнить др BIB-схемы? В наиболее общем виде эти условия выражаются как требования положительной определенности нек-рой квадратичной формы Q, а также возможности представить Qв виде суммы квадратов линейных форм с неотрицательными коэффициентами. Среди BIB-схем различают как наиболее изученные следующие подклассы: системы Штейнера (BIB-схемы с ), в частности системы троек Штейнера (); адамаровы конфигурации ( ), матрица инцидентности к-рых получается из Адамара матрицы;аффинные конечные геометрии и проективные копечные геометрии (см. [1]). В классе PBIB-схем наиболее изучены PBIB (2)-схемы, среди к-рых по виду схемы связанности выделяют так наз. Б.-с. с делимостью на группы, треугольные Б.-с., Б.-с. типа латинского к-в адрата, циклические Б.-с. и т. д. (см. [3]). Методы построения Б.-с. принято разделять на прямые и рекурсивные. Рекурсивные методы позволяют строить с помощью схем с меньшими значениями параметров схемы с большими значениями параметров. В прямых методах обычно используются свойства конечных полей "или какие-либо геометрические свойства. Помимо планирования экспериментов, Б.-с. применяются также в теории игр, теории графов и при построении кодов, исправляющих ошибки. Лит.:[1] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [2] Холл М., Комбинаторика, пер. с англ., М., 1970; 13] Широкова С. А., "Успехи матем. наук", 1968, т. 23, Л? 5, с. 51-98. В. Е. Тараканов.