Блок-схема — це множина разом із сімейством підмножин (у деяких випадках дозволено повторення підмножин), члени якого задовольняють деяким властивостям, які вважаються корисними для конкретного застосування. Ці застосування стосуються різних галузей, зокрема, планування експерименту, скінченної геометрії, тестування програмного забезпечення, криптографії та алгебричної геометрії. Розглядалося багато варіантів, але найінтенсивніше вивчалися зрівноважені неповні блок-схеми (Balanced Incomplete Block Designs, BIBD, 2-схеми), які історично пов'язані зі статистичними задачами при плануванні експерименту.

Блок-схему, де всі блоки мають один розмір, називають однорідною. Всі схеми, обговорювані в цій статті, однорідні. Попарно зрівноважені схеми (Pairwise balanced designs, PBD) є прикладами блок-схем, які не обов'язково однорідні.

Визначення BIBD (або 2-схеми)
Якщо задана скінченна множина (елементів, які називають точками ) і цілі числа , , , ми визначаємо 2-схему B як сімейство -елементних підмножин множини , таких, що будь-який елемент  із  міститься в  блоках, і будь-яка пара різних точок  і  в  міститься в   блоках.

Слово «сімейство» у визначенні вище можна замінити словом «множина», якщо повторення блоків не дозволяється. Схеми, в яких повторення блоків заборонено, називають простими.

Тут  (кількість елементів , званих точками),  (кількість блоків), ,  і  є параметрами схеми. (Щоб уникнути вироджених прикладів, передбачається, що , отже жоден блок не містить усіх елементів множини. Тому в назві схем є слово «неповні».) В таблиці:



v 

точки, число елементів X


b 

число блоків


r 

число блоків, які містять дану точку


k 

число точок у блоці


λ 

число блоків, які містять будь-які 2 (або, загальніше, t) точок



Схему називають -схемою або -схемою. Параметри не є незалежними — ,  і  визначають  і , і не всі комбінації ,  і  допустимі. Дві основні рівністі, що містять ці параметри:

: 

виходить з підрахунку пар , де  — блок, а  — точка в цьому блоці;

: 

виходить з підрахунку трійок , де  і  — різні точки, і  — блок, що містить обидві точки, і ділення числа трійок на .

Ці умови не достатні, оскільки, наприклад, (43,7,1)-схеми немає.

Порядок 2-схеми визначають як . Доповнення 2-схеми отримують заміною кожного блока його доповненням у множині точок X. Доповнення є також 2-схемою і має параметри , , , , . 2-Схема та її доповнення мають однаковий порядок.

Фундамендальна теорема, нерівність Фішера, названа ім'ям статистика Рональда Фішера, стверджує, що в будь-якій 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-схему з однаковою кількістю точок у блоках, називають симетричною схемою . Симетричні схеми мають найменшу кількість блоків серед усіх 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 = 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)-схема); це дві точки та два блоки, які містять обидві точки. Геометрично це двокутник.
* Біпланарна геометрія порядку 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, див. статтю «Побудова Пелі».

: Алгебрично це відповідає особливому вкладенню проєктивної спеціальної лінійної групи PSL(2,5) у PSL(2,11).

* Є три біпланарні геометрії порядку 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-(4 a − 1, 2 a − 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-схеми
Нехай D = (X, B) — t-(v,k,λ)-схема, і нехай p — точка множини X. Похідна схема D'p має множину точок 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-(n 2 + n + 1, n + 1, 1)-схеми) — це тільки ті, порядки яких дорівнюють 2 і 4.

Будь-яка 2-схема Адамара розширювана (до 3-схеми Адамара).

Теорема. Якщо D, симетрична 2-(v, k ,λ)-схема, розширювана, виконується одне з:

# D є 2-схемою Адамара,
# v = (λ + 2) (λ 2 + 4λ + 2), k = λ 2 + 3λ + 1,
# v = 495, k = 39, λ = 3.

Зауважимо, що проєктивна площина порядку 2 є 2-схемою Адамара. Проективна площина порядку 4 має параметри, які підпадають під випадок 2. Інші відомі симетричні 2-схеми з параметрами з випадку 2 — біпланарні геометрії порядку 9, але жодна з них не розширювана. Симетричні 2-схеми з параметрами випадку 3 невідомі.

Кругова площина
Схему з параметрами розширення , тобто 3-(n 2 + 1, n + 1, 1)-схему, називають скінченною круговою площиною або площиною Мебіуса порядку n.

Можна дати геометричний опис деяких кругових площин, більш того, всіх відомих кругових площин.  у PG(3,q) є множиною з q 2 + 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 розбиттю S, випливає належність R* розбиттю S.
* Якщо , кількість елементів , таких що  і , стале (дорівнює ) і це число залежить від i, j, k, але не від вибору x та y.

Схема поєднань коммутативна, якщо  для всіх 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.





  

 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. 

Властивості
Параметри 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, вона визначається такою таблицею:


Дослід

 Блок

 Лікування


 101

 1

 3


 102

 1

 2


 201

 2

 1


 202

 2

 3


 301

 3

 2


 302

 3

 1

Дослідник вибирає параметри блок-схеми ,  та , які підставляються в R-функцію. Решта параметрів ( і ) визначаються автоматично.

Використовуючи базові відношення, ми обчислюємо, що нам, щоб одержати зрівноважену неповну блок-схему, потрібно  блоків, тобто 3 піддослідних. Позначивши блоки  і , отримуємо блок-схему:

: ,    і .

Відповідну матрицю інцидентності наведено в таблиці:


Лікування

 Блок A

 Блок B

 Блок C


 1

 0

 1

 1


 2

 1

 0

 1


 3

 1

 1

 0

Кожне лікування міститься у 2 блоках, так що .

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

У цьому прикладі неможливо використати повну схему (всі лікування в кожному блоці), оскільки є 3 креми і лише по 2 руки в кожного випробуваного.

Див. також
* Геометрія інцидентності
* Лінійний простір (геометрія)
* Система Штейнера

Примітки


Література

* 
* 
* 
* 
* 
*
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
*
*
*


Посилання

*  DesignTheory.Org — бази даних комбінаторних, статистичних та експериментальних блок-схем. Програми та інші ресурси школи математичних наук у Queen Mary College, Лондонський університет.
*  Design Theory Resources — сторінка Пітера Кемерона про вебресурси з теорії схем.
* 



