Блок-схема

Блок-схе́ма, система ${\displaystyle B}$ подмножеств конечного множества ${\displaystyle V}$, удовлетворяющая некоторым условиям, связанным с частотой появления пар элементов множества ${\displaystyle V}$ в системе ${\displaystyle B}$.

Формально блок-схема задаётся парой множеств ${\displaystyle (V,B)}$, где

${\displaystyle V=\{a_{1},\ \ldots ,a_{v}\},\ B=\{B_{1},\ \ldots ,B_{b}\},\ B_{1},\ \ldots ,B_{b}\subseteq V}$.

Элементы множества ${\displaystyle V}$ называются элементами блок-схемы, а элементы множества ${\displaystyle B}$ – её блоками. Параметрами блок-схемы называются числа ${\displaystyle v}$, ${\displaystyle b}$, ${\displaystyle r_{i}}$, ${\displaystyle k_{j}}$, ${\displaystyle \lambda _{ik}}$, ${\displaystyle i,k=1,\ \ldots ,v}$, ${\displaystyle j=1,\ \ldots ,b}$, где ${\displaystyle k_{j}}$ – число элементов множества ${\displaystyle V}$, содержащихся в ${\displaystyle B_{j},r_{i}}$ – число блоков, содержащих элемент ${\displaystyle a_{i}}$, а ${\displaystyle \lambda _{ik}}$ – число блоков, содержащих пару элементов ${\displaystyle (a_{i},a_{k})}$.

Наиболее изучены т. н. уравновешенные неполные блок-схемы, для которых

${\displaystyle r_{i}=r,\,\,k_{j}=r,\,\,\lambda _{ik}=\lambda ,\,\,i,k=1,\ \ldots ,\,\,v,\ j=1,\ \ldots ,b}$.

Параметры уравновешенной неполной блок-схемы связаны соотношениями

${\displaystyle vr=kb,\ \lambda (v-1)=r(k-1)}$.

Уравновешенная неполная блок-схема, для которой ${\displaystyle b=v}$, называется симметричной блок-схемой или ${\displaystyle (v,k,\lambda )}$-конфигурацией. Подклассами уравновешенных неполных блок-схем являются системы Штейнера (${\displaystyle \lambda =1}$), в частности системы троек Штейнера (${\displaystyle k=3}$), а также адамаровы конфигурации (${\displaystyle v=b=4t-1}$, ${\displaystyle r=k=2t-1}$, ${\displaystyle \lambda =t-1}$, ${\displaystyle t{\geqslant }2}$). Блок-схемы находят применение в планировании эксперимента, теории игр, теории графов и в теории кодирования.