Блочная конструкция - Block design

В комбинаторной математике , А конструкция блока представляет собой структура заболеваемости , состоящая из множества вместе с семейством подмножеств , известными как блоки , выбрано таким образом, что частота элементов удовлетворяют определенные условия , делающие коллекцию блоков обладают симметрией (баланс). У них есть приложения во многих областях, включая экспериментальное проектирование , конечную геометрию , физическую химию , тестирование программного обеспечения , криптографию и алгебраическую геометрию .

Без дополнительных спецификаций термин блочный дизайн обычно относится к сбалансированному неполному блочному дизайну ( BIBD ), в частности (и также синонимично) 2-дизайну, который исторически был наиболее интенсивно изученным типом из-за его применения при планировании экспериментов . Его обобщение известно как t-образная конструкция .

Обзор

Дизайн называется сбалансированным (до t ), если все t -подмножества исходного набора встречаются в одинаковом количестве (т. Е. Λ ) блоков. Если t не указано, обычно можно принять его равным 2, что означает, что каждая пара элементов находится в одинаковом количестве блоков, и конструкция попарно сбалансирована . При t = 1 каждый элемент встречается в одном и том же количестве блоков ( номер воспроизведения , обозначенный r ), и дизайн называется регулярным . Любая схема, сбалансированная до t , также сбалансирована по всем более низким значениям t (хотя и с разными λ-значениями ), поэтому, например, попарно сбалансированная ( t = 2) схема также является регулярной ( t = 1). Когда требование балансировки не выполняется, проект все еще может быть частично сбалансирован, если t -подмножества можно разделить на n классов, каждый со своим собственным (различным) λ- значением. Для t = 2 они известны как планы PBIBD ( n ) , классы которых образуют схему ассоциации .

Проекты обычно называют (или предполагают) неполными , что означает, что ни один блок не содержит всех элементов набора, что исключает тривиальный дизайн.

Дизайн блока, в котором все блоки имеют одинаковый размер (обычно обозначаемый k ), называется равномерным или правильным . Все дизайны, обсуждаемые в этой статье, одинаковы. Также были изучены блочные конструкции, которые не обязательно являются однородными; для t = 2 они известны в литературе под общим названием парные сбалансированные схемы (PBD).

Блочные конструкции могут иметь повторяющиеся блоки, а могут и не иметь. Конструкции без повторяющихся блоков называются простыми , и в этом случае «семейство» блоков представляет собой набор, а не мультимножество .

В статистике концепция блочного дизайна может быть расширена до небинарных блочных дизайнов, в которых блоки могут содержать несколько копий элемента (см. Блокирование (статистика) ). Здесь дизайн, в котором каждый элемент встречается одинаковое общее количество раз, называется равноповторным, что подразумевает регулярный дизайн только в том случае, если дизайн также является двоичным. В матрице инцидентности недвоичного плана указано, сколько раз каждый элемент повторяется в каждом блоке.

Регулярные унифицированные конструкции (конфигурации)

Самый простой тип «сбалансированной» конструкции ( t = 1) известен как тактическая конфигурация или 1-конструкция . Соответствующая структура падения в геометрии известна просто как конфигурация , см. Конфигурация (геометрия) . Такой дизайн единообразен и регулярен: каждый блок содержит k элементов, а каждый элемент содержится в r блоках. Количество элементов набора v и количество блоков b связаны соотношением , которое является общим количеством вхождений элемента.

Каждая двоичная матрица с постоянными суммами строк и столбцов является матрицей инцидентности регулярной однородной блочной схемы. Кроме того, каждой конфигурации соответствует бирегулярный двудольный граф, известный как его инцидентность или граф Леви .

Попарно сбалансированные однородные конструкции (2-конструкции или BIBD)

Учитывая конечное множество X (элементов, называемых точками ) и целые числа k , r , λ ≥ 1, мы определяем 2-схему (или BIBD , обозначающую сбалансированный неполный блочный дизайн) B как семейство k -элементных подмножеств X , называемые блоками , такие, что любой x в X содержится в r блоках, а любая пара различных точек x и y в X содержится в λ блоках. Здесь условие, что любой x в X содержится в r блоках, является избыточным, как показано ниже.

Здесь v (количество элементов X , называемых точками), b (количество блоков), k , r и λ - параметры конструкции. (Чтобы избежать вырожденных примеров, также предполагается, что v > k , так что ни один блок не содержит всех элементов набора. Это значение слова «неполный» в названии этих проектов.) В таблице:

v баллов, количество элементов X
б количество блоков
р количество блоков, содержащих данную точку
k количество баллов в блоке
λ количество блоков, содержащих любые 2 (или, как правило, t ) различные точки

Дизайн называется ( v , k , λ ) -дизайном или ( v , b , r , k , λ ) -дизайном. Не все параметры независимы; v , k и λ определяют b и r , и не все комбинации v , k и λ возможны. Два основных уравнения, связывающих эти параметры:

полученные путем подсчета количества пар ( B , p ), где B - блок, а p - точка в этом блоке, и

полученный путем подсчета для фиксированного x троек ( x , y , B ), где x и y - различные точки, а B - блок, содержащий их обе. Это уравнение для каждого x также доказывает, что r постоянно (независимо от x ), даже не предполагая его явно, тем самым доказывая, что условие, что любой x в X содержится в r блоках, является избыточным и r может быть вычислено из других параметров.

Этих условий недостаточно, например, не существует (43,7,1) -конструкции.

Заказ из 2-дизайна определяется как п = г  -  λ . Дополнение из 2-дизайна получается путем замены каждого блока со своим дополнением в множестве точек X . Это также 2-конструкция и параметры v ′ = v , b ′ = b , r ′ = b  -  r , k ′ = v  -  k , λ ′ = λ  +  b  - 2 r . 2-конструкция и ее дополнение имеют одинаковый порядок.

Фундаментальная теорема, неравенство Фишера , названное в честь статистика Рональда Фишера , заключается в том, что b  ≥  v в любом 2-плане.

Примеры

Уникальный (6,3,2) -дизайн ( v = 6, k = 3, λ = 2) состоит из 10 блоков ( b = 10), и каждый элемент повторяется 5 раз ( r = 5). Используя символы 0-5, блоки представляют собой следующие тройки:

012 013 024 035 045 125 134 145 234 235.

и соответствующая матрица инцидентности ( двоичная матрица размера v × b с постоянной суммой строк r и постоянной суммой столбцов k ):

Одна из четырех неизоморфных (8,4,3) -конструкций состоит из 14 блоков, каждый элемент которых повторяется 7 раз. Используя символы 0-7, блоки представляют собой следующие 4-х кортежи:

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.

Этот дизайн ассоциируется с плоскостью Фано , с элементами и блоками дизайна, соответствующими точкам и линиям плоскости. Соответствующая ему матрица инцидентности также может быть симметричной, если метки или блоки отсортированы правильно:

Симметричные 2-схемы (SBIBD)

Случай равенства в неравенстве Фишера, то есть 2-план с равным количеством точек и блоков, называется симметричным планом . Симметричные планы имеют наименьшее количество блоков среди всех 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 = n 2  +  n  + 1 точек в проективном самолет порядка n .

Поскольку проективная плоскость представляет собой симметричный дизайн, мы имеем b = v , что означает также, что b = n 2  +  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)); это две точки с двумя блоками, каждый из которых состоит из обеих точек. Геометрически это двуугольник .
  • Биплан первого порядка имеет 4 точки (и линии размера 3; дизайн 2- (4,3,2)); это полный план с v = 4 и k = 3. Геометрически точки - это вершины тетраэдра, а блоки - его грани.
  • Биплан 2-го порядка является дополнением к плоскости Фано : он имеет 7 точек (и линии размера 4; a 2- (7,4,2)), где линии даны как дополнения к (3-точечной) линии в плоскости Фано.
  • Биплан 3-го порядка имеет 11 точек (и линии размера 5; 2- (11,5,2)) и также известен как Биплан Пэли послеРаймонда Пэли; он связан сорграфом Пэлипорядка 11, который построен с использованием поля с 11 элементами, и представляет собойсхему Адамара 2,связанную с матрицей Адамара размера 12; смPaley строительство I.
Алгебраически это соответствует исключительному вложению проективной специальной линейной группы PSL (2,5) в PSL (2,11) - подробности см. В проективной линейной группе: действие на p точках .
  • Есть три биплана 4-го порядка (и 16 точек, линии 6-го размера; 2- (16,6,2)). Одна из них - конфигурация Куммера . Эти три дизайна также являются дизайнами Menon .
  • Есть четыре биплана 7-го порядка (и 37 точек, линии размера 9; 2- (37,9,2)).
  • Есть пять бипланов 9-го порядка (и 56 точек, линии размера 11; 2- (56,11,2)).
  • Известны два биплана порядка 11 (и 79 точек, линии размера 13; a 2- (79,13,2)).

Бипланы порядков 5, 6, 8 и 10 не существуют, как показывает теорема Брука-Райзера-Чоула .

2-конструкции Адамара

Матрица Адамара размера м является м × м матрицы Н , элементы которой равны ± 1, что HH  = т я м , где Н является транспонированием H и я м является м  ×  м единичная матрица. Матрицу Адамара можно преобразовать в стандартизированную форму (то есть преобразовать в эквивалентную матрицу Адамара), где все элементы первой строки и первого столбца равны +1. Если размер m  > 2, то m должно быть кратно 4.

Для матрицы Адамара размера 4 a в стандартизированной форме удалите первую строку и первый столбец и преобразуйте каждые −1 в 0. Полученная матрица M 0–1 является матрицей инцидентности симметричной 2- (4 a  - 1, 2 а  - 1, а  - 1) конструкция, называемая схемой Адамара 2 . Он содержит блоки / точки; каждый содержит / содержится в точках / блоках. Каждая пара точек содержится ровно в блоках.

Эта конструкция обратима, и матрица инцидентности симметричной 2-схемы с этими параметрами может быть использована для формирования матрицы Адамара размером 4 a .

Разрешаемые 2-конструкции

Разрешимы 2-дизайн является BIBD , чьи блоки могут быть разделены на наборы ( так называемые параллельные классы ), каждый из которых образует разбиение множества точек на BIBD. Набор параллельных классов называется разрешением проекта.

Если 2- ( v , k , λ) разрешимый план имеет c параллельных классов, то b  ≥  v  +  c  - 1.

Следовательно, симметричный дизайн не может иметь нетривиального (более одного параллельного класса) разрешения.

Типичные разрешимые 2-планы - это конечные аффинные плоскости . Решение знаменитой задачи «15 школьниц» - это решение схемы 2- (15,3,1).

Общие сбалансированные конструкции ( t- конструкции)

Принимая во внимание любое положительное целое число т , А т -дизайн Б представляет собой класс K - элементных подмножеств X , называемых блоками , таким образом, что каждая точка х в X появляется в точности г блоков, а каждый т -элементное подмножество Т появляется в точности Л блоков . Числа v (количество элементов X ), b (количество блоков), k , r , λ и t являются параметрами конструкции. Дизайн можно назвать t - ( v , k , λ) -дизайном. Опять же, эти четыре числа определяют b и r, и сами четыре числа не могут быть выбраны произвольно. Уравнения

где λ i - количество блоков, содержащих любой i -элементный набор точек, а λ t = λ.

Обратите внимание, что и .

Теорема : Любой t - ( v , k , λ) -дизайн также является s - ( v , k , λ s ) -дизайном для любого s с 1 ≤  s  ≤  t . (Обратите внимание, что «лямбда-значение» изменяется, как указано выше, и зависит от s .)

Следствием этой теоремы является то, что любой t- дизайн с t ≥ 2 также является 2-дизайном.

Т - ( v , к , 1) -дизайн называется система Штайнер .

Сам по себе термин блочная конструкция обычно означает двухуровневую конструкцию.

Производные и расширяемые t-конструкции

Пусть D = ( Х , В ) быть t- ( v , к , λ ) дизайн и р точка X . Производный план D p имеет набор точек X  - { p } и в качестве набора блоков все блоки D, которые содержат p с удаленным p. Это дизайн ( t  - 1) - ( v  - 1, k  - 1, λ ). Обратите внимание, что производные планы относительно разных точек могут быть не изоморфными. Конструкция Е называется расширением из D , если Е имеет точку р такую , что Е р изоморфна D ; мы называем D расширяемым, если у него есть расширение.

Теорема : если план t - ( v , k , λ ) имеет расширение, то k  + 1 делит b ( v  + 1).

Единственные расширяемые проективные плоскости (симметричные 2- ( n 2  +  n  + 1, n  + 1, 1) планы) - это плоскости 2-го и 4-го порядков.

Каждый дизайн Адамара 2 может быть расширен (до дизайна Адамара 3 ).

Теорема :. Если D , симметричный план 2- ( v , k , λ), расширяемый, то выполняется одно из следующих утверждений:

  1. D - конструкция Адамара 2,
  2. v  = (λ + 2) (λ 2  + 4λ + 2), k  = λ 2  + 3λ + 1,
  3. v  = 495, k  = 39, λ = 3.

Обратите внимание, что проективная плоскость второго порядка - это 2-план Адамара; проективная плоскость четвертого порядка имеет параметры, которые попадают в случай 2; единственными другими известными симметричными 2-конструкциями с параметрами в случае 2 являются бипланы порядка 9, но ни одна из них не является расширяемой; и нет известной симметричной 2-конструкции с параметрами case 3.

Инверсивные самолеты

План с параметрами продолжения аффинной плоскости , т. Е. План 3- ( n 2  + 1, n  + 1, 1), называется конечной инверсной плоскостью или плоскостью Мёбиуса порядка  n .

Можно дать геометрическое описание некоторых инверсионных плоскостей, да и всех известных инверсионных плоскостей. Яйцевидной в PG (3, д ) представляет собой набор д 2  + 1 точек, никакие три коллинеарны. Можно показать, что каждая плоскость (которая является гиперплоскостью, поскольку геометрическая размерность равна 3) PG (3, q ) встречает овоид O либо в 1, либо в q  + 1 точках. Плоские сечения размером q  + 1 из O являются блоками обратной плоскости порядка  q . Возникающий таким образом инверсионный план называется яйцеподобным . Все известные инверсионные плоскости похожи на яйца.

Примером овоида является эллиптическая квадрика , множество нулей квадратичной формы

х 1 х 2 + е ( х 3 , х 4 ),

где f - неприводимая квадратичная форма от двух переменных над GF ( q ). [например, f ( x , y ) = x 2 + xy + y 2 ].

Если q является нечетной степенью двойки, известен другой тип овоида - яйцевид Сузуки – Титса .

Теорема . Пусть q - натуральное число, по крайней мере 2. (a) Если q нечетно, то любой овоид проективно эквивалентен эллиптической квадрике в проективной геометрии PG (3, q ); поэтому q - степень простого числа, и существует единственная яйцеобразная инверсивная плоскость порядка q . (Но неизвестно, существуют ли не яйцеподобные.) (Б) если q четно, то q является степенью двойки и любая инверсивная плоскость порядка q подобна яйцу (но могут быть некоторые неизвестные овоиды).

Частично сбалансированные конструкции (PBIBD)

An н -class Схема объединения состоит из множества X размера V вместе с перегородкой S из X × X в п + 1 бинарных отношений , R 0 , R 1 , ..., R н . Пара элементов в отношении R i называется i th – ассоциатами . Каждый элемент X имеет n i   i- е ассоциированное лицо . Более того:

  • и называется отношением идентичности .
  • Определяя , если R в S , то R * в S
  • Если , количество таких, что и является константой, зависящей от i , j , k, но не от конкретного выбора x и y .

Схема ассоциации коммутативна, если для всех i , j и k . Большинство авторов предполагают это свойство.

Частично уравновешивается неполными конструкции блока с п ассоциированных классов (PBIBD ( п )) представляет собой блочную конструкцию на основе об -set X с Ь блоков , каждый размером к и с каждый элемент появляется в г блоков, таким образом, что существует схема объединения с n классами, определенными на X, где, если элементы x и y являются i- ми ассоциированными, 1 ≤ in , то они вместе находятся ровно в λ i блоках.

PBIBD ( n ) определяет схему ассоциации, но обратное неверно.

Пример

Пусть A (3) будет следующей схемой ассоциации с тремя ассоциированными классами на множестве X = {1,2,3,4,5,6}. Запись ( i , j ) - s, если элементы i и j находятся в отношении R s .

  1 2 3 4 5 6
1  0   1   1   2   3   3 
2  1   0   1   3   2   3 
3  1   1   0   3   3   2 
4  2   3   3   0   1   1 
5  3   2   3   1   0   1 
6  3   3   2   1   1   0 

Блоки PBIBD (3) на основе A (3):

 124    134     235   456 
  125   136    236    456 

Параметры этого PBIBD (3): v  = 6, b  = 8, k  = 3, r  = 4 и λ 1  = λ 2  = 2 и λ 3  = 1. Кроме того, для схемы ассоциации мы имеем n 0  =  n 2  = 1 и n 1  =  n 3  = 2. Матрица инцидентности M равна

а матрица совпадений MM T равна

из которого мы можем восстановить значения λ и r .

Характеристики

Параметры PBIBD ( m ) удовлетворяют:

PBIBD (1) - это BIBD, а PBIBD (2), в котором λ 1  = λ 2, - это BIBD.

Два ассоциированных класса PBIBD

PBIBD (2) изучены больше всего, поскольку они являются простейшими и наиболее полезными из PBIBD. Они делятся на шесть типов на основе классификации известных тогда PBIBD (2) Бозе и Шимамото (1952) :

  1. группа делимая;
  2. треугольная;
  3. Латинский квадрат;
  4. циклический;
  5. частичный тип геометрии;
  6. разнообразный.

Приложения

Математическая тема блочных планов возникла в статистических рамках планирования экспериментов . Эти планы были особенно полезны в приложениях метода дисперсионного анализа (ANOVA) . Это остается важной областью использования блочных конструкций.

Хотя истоки предмета основаны на биологических приложениях (как и в некоторой существующей терминологии), конструкции используются во многих приложениях, где проводятся систематические сравнения, например, при тестировании программного обеспечения .

Матрица инцидентности блока конструкция обеспечивает естественный источник интересных блочных кодов , которые используются в качестве кодов коррекции ошибок . Строки их матриц инцидентности также используются в качестве символов в форме импульсно-позиционной модуляции .

Статистическое приложение

Предположим, что исследователи рака кожи хотят протестировать три разных солнцезащитных крема. Они наносят два разных солнцезащитных крема на верхнюю часть рук испытуемого. После УФ-излучения регистрируют раздражение кожи в виде солнечных ожогов. Количество процедур - 3 (солнцезащитные кремы), размер блока - 2 (руки на человека).

Соответствующее BIBD может быть получено с помощью R -функции design.bib из Р-пакет agricolae и указано в следующей таблице:

Сюжеты Блокировать Уход
101 1 3
102 1 2
201 2 1
202 2 3
301 3 2
302 3 1

Исследователь выбирает параметры v = 3 , k = 2 и λ = 1 для конструкции блока, которые затем вставляются в R-функцию. Впоследствии остальные параметры b и r определяются автоматически.

Используя базовые соотношения, мы вычисляем, что нам нужно b = 3 блока, то есть 3 тестовых человека, чтобы получить сбалансированный неполный дизайн блока. Обозначив блоки A , B и C , чтобы избежать путаницы, мы имеем конструкцию блока,

A = {2, 3 },    B = {1, 3 } и C = {1, 2 }.

Соответствующая матрица инцидентности указана в следующей таблице:

Уход Блок А Блок Б Блок C
1 0 1 1
2 1 0 1
3 1 1 0

Каждая обработка происходит в 2 блока, поэтому r = 2 .

Только один блок ( C ) содержит лечение 1 и 2 одновременно, и то же самое относится к парам обработок (1,3) и (2,3). Следовательно, λ = 1 .

В этом примере невозможно использовать полный дизайн (все процедуры в каждом блоке), потому что нужно протестировать 3 солнцезащитных крема, но только 2 руки на каждого человека.

Смотрите также

Заметки

Рекомендации

  • Ландер, ES (1983), Симметричные конструкции: алгебраический подход , Cambridge University Press, ISBN 978-0-521-28693-0
  • Линднер, CC; Роджер, Калифорния (1997), Теория дизайна , Бока-Ратон: CRC Press, ISBN 0-8493-3986-3
  • Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные задачи планирования экспериментов . Дувр. ISBN 978-0-486-65685-4.
  • ван Линт, JH; Уилсон, Р.М. (1992). Курс комбинаторики . Издательство Кембриджского университета. ISBN 978-0-521-41057-1.

Внешние ссылки