Блок-схема

БЛОК-СХЕМА, система В подмножеств конечного множества V, удовлетворяющая некоторым условиям, связанным с частотой появления пар элементов множества V в системе В.

Формально блок-система задаётся парой множеств (V, В), где

Элементы множества V называются элементами блок-схемы, а элементы множества В - её блоками. Параметрами блок-схемы называются числа v, b, r_i, k_j, λ_ik, i, k = 1, ..., v, j = 1, ..., b, где k_j - число элементов множества V, содержащихся в B_j, r_i - число блоков, содержащих элемент a_i , a λ_ik- число блоков, содер­жащих пару элементов (a_i, а_к).

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

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

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

Лит.: Сачков В.Н. Введение в комбинаторные методы дискретной математики. 2-е изд. М., 2004.