Главная
Блок-схема — это множество вместе с семейством подмножеств (повторение подмножеств разрешено в некоторых случаях), члены которого удовлетворяют некоторым свойствам, которые считаются полезными для конкретного приложения. Эти приложения приходят из разных областей, включая планирование эксперимента, конечную геометрию, тестирование программного обеспечения, криптографию и алгебраическую геометрию. Рассматривалось много вариантов, но наиболее интенсивно изучались сбалансированные неполные блок-схемы (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, так что никакой блок не содержит все элементы множества. Поэтому в названии схем присутствует слово «неполные».) В таблице:
Схема называется (v, k, λ)-схемой или (v, b, r, k, λ)-схемой. Параметры не являются независимыми — v, k и λ определяют b и r, и не все комбинации v, k и λ допустимы. Два основных равенства, содержащих эти параметры
b k = v r , {displaystyle bk=vr,}получается путём подсчёта пар (B, p), где B — блок, а p — точка в этом блоке
λ ( v − 1 ) = r ( k − 1 ) , {displaystyle lambda (v-1)=r(k-1),}получается путём подсчёта троек (p, q, B), где p и q — различные точки, и B — блок, содержащий обе точки, и делением числа троек на v.
Эти условия не достаточны, так как, например, (43,7,1)-схемы не существует
Порядок 2-схемы определяется как n = r − λ. Дополнение 2-схемы получается путём замены каждого блока его дополнением в множестве точек X. Дополнение является также 2-схемой и имеет параметры v′ = v, b′ = b, r′ = b − r, k′ = v − k, λ′ = λ + b − 2r. 2-Схема и её дополнение имеют один порядок.
Фундамендальная теорема, неравенство Фишера, названное именем статистика Рональда Фишера, утверждает, что b ≥ v в любой 2-схеме.
В терминах теории графов определение 2-схемы можно переформулировать так: блок-схема — это покрытие с кратностью λ {displaystyle lambda } полного графа на v {displaystyle v} вершинах полными графами на k {displaystyle k} вершинах. Блок-схемы при k = 0 , 1 {displaystyle k=0,1} и v {displaystyle v} тривиальны, поэтому обычно предполагается, что 2 ≤ k ≤ n − 1 {displaystyle 2leq kleq n-1} .
Примеры
Единственная (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-схема с одинаковым числом точек в блоках, называется симметричной схемой. Симметричные схемы имеют наименьшее число блоков среди всех 2-схем с тем же числом точек.
В симметричной схеме выполняется r = k, как и b = v, и, хотя это неверно для произвольных 2-схем, в симметричных схемах любые два различных блока имеют общими λ точек. Теорема Райзера даёт обратный вывод — если X является множеством из v элементов, а B является набором из v k-элементных подмножеств («блоков»), таких, что любые два различных блока имеют в точности λ общих точек, то (X, B) является симметричной блок-схемой.
Параметры симметричной схемы удовлетворяют равенству
λ ( v − 1 ) = k ( k − 1 ) . {displaystyle lambda (v-1)=k(k-1).}Равенство накладывает сильное ограничение на v, так что число точек далеко от произвольного. Теорема Брука — Райзера — Човла даёт необходимое, но не достаточное условие существования симметричных схем в терминах их параметров.
Ниже приведены важные примеры симметричных 2-схем:
Проективные плоскости
Конечные проективные плоскости являются симметричными 2-схемами с λ = 1 и порядком n > 1. Для этих схем равенство симметричной схемы превращается в:
v − 1 = k ( k − 1 ) . {displaystyle v-1=k(k-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 мы имеем проективную плоскость порядка, которая называется также плоскостью Фано, с 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».
- Имеется три бипланарных геометрии порядка 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-схемой Адамара. Схема содержит 4 a − 1 {displaystyle 4a-1} блоков, каждый из которых содержит 2 a − 1 {displaystyle 2a-1} точек, и 4 a − 1 {displaystyle 4a-1} точек, которые содержатся в 2 a − 1 {displaystyle 2a-1} блоках. Каждая пара точек содержится точно в a − 1 {displaystyle a-1} блоках.
Построение обратимо, и матрица инцидентности симметричной 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 = λ ( v − i t − i ) / ( k − i t − i ) for i = 0 , 1 , … , t , {displaystyle lambda _{i}=lambda left.{inom {v-i}{t-i}} ight/{inom {k-i}{t-i}}{ ext{ for }}i=0,1,ldots ,t,} ,где λi — число блоков, которые содержат любое i-элементное множество точек.
Заметим, что b = λ 0 = λ ( v t ) / ( k t ) {displaystyle b=lambda _{0}=lambda {v choose t}/{k choose t}} .
Теорема: Любая t-(v,k,λ)-схема является также s-(v,k,λs)-схемой для любого числа s при условии 1 ≤ s ≤ t. (Заметим, что «значение лямбда» меняется, как выше указано, и зависит от s.)
Следствие этой теоремы — любая t-схема с t ≥ 2 является также 2-схемой.
Схема t-(v,k,1) называется системой Штейнера.
Сам по себе термин блок-схема обычно подразумевает 2-схему.
Производные и расширяемые t-схемы
Пусть D = (X, B) является t-(v,k,λ) схемой и пусть p — точка множества X. Производная схема Dp имеет множество точек X − {p}, а в качестве множества блоков все блоки D, которые содержат p и в которых точка p удалена. Эта схема является (t − 1)-(v − 1, k − 1, λ) схемой. Заметим, что порождённые схемы для различных точек могут не быть изоморфными. Схема E называется расширением схемы D, если E имеет точку p, такую, что Ep изоморфна D. Мы называем D расширяемым, если схема имеет расширение.
Теорема: Если t-(v,k,λ) схема имеет расширение, то k + 1 делит b(v + 1).
Расширяемые проективные плоскости (симметричные 2-(n2 + n + 1, n + 1, 1) схемы) — это только те, порядки которых равны 2 и 4.
Любая 2-схема Адамара расширяема (до 3-схемы Адамара).
Теорема: Если D, симметричная 2-(v,k,λ) схема, расширяема, выполняется одно из:
Заметим, что проективная плоскость порядка два является 2-схемой Адамара. Проективная плоскость порядка четыре имеет параметры, которые подпадают под случай 2. Другие известные симметричные 2-схемы с параметрами из случая 2 — бипланарные геометрии порядка 9, но ни одна из них не расширяема. Симметричные 2-схемы с параметрами случая 3 неизвестны.
Круговая плоскость
Схема с параметрами расширения аффинной плоскости, то есть 3-(n2 + 1, n + 1, 1) схема, называется конечной круговой плоскостью или плоскостью Мёбиуса порядка n.
Можно дать геометрическое описание некоторых круговых плоскостей, более того, всех известных круговых плоскостей. Овоид в PG(3,q) является множеством из q2 + 1 точек, никакие три из которых не коллинеарны. Можно показать, что любая плоскость (которая является гиперплоскостью в размерности 3) в PG(3,q) пересекает овоид O либо в одной, либо в q + 1 точках. Пересечения овоида O размера q + 1 плоскостью — это блоки круговой плоскости порядка q. Любая круговая плоскость, получающаяся таким образом, называется яйцевидной. Все известные круговые плоскости яйцевидны.
Примером овоида служит эллиптитическая квадрика, множество нулей квадратичной формы
x1x2 + f(x3, x4),где f — неприводимая квадратичная форма от двух переменных над GF(q). [f(x,y)=x2 + xy + y2, например].
Если q равно нечётной степени 2, известен другой тип овоида — овоид Сузуки – Титса.
Теорема. Пусть q — положительное целое число, не меньшее 2. (a) Если q нечётно, любой овоид проективно эквивалентен эллиптической квадрике в проективной геометрии PG(3,q), так что q является степенью простого числа и существует единственная яйцеподобная круговая плоскость порядка q (неизвестно при этом, существуют ли не яйцеподобные плоскости.) (b) если q чётно, то q является степенью 2 и любая круговая плоскость порядка q яйцеподобна (возможно, существуют некоторые неизвестные овоиды).
Частично сбалансированные схемы (PBIBD)
n-Класс схемы отношения состоит из множества X размера v вместе с разбиением S множества X × X на n + 1 бинарных отношений R0, R1, ..., Rn. Говорят, что пара элементов находятся в отношении Ri (элементы i-сочетаются). Каждый элемент из X имеет ni i-ых сочетаний. Кроме того:
- R 0 = { ( x , x ) : x ∈ X } {displaystyle R_{0}={(x,x):xin X}} и называется отношением тождества.
- Если определить R ∗ := { ( x , y ) | ( y , x ) ∈ R } {displaystyle R^{*}:={(x,y)|(y,x)in R}} , то из принадлежности R разбиению S, следует принадлежность R* разбиению S
- Если ( x , y ) ∈ R k {displaystyle (x,y)in R_{k}} , число элементов z ∈ X {displaystyle zin X} , таких что ( x , z ) ∈ R i {displaystyle (x,z)in R_{i}} и ( z , y ) ∈ R j {displaystyle (z,y)in R_{j}} , постоянно (равно p i j k {displaystyle p_{ij}^{k}} ) и это число зависит от i, j, k, но не от выбора x и y.
Схема сочетаний коммутативна, если p i j k = p j i k {displaystyle p_{ij}^{k}=p_{ji}^{k}} для всех i, j и k. Большинство авторов предполагают это свойство.
Частично сбалансированная неполная блочная схема с n классами сочетаний (PBIBD(n)) — это блок-схема, основанная на множестве X с v элементами, имеющая b блоков по k элементов в каждом, в которой каждый элемент появляется в r блоках и для которой существует схема сочетаний с n классами, определёнными на X, при этом, если элементы x и y i-сочетаются для 1 ≤ i ≤ n, то они содержатся вместе точно в λi блоках.
PBIBD(n) определяет схему сочетаний, но обратное неверно.
Пример
Пусть A(3) — схем сочетаний с тремя классами на множестве X = {1,2,3,4,5,6}. Значение элемента таблицы (i,j) равно s, если элементы i и j находятся в отношении Rs.
Блоки PBIBD(3), основанные на A(3):
Параметры этой PBIBD(3): v = 6, b = 8, k = 3, r = 4 и λ1 = λ2 = 2 и λ3 = 1. Также, для схемы соотношений имеем n0 = n2 = 1 и n1 = n3 = 2.
Свойства
Параметры PBIBD(m) удовлетворяют равенствам:
PBIBD(1) — это BIBD, PBIBD(2), в которой λ1 = λ2, также является BIBD.
PBIBD с двумя классами сочетаний
Схемы PBIBD(2) изучались больше всего ввиду их простоты и полезности . Они распадаются на шесть типов , если базироваться на проведённой Бозе и Шимамото классификации известных тогда схем PBIBD(2):
Приложения
Математический субъект блок-схем возник как статистическая основа планирования эксперимента. Схемы были особенно полезны в приложениях техники дисперсионного анализа (ANOVA). Эта область остаётся существенной частью использования блочных схем.
Хотя источником были биологические приложения, схемы используются во многих других областях, где осуществляются систематические сравнения, таких как тестирование программного обеспечения.
Матрица инцидентности блок-схемы даёт естественный источник интересных блочных кодов, которые используются как коды, исправляющие ошибки. Строки матрицы инцидентности используются также как символы в фазово-импульсной модуляции.
Статистические приложения
Предположим, что исследователи рака кожи хотят проверить три различных солнцезащитных крема. Они наносят два различных крема на верхние стороны рук испытуемых. После облучения ультрафиолетом они записывают степень раздражения кожи в терминах солнечного ожога. Число способов лечения — 3 (число кремов), размер блока равен 2 (число рук у человека).
Соответствующая схема BIBD может быть получена как R-функция design.bib пакета R-package agricolae и определяется следующей таблицей:
Исследователь выбирает параметры v = 3, k = 2 и λ = 1 для блок-схемы, которые подставляются в R-функцию. Оставшиеся параметры b и r определяются автоматически.
Используя базовые отношения, мы вычисляем, что нам нужно b = 3 блоков, то есть 3 испытуемых, чтобы получить сбалансированную неполную блок-схему. Обозначив блоки A, B и C, чтобы не путаться, мы получаем блок-схему,
A = {2, 3}, B = {1, 3} и C = {1, 2}.Соответствующая матрица инцидентности приведена в таблице:
Каждое лечение содержится в 2 блоках, так что r=2.
Только один блок (C) содержит лечения 1 и 2 одновременно, и то же самое верно для пар лечений (1,3) и (2,3). Поэтому λ=1.
Невозможно использовать полную схему (все лечения в каждом блоке) в этом примере, поскольку имеется 3 крема и только по 2 руки у каждого испытуемого.