Блок-схема — это множество вместе с семейством подмножеств (повторение подмножеств разрешено в некоторых случаях), члены которого удовлетворяют некоторым свойствам, которые считаются полезными для конкретного приложения. Эти приложения приходят из разных областей, включая планирование эксперимента, конечную геометрию, тестирование программного обеспечения, криптографию и алгебраическую геометрию. Рассматривалось много вариантов, но наиболее интенсивно изучались сбалансированные неполные блок-схемы (Balanced Incomplete Block Designs, BIBD, 2-схемы), которые исторически были связаны со статистическими задачами при планировании эксперимента.
Блок-схема, в которой все блоки имеют один размер, называется однородной. Схемы, обсуждаемые в этой статье, все однородны. Попарно сбалансированные схемы (Pairwise balanced designs, PBD) являются примерами блок-схем, которые не обязательно однородны.
Определение BIBD (или 2-схемы)
Если задано конечное множество X (элементов, которые называются точками) и целые числа k, r, λ ≥ 1, мы определяем 2-схему B как семейство k-элементных подмножеств множества X, называемых блоками, таких, что любой элемент x из X содержится в r блоках, и любая пара различных точек x и y в X содержится в λ блоках.
Слово «семейство» в определении выше может быть заменено словом «множество», если повторение блоков не разрешено. Схемы, в которых повторение блоков не позволяется, называются простыми.
Здесь v (число элементов X, называемых точками), b (число блоков), k, r и λ являются параметрами схемы. (Чтобы избежать вырожденных примеров, предполагается, что v > k, так что никакой блок не содержит все элементы множества. Поэтому в названии схем присутствует слово «неполные».) В таблице: {|class="wikitable" |v ||точки, число элементов X |- |b ||число блоков |- |r ||число блоков, содержащих данную точку |- |k ||число точек в блоке |- |λ ||число блоков, содержащих любые 2 (или, более обще, t) точек
Схема называется (v, k, λ)-схемой или (v, b, r, k, λ)-схемой. Параметры не являются независимыми — v, k и λ определяют b и r, и не все комбинации v, k и λ допустимы. Два основных равенства, содержащих эти параметры
получается путём подсчёта пар (B, p), где B — блок, а p — точка в этом блоке
получается путём подсчёта троек (p, q, B), где p и q — различные точки, и B — блок, содержащий обе точки, и делением числа троек на v.
Эти условия не достаточны, так как, например, (43,7,1)-схемы не существует Доказательство дал Тарри в 1900, который показал, что не существует пары ортогональных латинских квадратов порядка 6. 2-Схема с указанными параметрами эквивалентна существованию пяти взаимно ортогональных латинских квадратов порядка шесть.
Порядок 2-схемы определяется как n = r − λ. Дополнение 2-схемы получается путём замены каждого блока его дополнением в множестве точек X. Дополнение является также 2-схемой и имеет параметры v′ = v, b′ = b, r′ = b − r, k′ = v − k, λ′ = λ + b − 2r. 2-Схема и её дополнение имеют один порядок.
Фундамендальная теорема, неравенство Фишера, названное именем статистика Рональда Фишера, утверждает, что b ≥ v в любой 2-схеме.
В терминах теории графов определение 2-схемы можно переформулировать так: блок-схема — это покрытие с кратностью полного графа на вершинах полными графами на вершинах. Блок-схемы при и тривиальны, поэтому обычно предполагается, что .
Примеры Единственная (6,3,2)-схема имеет 10 блоков (b = 10) и каждый элемент повторяется 5 раз (r = 5). Если использовать символы 0 − 5, блоки содержат следующие тройки: 012 013 024 035 045 125 134 145 234 235.
Одна из четырёх неизоморфных (8,4,3)-схем имеет 14 блоков, в которых элементы повторяются 7 раз. Если использовать символы 0 – 7, блоками являются следующие четвёрки: 0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.
Единственная (7,3,1)-схема имеет 7 блоков, в которых каждый элемент повторён 3 раза. Если использовать символы 0 − 6, блоками служат следующие тройки: 013 026 045 124 156 235 346. Если элементы понимаются как точки на плоскости Фано, то эти блоки являются прямыми.
Симметричные BIBD
Случай равенства в неравенстве Фишера, то есть 2-схема с одинаковым числом точек в блоках, называется симметричной схемойЭти схемы называются также проективными схемами или квадратными схемами. Эти альтернативные названия использовались в попытке заменить термин «симметричная», поскольку ничего нет симметричного (в обычном смысле термина) в этих схемах. Термин проективные использовал П. Дембовски , по аналогии с наиболее общим примером, проективными плоскостями. Термин квадратные использовал П. Камерон , что отражает равенство v = b для матрицы инцидентности. Ни один из терминов не был подхвачен в качестве замены и схемы по-прежнему называются симметричными.. Симметричные схемы имеют наименьшее число блоков среди всех 2-схем с тем же числом точек.
В симметричной схеме выполняется r = k, как и b = v, и, хотя это неверно для произвольных 2-схем, в симметричных схемах любые два различных блока имеют общими λ точек. Теорема даёт обратный вывод — если X является множеством из v элементов, а B является набором из v k-элементных подмножеств («блоков»), таких, что любые два различных блока имеют в точности λ общих точек, то (X, B) является симметричной блок-схемой.
Параметры симметричной схемы удовлетворяют равенству
Равенство накладывает сильное ограничение на v, так что число точек далеко от произвольного. Теорема Брука — Райзера — Човла даёт необходимое, но не достаточное условие существования симметричных схем в терминах их параметров.
Ниже приведены важные примеры симметричных 2-схем:
Проективные плоскости
Конечные проективные плоскости являются симметричными 2-схемами с λ = 1 и порядком n > 1. Для этих схем равенство симметричной схемы превращается в:
Поскольку k = r, мы можем записать порядок проективной плоскости как n = k − 1 и, из приведённого выше равенства, мы получаем v = (n + 1)n + 1 = n2 + n + 1 точек в проективной плоскости порядка n.
Так как проективная плоскость является симметричной схемой, мы имеем b = v, что означает, что b = n2 + n + 1 также. Число b является числом прямых проективной плоскости. Не может быть повторяющихся прямых, поскольку λ = 1, так что проективная плоскость является простой 2-схемой, в которой число прямых и число точек всегда равны. Для проективной плоскости k является числом точек на прямой и оно равно n + 1. Аналогично, r = n + 1 является числом прямых, с которыми данная точка инцидента.
Для n = 2 мы имеем проективную плоскость порядка 2, которая называется также плоскостью Фано, с v = 4 + 2 + 1 = 7 точками и 7 прямыми. На плоскости Фано любая прямая имеет в точности n + 1 = 3 точек и каждая точка принадлежит n + 1 = 3 прямым.
Известно, что проективные плоскости существуют для всех порядков, равных простым числам и их степеням. Они образуют единственное известное бесконечное семейство симметричных блочных схем.
Бипланарная геометрия Бипланарная геометрия — это симметричная 2-схема с λ = 2. То есть любое множество из двух точек содержится в двух блоках («прямых»), а любые две прямые пересекаются в двух точках. Бипланарные геометрии аналогичны проективным плоскостям, за исключением того, что две точки не определяют прямую (а две прямые не определяют точку). В бипланарной геометрии две точки определяют две прямых (соответственно, две прямые определяют две точки). Бипланарная геометрия порядка n — это схема, блоки которой имеют k = n + 2 точек, Всего же точек v = 1 + (n + 2)(n + 1)/2 (поскольку r = k).
18 известных примеров перечислены ниже. (Тривиальная схема) Бипланарная геометрия порядка 0 имеет 2 точки (и прямые размера 2; 2-(2,2,2) схема); это две точки и два блока, которые содержат обе точки. Геометрически это двуугольник. Бипланарная геометрия порядка 1 имеет 4 точки (и прямые размера 3; 2-(4,3,2) схема); это полная схема с v = 4 и k = 3. Геометрически точки являются вершинами, а блоки являются гранями тетраэдра. Бипланарная геометрия порядка 2 является дополнением плоскости Фано — она содержит 7 точек (и прямые размера 4; 2-(7,4,2)) схема, где прямые задаются как дополнения (3-точечных) прямых плоскости Фано. Бипланарная геометрия порядка 3 имеет 11 точек (и прямые размера 5; 2-(11,5,2)) схема, которая известна как бипланарная геометрия Пэли по имени ; Схема связана с графом Пэли порядка 11, который строится с помощью поля с 11 элементами, и является 2-схемой Адамара, связанной с матрицей Адамара размера 12, см. статью «Построение Пэли I». Алгебраически это соответствует особому вложению проективной специальной линейной группы PSL(2,5) в PSL(2,11) – для детального описания см. проективная линейная группа: действие на p точек. Имеется три бипланарных геометрии порядка 4 (16 точек, прямые размера 6; 2-(16,6,2)) схемы. Эти три схемы являются также схемами Менона. Имеется четыре бипланарных геометрии порядка 7 (37 точек, прямые размера 9; 2-(37,9,2) схемы) Имеется пять бипланарных геометрий порядка 9 (56 точек, прямые размера 11; 2-(56,11,2) схемы) Известны две бипланарные геометрии порядка 11 (79 точек, прямые размера 13; 2-(79,13,2) схемы).
2-схемы Адамара Матрица Адамара размера m — это m × m матрица H, элементы которой равны ±1, такая, что HH⊤ = mEm, где H⊤ равна транспонированной матрице H, а Em — m × m единичная матрица. Матрицу Адамара можно представить в стандартной форме (то есть привести к эквивалентной матрице Адамара), в которой первая строка и первый столбец состоят из +1. Если размер m > 2, m должен делиться на 4.
Если дана матрица Адамара размера 4a в стандратной форме, удалим первую строку и первый столбец и заменим все элементы −1 на 0. В результате получим матрицу M, состоящую из 0 и 1, которая является матрицей инцидентности симметричной 2-(4a − 1, 2a − 1, a − 1) схемы. Эта схема называется 2-схемой Адамара. Схема содержит блоков, каждый из которых содержит точек, и точек, которые содержатся в блоках. Каждая пара точек содержится точно в блоках.
Построение обратимо, и матрица инцидентности симметричной 2-схемы с этими параметрами может быть использовано для формирования матрицы Адамара размера 4a.
Разрешимые 2-схемы Разрешимая 2-схема — это BIBD, блоки которого могут быть разбиты на множества (называемые параллельными классами), каждое из которых образует раздел разбиения точек из BIBD. Множество параллельных классов называется разрешением схемы.
Если 2-(v,k,λ) разрешимая схема имеет c параллельных классов, то b ≥ v + c − 1.
Следовательно, симметричная схема не может иметь нетривиальное (более одного параллельного класса) разрешение.
Архетипичные разрешимые 2-схемы — это конечные проективные плоскости. Решение знаменитой задачи Киркмана о школьницах является разрешением 2-(15,3,1) схемы.
Обобщения: t-схемы
Если дано любое положительное число t, t-схема B — это класс k-элементных подмножеств множества X, называемых блоками, таких, что любая точка x из X появляется точно в r блоках, а любое t-элементное подмножество T содержится ровно в λ блоках. Числа v (число элементов в X), b (число блоков), k, r, λ и t служат параметрами схемы. Схему можно назвать t-(v,k,λ)-схемой. Снова эти четыре числа определяют b и r, а сами четыре числа нельзя выбрать произвольно. Связывающие их равенства
,
где λi — число блоков, которые содержат любое i-элементное множество точек.
Заметим, что .
Теорема: Любая t-(v,k,λ)-схема является также s-(v,k,λs)-схемой для любого числа s при условии 1 ≤ s ≤ t. (Заметим, что «значение лямбда» меняется, как выше указано, и зависит от s.)
Следствие этой теоремы — любая t-схема с t ≥ 2 является также 2-схемой.
Схема t-(v,k,1) называется системой Штейнера.
Сам по себе термин блок-схема обычно подразумевает 2-схему.
Производные и расширяемые t-схемы