Математическая энциклопедия - блок-схема

система подмножеств конечного множества, удовлетворяющая нек-рым условиям, связанным с частотой появления пар элементов множества в подмножествах системы. Понятие Б.-с. возникло в теории планирования эксперимента в 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-схемы удовлетворяет основному матричному соотношению