Блок-схема

- система подмножеств конечного множества, удовлетворяющая нек-рым условиям, связанным с частотой появления пар элементов множества в подмножествах системы. Понятие Б.-с. возникло в теории планирования эксперимента в 20-30-х гг. 20 в., однако под названием тактических конфигураций Б.-с. изучались уже в сер. 19 в. Понятие Б.-с. является вариантом понятий гиперграфа, сети, комплекса. Обычно в Б.-с. на семейства подмножеств накладывается целый ряд дополнительных ограничений. Б.-с. можно задать парой множеств (F, В), где [img: http://localhost:8080/file/010214-115.jpg] Элементы множества Vназ. элементами Б.-с., а элементы множества В - ее блоками. Элемент [img: http://localhost:8080/file/010214-116.jpg] гг блок [img: http://localhost:8080/file/010214-117.jpg] инцидентны, если [img: http://localhost:8080/file/010214-118.jpg]. Число [img: http://localhost:8080/file/010214-119.jpg] элементов, инцидентных блоку [img: http://localhost:8080/file/010214-120.jpg], обозначается обычно через [img: http://localhost:8080/file/010214-121.jpg], а число блоков, инцидентных элементу [img: http://localhost:8080/file/010214-122.jpg], - через [img: http://localhost:8080/file/010214-123.jpg]. Через [img: http://localhost:8080/file/010214-124.jpg] обозначается число [img: http://localhost:8080/file/010214-125.jpg] Числа [img: http://localhost:8080/file/010214-126.jpg] наз. параметрами Б.-с. Если [img: http://localhost:8080/file/010214-127.jpg] для всех [img: http://localhost:8080/file/010214-128.jpg] [img: http://localhost:8080/file/010214-129.jpg] для всех [img: http://localhost:8080/file/010214-130.jpg] есть уравновешенная не полная Б.-с., или BIB-схема (от английского balanced incomplete block design) с параметрами [img: http://localhost:8080/file/010214-131.jpg] Слово "уравновешенный" характеризует одинаковую частоту появлений элементов и пар элементов в блоках, а слово "неполный" служит для указания того, что, вообще говоря, не все k-элементные подмножества входят в В. Пусть среди чисел [img: http://localhost:8080/file/010214-132.jpg] встречается ровно [img: http://localhost:8080/file/010214-133.jpg] различных: [img: http://localhost:8080/file/010214-134.jpg] и пусть на элементах множества [img: http://localhost:8080/file/010214-135.jpg] введено [img: http://localhost:8080/file/010214-136.jpg] симметричных отношений связанности так, что выполнены следующие условия: а) множество [img: http://localhost:8080/file/010214-137.jpg] всех пар элементов множества [img: http://localhost:8080/file/010214-138.jpg] разбивается на [img: http://localhost:8080/file/010214-139.jpg] непересекающихся подмножеств [img: http://localhost:8080/file/010214-140.jpg] [img: http://localhost:8080/file/010214-141.jpg] причем если [img: http://localhost:8080/file/010214-142.jpg] то говорят, что элементы [img: http://localhost:8080/file/010214-143.jpg] -связаны; [img: http://localhost:8080/file/010214-144.jpg] причем в силу симметричности Б.-с. со свойствами а) - г) наз. [img: http://localhost:8080/file/010214-145.jpg] частично уравновешенной Б.-с. с ттипами связей, или PBIB(m)-cхемой (от английского partially balanced incomplete block design). Правило, задающее отношение связанности, наз. схемой связанности. BIB-схема является PBIB (1)-схемой. Примером PBIB (2)-схемы является Б.-с., к-рую можно представить в виде таблицы [img: http://localhost:8080/file/010214-146.jpg] где любые два числа из одного столбца 1-связаны, а любые два числа, не принадлежащие одному столбцу, - 2-связаны. Здесь [img: http://localhost:8080/file/010214-147.jpg] n1=9, n2=2, [img: http://localhost:8080/file/010214-148.jpg] Всякой Б.-с. с [img: http://localhost:8080/file/010214-149.jpg] элементами и bблоками соответствует матрица инцидентности где [img: http://localhost:8080/file/010214-150.jpg], если [img: http://localhost:8080/file/010214-151.jpg] в противном [img: http://localhost:8080/file/010214-152.jpg] случае, [img: http://localhost:8080/file/010214-153.jpg] [img: http://localhost:8080/file/010214-154.jpg] В теории Б.-с. рассматриваются вопросы существования, классификации и вопросы, связанные с построением Б.-с. с заданными параметрами. Параметры Б.-с. связаны определенными соотношениями. Для BIB-схем справедливы равенства: [img: http://localhost:8080/file/010214-155.jpg] Для параметров PBIB (m)-схем справедливы равенство (1) и следующие соотношения: [img: http://localhost:8080/file/010214-156.jpg] Матрица инцидентности BIB-схемы удовлетворяет основному матричному соотношению [img: http://localhost:8080/file/010214-157.jpg] где Е - единичная матрица порядка v,a J - матрица порядка [img: http://localhost:8080/file/010214-158.jpg], составленная сплошь из единиц. Существование (0,1)-матрицы, удовлетворяющей условию (2), является достаточным условием существования BIB-схемы с заданными параметрами. Из (2) вытекает неравенство [img: http://localhost:8080/file/010214-159.jpg]. BIB-схема, для к-рой [img: http://localhost:8080/file/010214-160.jpg] (и значит r=k), наз. симметричной Б.-с., или [img: http://localhost:8080/file/010214-161.jpg] -конфигурацией. Для симметричных BIB-схем справедлива теорема: если существует симметричная BIB-схема с параметрами [img: http://localhost:8080/file/010214-162.jpg] то: а) при [img: http://localhost:8080/file/010214-163.jpg] четном [img: http://localhost:8080/file/010214-164.jpg] есть квадрат, б) при vнечетном уравнение [img: http://localhost:8080/file/010214-165.jpg] имеет решение в целых числах х, у, z, не равных одновременно нулю. Условия этой теоремы достаточны для существования рациональной матрицы А, удовлетворяющей (2). Специальный Круг вопросов, относящихся к существованию BIB-схем, возникает в связи с задачей: даны b блоков; каковы Условия того, чтобы эти блоки можно было дополнить др BIB-схемы? В наиболее общем виде эти условия выражаются как требования положительной определенности нек-рой квадратичной формы Q, а также возможности представить Qв виде суммы квадратов линейных форм с неотрицательными коэффициентами. Среди BIB-схем различают как наиболее изученные следующие подклассы: системы Штейнера (BIB-схемы с [img: http://localhost:8080/file/010214-166.jpg]), в частности системы троек Штейнера ([img: http://localhost:8080/file/010214-167.jpg]); адамаровы конфигурации ([img: http://localhost:8080/file/010214-168.jpg]), матрица инцидентности к-рых получается из Адамара матрицы;аффинные конечные геометрии и проективные копечные геометрии (см. [1]). В классе PBIB-схем наиболее изучены PBIB (2)-схемы, среди к-рых по виду схемы связанности выделяют так наз. Б.-с. с делимостью на группы, треугольные Б.-с., Б.-с. типа латинского к-в адрата, циклические Б.-с. и т. д. (см. [3]). Методы построения Б.-с. принято разделять на прямые и рекурсивные. Рекурсивные методы позволяют строить с помощью схем с меньшими значениями параметров схемы с большими значениями параметров. В прямых методах обычно используются свойства конечных полей "или какие-либо геометрические свойства. Помимо планирования экспериментов, Б.-с. применяются также в теории игр, теории графов и при построении кодов, исправляющих ошибки.