Lohkon suunnittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. syyskuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Lohkokaavio on joukko yhdessä osajoukkojen perheen kanssa (osajoukkojen toisto on joissain tapauksissa sallittu), jonka jäsenet täyttävät joitain ominaisuuksia, joita pidetään hyödyllisinä tietyssä sovelluksessa. Nämä sovellukset tulevat eri aloilta, mukaan lukien kokeiden suunnittelu , rajallinen geometria , ohjelmistotestaus , kryptografia ja algebrallinen geometria . Monia vaihtoehtoja on harkittu, mutta intensiivisimmin tutkittuja ovat tasapainotetut epätäydelliset lohkosuunnittelut (Balanced Incomplete Block Designs, BIBD , 2-schemes), joita on historiallisesti liitetty tilastollisiin ongelmiinkokeilun suunnittelu [1] [2] .

Lohkokaaviota, jossa kaikki lohkot ovat samankokoisia, kutsutaan homogeeniseksi . Tässä artikkelissa käsitellyt piirit ovat kaikki samoja. Pairwise balanced designs (PBD) ovat esimerkkejä lohkokaavioista, jotka eivät välttämättä ole yhtenäisiä.

BIBD:n (tai 2-skeeman) määritelmä

Kun on annettu äärellinen joukko X (elementtejä, joita kutsutaan pisteiksi ) ja kokonaisluvut k , r , λ ≥ 1, määritämme 2-skeeman B ryhmäksi X :n k - elementtiosajoukkoja , joita kutsutaan lohkoiksi , siten että mikä tahansa elementti x X : stä sisältyy r lohkoon, ja mikä tahansa erillisten pisteiden x ja y pari X : ssä sisältyy λ - lohkoihin.

Yllä olevan määritelmän sana "perhe" voidaan korvata sanalla "joukko", jos lohkojen toistaminen ei ole sallittua. Piirejä, joissa lohkojen toistaminen ei ole sallittua, kutsutaan yksinkertaisiksi .

Tässä v ( pisteiksi kutsuttujen X :n alkioiden lukumäärä ), b (lohkojen lukumäärä), k , r ja λ ovat piiriparametreja . (Degeneroituneiden esimerkkien välttämiseksi oletetaan, että v > k , jolloin mikään lohko ei sisällä kaikkia joukon alkioita. Siksi piirien nimessä on sana "epätäydellinen".) Taulukossa:

v	pisteet, elementtien lukumäärä X
b	lohkojen määrä
r	tietyn pisteen sisältävien lohkojen lukumäärä
k	pisteiden määrä lohkossa
λ	lohkojen lukumäärä, jotka sisältävät mitkä tahansa 2 (tai yleisemmin t ) pistettä

Piiriä kutsutaan ( v , k , λ )-piiriksi tai ( v , b , r , k , λ )-piiriksi. Parametrit eivät ole riippumattomia - v , k ja λ määrittävät b ja r , eivätkä kaikki v :n , k :n ja λ :n yhdistelmät ole sallittuja. Kaksi perusyhtälöä, jotka sisältävät nämä parametrit

bk=vr,

saadaan laskemalla pareja ( B , p ) missä B on lohko ja p on piste siinä lohkossa

\lambda (v-1)=r(k-1),

saadaan laskemalla tripletit ( p , q , B ), missä p ja q ovat erillisiä pisteitä ja B on lohko, joka sisältää molemmat pisteet, ja jakamalla triplettien lukumäärä v :llä .

Nämä ehdot eivät ole riittäviä, koska esimerkiksi (43,7,1)-kaaviota ei ole olemassa [3]

2-skeeman järjestys määritellään n = r − λ . 2-skeeman komplementti saadaan korvaamalla jokainen lohko sen komplementilla pistejoukossa X . Komplementti on myös 2-skeema ja sillä on parametrit v ′ = v , b ′ = b , r ′ = b − r , k ′ = v − k , λ ′ = λ + b − 2 r . 2-skeemalla ja sen täydennyksellä on sama järjestys.

Peruslause, Fisherin epäyhtälö , joka on nimetty tilastotieteilijä Ronald Fisherin mukaan, sanoo, että b ≥ v missä tahansa 2-skeemassa.

Graafiteorian kannalta 2 -skeeman määritelmä voidaan muotoilla uudelleen seuraavasti: lohkokaavio on peitto, jossa on pisteissä olevan täydellisen graafin moninkertaisuus pisteiden täydellisillä graafilla . Vuokaaviot ja ovat triviaaleja, joten yleensä oletetaan, että . $\lambda$ $v$ $k$ $k=0,1$ $v$ $2\leq k\leq n-1$

Esimerkkejä

Ainoassa (6,3,2)-piirissä on 10 lohkoa ( b = 10) ja jokainen elementti toistetaan 5 kertaa ( r = 5) [4] . Jos käytetään symboleja 0–5, lohkot sisältävät seuraavat kolmiot:

012 013 024 035 045 125 134 145 234 235.

Yhdessä neljästä ei-isomorfisesta (8,4,3)-kaaviosta on 14 lohkoa, joissa elementtejä toistetaan 7 kertaa. Käyttämällä symboleja 0 - 7, lohkot ovat seuraavat neloset: [4]

0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.

Ainoassa (7,3,1)-piirissä on 7 lohkoa, joissa jokainen elementti toistetaan 3 kertaa. Jos käytetään symboleja 0 - 6, seuraavat kolmiot toimivat lohkoina: [4]

013 026 045 124 156 235 346. Jos elementit ymmärretään Fano-tason pisteiksi , niin nämä lohkot ovat suoria viivoja.

Symmetrinen BIBD:t

Tasa-arvotapausta Fisherin epäyhtälössä, eli 2-piiriä, jossa on sama määrä pisteitä lohkoissa, kutsutaan symmetriseksi piiriksi [5] . Symmetrisissä piireissä on pienin määrä lohkoja kaikista 2-piireistä, joissa on sama määrä pisteitä.

Symmetrisessä piirissä r = k täyttyy , kuten myös b = v , ja vaikka tämä ei pidä paikkaansa mielivaltaisissa 2-piireissä, symmetrisissä piireissä millä tahansa kahdella eri lohkolla on yhteistä λ - pistettä [6] . Reiserin lause antaa päinvastaisen johtopäätöksen - jos X on joukko v alkioita ja B on joukko v k -elementtejä ("lohkoja"), niin että millä tahansa kahdella eri lohkolla on täsmälleen λ pistettä yhteistä , niin ( X , B ) on symmetrinen lohkokaavio [7] .

Symmetrisen piirin parametrit täyttävät tasa-arvon

\lambda (v-1)=k(k-1).

Tasa-arvo asettaa voimakkaan rajoitteen v :lle , joten pisteiden määrä on kaukana mielivaltaisesta. Brook-Reiser-Chowl-lause antaa tarpeellisen, mutta ei riittävän ehdon symmetristen piirien olemassaololle niiden parametrien suhteen.

Seuraavat ovat tärkeitä esimerkkejä symmetrisistä 2-piireistä:

Projektiiviset tasot

Äärelliset projektitiiviset tasot ovat symmetrisiä 2-kaavioita, joissa λ = 1 ja kertaluku n > 1. Näille kaavioille symmetrisen kaavion yhtäläisyys on:

v-1=k(k-1).\,

Koska k = r , voidaan kirjoittaa projektiivitason järjestykseksi n = k − 1 ja yllä olevasta yhtälöstä saadaan v = ( n + 1) n + 1 = n 2 + n + 1 pistettä projektiivissä kertaluvun n taso .

Koska projektiivinen taso on symmetrinen piiri, meillä on b = v , mikä tarkoittaa, että myös b = n 2 + n + 1. Numero b on viivojen lukumäärä projektitiivisessa tasossa. Viivoja ei voi toistaa, koska λ = 1, joten projektitiivitaso on yksinkertainen 2-kaavio, jossa viivojen määrä ja pisteiden määrä ovat aina yhtä suuret. Projektiiviselle tasolle k on pisteiden lukumäärä suoralla, ja se on yhtä suuri kuin n + 1. Vastaavasti r = n + 1 on niiden viivojen lukumäärä, joihin annettu piste osuu.

Kohdalle n = 2 meillä on kertalukua 2 oleva projektiivinen taso, jota kutsutaan myös Fanon tasoksi , jossa v = 4 + 2 + 1 = 7 pistettä ja 7 suoraa. Fano-tasossa millä tahansa suoralla on täsmälleen n + 1 = 3 pistettä, ja jokainen piste kuuluu n + 1 = 3 viivaan.

Tiedetään, että projektiivitasoja on olemassa kaikille alkulukujen ja niiden potenssien kertaluvuille. Ne muodostavat ainoan tunnetun äärettömän symmetristen lohkokaavioiden perheen [8] .

Kaksitasogeometria

Kaksitasogeometria on symmetrinen 2-kaavio, jossa λ = 2. Toisin sanoen mikä tahansa kahden pisteen joukko sisältyy kahteen lohkoon ("suoraan"), ja mitkä tahansa kaksi suoraa leikkaavat kaksi pistettä [8] . Kaksitasoiset geometriat ovat samanlaisia kuin projektiiviset tasot, paitsi että kaksi pistettä eivät määritä suoraa (ja kaksi suoraa eivät määritä pistettä). Kaksitasogeometriassa kaksi pistettä määrittelee kaksi suoraa (vastaavasti kaksi suoraa määrittelee kaksi pistettä). Biplanaarinen geometria, jonka kertaluku on n , on piiri, jonka lohkoissa on k = n + 2 pistettä.Pisteiden kokonaismäärä on v = 1 + ( n + 2)( n + 1)/2 (koska r = k ).

Alla on lueteltu 18 tunnettua esimerkkiä [9] .

(Triviaali kaavio) Biplanaarisessa geometriassa kertaluvun 0 pisteessä on 2 pistettä (ja 2-koon viivat; 2-(2,2,2)-kaavio); se on kaksi pistettä ja kaksi lohkoa, jotka sisältävät molemmat pisteet. Geometrisesti se on kaksikko .
Biplanaarisessa geometriassa kertaluvun 1 pisteessä on 4 pistettä (ja viivoja, joiden koko on 3; kaavio 2-(4,3,2)); tämä on täydellinen piiri, jossa v = 4 ja k = 3. Geometrisesti pisteet ovat tetraedrin huippuja ja lohkot pintoja.
Biplanaarinen geometria, kertaluokkaa 2, on Fanon tason komplementti - se sisältää 7 pistettä (ja viivoja, joiden koko on 4; 2-(7,4,2)), jossa suorat annetaan (3- pisteisten) viivojen komplementteina Fano-koneesta [10] .
Järjestyksen 3 kaksitasogeometriassa on 11 pisteen (ja 5-koon viivat; 2-(11,5,2)) kaavio, joka tunnetaan nimellä Paley biplanar geometria Raymond Paleyn mukaan ; Piiri liittyy 11 - kertaiseen Paley-graafiin , joka on konstruoitu käyttämällä 11-elementin kenttää, ja se on 2-Hadamard-piiri , joka liittyy Hadamard-matriisiin, jonka koko on 12, katso Paley-konstruktio I.

Algebrallisesti tämä vastaa projektiivisen erikoislineaariryhmän PSL (2,5) erityistä upottamista PSL :ään (2,11) – katso projektiivinen lineaarinen ryhmä: toiminta p - pisteillä [11] saadaksesi yksityiskohtaisen kuvauksen .

Kaksitasoisia geometrioita on kolme kertaluvun 4 (16 pistettä, viivat kooltaan 6; 2-(16,6,2)) kaavioita. Nämä kolme järjestelmää ovat myös Menonin järjestelmiä .
Kaksitasoisia geometrioita on neljä luokkaa 7 (37 pistettä, viivat kooltaan 9; kaaviot 2-(37,9,2)) [12]
Kaksitasoisia geometrioita on viisi luokkaa 9 (56 pistettä, viivat kooltaan 11; kaaviot 2-(56,11,2)) [13]
Tunnetaan kaksi kaksitasoista geometriaa, joiden kertaluokka on 11 (79 pistettä, viivat kooltaan 13; kaaviot 2-(79,13,2)) [14] .

2-Hadamardin mallit

Hadamard-matriisi m on m × m -matriisi H , jonka alkiot ovat ±1 siten, että HH ⊤ = m E m , missä H ⊤ on yhtä suuri kuin transponoitu matriisi H ja E m on m × m identtisyysmatriisi. Hadamard-matriisi voidaan kirjoittaa vakiomuotoon (eli pelkistettynä vastaavaan Hadamard-matriisiin), jossa ensimmäinen rivi ja ensimmäinen sarake koostuvat +1:stä. Jos koko m > 2, m on oltava jaollinen 4:llä.

Kun annetaan Hadamard-matriisi, jonka koko on 4 a vakiomuodossa, poista ensimmäinen rivi ja ensimmäinen sarake ja korvaa kaikki -1:n elementit nollalla. Tuloksena on matriisi M , joka koostuu 0:sta ja 1:stä, joka on 2- symmetrinen ilmaantuvuusmatriisi . (4 a − 1 , 2 a − 1, a − 1) kaavioita. Tätä järjestelmää kutsutaan Hadamard 2 -skeemaksi [15] . Kaavio sisältää lohkoja, joista jokainen sisältää pisteitä, ja pisteitä, jotka sisältyvät lohkoihin. Jokainen pistepari sisältyy täsmälleen lohkoihin. $4a-1$ $2a-1$ $4a-1$ $2a-1$ $a-1$

Rakenne on reversiibeli, ja symmetrisen 2-piirin tulomatriisia näillä parametreilla voidaan käyttää muodostamaan Hadamard-matriisi, jonka koko on 4 a .

Ratkaistava 2-skeema

Päätettävissä oleva 2-skeema on BIBD, jonka lohkot voidaan jakaa joukoiksi (kutsutaan rinnakkaisluokiksi ), joista jokainen muodostaa pistejakoosan BIBD:stä. Rinnakkaisten luokkien joukkoa kutsutaan skeeman resoluutioksi .

Jos 2-( v , k ,λ) ratkaistavassa piirissä on c rinnakkaisluokkaa, niin b ≥ v + c − 1 [16] .

Siksi symmetrisellä piirillä ei voi olla ei-triviaali (enemmän kuin yksi rinnakkaisluokka) resoluutio [17] .

Arkkityyppiset pääteltävissä olevat 2-skeemat ovat äärellisiä projektiivitasoja . Ratkaisu koulutyttöjä koskevaan kuuluisaan Kirkman-ongelmaan on 2-(15,3,1)-järjestelmän ratkaisu [18] .

Yleistykset: t -skeemat

Kun otetaan huomioon mikä tahansa positiivinen luku t , t -skeema B on X :n k - alkioisten osajoukkojen luokka , joita kutsutaan lohkoiksi siten, että mikä tahansa X :n piste x esiintyy täsmälleen r lohkossa ja mikä tahansa T :n t -elementtiosajoukko sisältyy täsmälleen λ lohkot. Numerot v (elementtien lukumäärä X :ssä ), b (lohkojen lukumäärä), k , r , λ ja t toimivat piiriparametreina . Kaavaa voidaan kutsua t- ( v , k ,λ)-kaavioksi. Jälleen nämä neljä numeroa määrittävät b :n ja r :n, eikä itse neljää numeroa voida valita mielivaltaisesti. Heitä yhdistävät tasa-arvot

\lambda _{i}=\lambda \left.{\binom {vi}{ti}}\right/{\binom {ki}{ti}}{\text{ for }}i=0,1 ,\ldots ,t,

missä λ i on niiden lohkojen lukumäärä, jotka sisältävät minkä tahansa i - elementtijoukon pisteitä.

Huomaa, että . ${\displaystyle b=\lambda _{0}=\lambda {v \choose t}/{k \choose t))$

Lause : [19] Mikä tahansa t- ( v , k ,λ)-kaavio on myös s- ( v , k , λs )-kaavio mille tahansa luvulle s , jos 1 ≤ s ≤ t . (Huomaa, että "lambda-arvo" vaihtelee kuten yllä ja riippuu s :stä .)

Tämän lauseen seuraus on, että mikä tahansa t - kaavio, jossa t ≥ 2, on myös 2-skeema.

Piiriä t -( v , k ,1) kutsutaan Steiner-järjestelmäksi .

Termi lohkokaavio sinänsä tarkoittaa yleensä 2-kaaviota.

Johdannaiset ja laajennettavat t-skeemat

Olkoon D = ( X , B ) t-( v , k , λ ) - piiri ja olkoon p X : n piste . Johdetussa piirissä D p on pisteiden joukko X − { p } ja lohkojoukona kaikki lohkot D , jotka sisältävät p ja joista piste p on poistettu. Tämä piiri on ( t − 1)-( v − 1, k − 1, λ ) -piiri. Huomaa, että eri pisteille generoidut piirit eivät välttämättä ole isomorfisia. Kaavaa E kutsutaan kaavion D laajennukseksi , jos E :llä on piste p siten, että E p on isomorfinen D :n kanssa . Kutsumme D :tä laajennettavaksi , jos skeemalla on laajennus.

Lause : [20] Jos t -( v , k , λ ) -skeemalla on laajennus, niin k + 1 jakaa b ( v + 1).

Laajentuvat projektiivitasot (symmetriset 2-( n 2 + n + 1, n + 1, 1) kaaviot) ovat vain niitä, joiden kertaluku on 2 ja 4 [21] .

Mikä tahansa 2-Hadamard-skeema on laajennettavissa ( 3-Hadamardin malliin asti ) [22] .

Lause : [23] Jos D , symmetrinen 2-( v , k ,λ) piiri, on laajennettavissa, jokin seuraavista:

D on Hadamard 2 -kaavio,
v = (λ + 2) (λ 2 + 4λ + 2), k = λ 2 + 3λ + 1,
v = 495, k = 39, λ = 3.

Huomaa, että toisen asteen projektiivinen taso on Hadamardin 2-kaavio. Neljännen kertaluvun projektiivisella tasolla on parametrit, jotka kuuluvat tapaukseen 2. Muut tunnetut symmetriset 2-kaaviot tapauksen 2 parametreillä ovat luokkaa 9 kaksitasoisia geometrioita, mutta mikään niistä ei ole laajennettavissa. Symmetriset 2-kaaviot tapauksen 3 parametreilla ovat tuntemattomia [24] .

Pyöreä taso

Kaavaa , jossa on affiinitason laajennusparametrit , eli 3-( n 2 + 1, n + 1, 1) -kaaviota, kutsutaan äärelliseksi ympyrätasoksi tai Möbius-tasoksi , jonka kertaluku on n .

On mahdollista antaa geometrinen kuvaus joistakin ympyrätasoista, ei, kaikista tunnetuista ympyrätasoista. Soikea PG(3, q ) on joukko q 2 + 1 pistettä, joista yksikään ei ole kollineaarinen. Voidaan osoittaa, että mikä tahansa taso (joka on hypertaso dimensiossa 3) PG(3, q ) leikkaa munanmuotoisen O joko yhdessä pisteessä tai pisteessä q + 1. Soikean O :n, jonka koko on q + 1, leikkauspisteet tason kanssa ovat ympyränmuotoisen tason lohkoja, joiden suuruus on q . Mitä tahansa näin saatua ympyrätasoa kutsutaan munamaiseksi . Kaikki tunnetut pyöreät tasot ovat munamaisia.

Esimerkki munasolusta on elliptinen neliö , neliömuodon nollien joukko

x 1 x 2 + f ( x 3 , x 4 ),

jossa f on redusoitumaton neliömuoto kahdessa muuttujassa GF( q ) -arvon yli. [ esimerkiksi f ( x , y ) = x2 + xy + y2 ] .

Jos q on luvun 2 pariton potenssi, tunnetaan toinen munalaji, Suzuki-Tits ovid .

Lause . Olkoon q positiivinen kokonaisluku vähintään 2. (a) Jos q on pariton, mikä tahansa munamuoto on projektitiivisesti ekvivalentti elliptiselle neliölle projektiivisessa geometriassa PG(3, q ), joten q on alkuluvun potenssi ja on olemassa uniikki munamainen ympyrätaso kertalukua q ( (b) jos q on parillinen, niin q on 2:n potenssi ja mikä tahansa ympyrätaso q kertaluokkaa on munamainen (ehkä siellä on joitain tuntemattomia munamaisia).

Osittain balansoidut piirit (PBIBD)

N - luokan relaatioskeema koostuu joukosta X , jonka koko on v , yhdessä joukon X × X osion S kanssa n + 1 binäärisuhteisiin R 0 , R 1 , ..., R n . Alkuparin sanotaan olevan suhteessa R i (elementit i - yhdistetty ). Jokaisella X :n elementillä on n i i -nnettä yhdistelmää. Sitä paitsi:

$R_{0}=\{(x,x):x\in X\}$ ja sitä kutsutaan identiteettisuhteeksi .
Jos määrittelemme , niin siitä tosiasiasta, että R kuuluu osioon S , seuraa, että R* kuuluu osioon S ${\displaystyle R^{*}:=\{(x,y)|(y,x)\in R\))$
Jos , alkioiden , kuten ja , lukumäärä on vakio (yhtä kuin ) ja tämä luku riippuu i , j , k , mutta ei x :n ja y :n valinnasta . ${\näyttötyyli (x,y)\in R_{k))$ $z\in X$ ${\näyttötyyli (x,z)\in R_{i))$ ${\näyttötyyli (z,y)\in R_{j))$ ${\displaystyle p_{ij}^{k))$

Yhdistelmäkaavio on kommutatiivinen , jos kaikille i , j ja k . Useimmat kirjoittajat olettavat tämän ominaisuuden. ${\displaystyle p_{ij}^{k}=p_{ji}^{k))$

Osittain tasapainotettu epätäydellinen lohkokaavio , jossa on n yhdistelmäluokkaa (PBIBD( n )) on lohkokaavio, joka perustuu joukkoon X, jossa on v elementtejä, joissa kussakin on k k elementin lohkoa , joissa jokainen elementti esiintyy r lohkossa ja jolle on on yhdistelmämalli, jossa on X :lle määritelty n luokkaa , jolloin jos alkiot x ja y i -yhtyvät arvolle 1 ≤ i ≤ n , ne sisältyvät yhdessä tarkalleen λ i -lohkoihin .

PBIBD( n ) määrittelee yhdistelmäkaavion, mutta päinvastoin ei pidä paikkaansa [25] .

Esimerkki

Olkoon A (3) yhdistelmämalleja, joissa on kolme luokkaa joukossa X = {1,2,3,4,5,6}. Taulukon elementin ( i , j ) arvo on yhtä suuri kuin s , jos alkiot i ja j ovat suhteessa Rs .

	yksi	2	3	neljä	5	6
yksi	0	yksi	yksi	2	3	3
2	yksi	0	yksi	3	2	3
3	yksi	yksi	0	3	3	2
neljä	2	3	3	0	yksi	yksi
5	3	2	3	yksi	0	yksi
6	3	3	2	yksi	yksi	0

PBIBD(3)-lohkot perustuen A (3):

124	134	235	456
125	136	236	456

Tämän PBIBD(3):n parametrit ovat: v = 6, b = 8, k = 3, r = 4 ja λ 1 = λ 2 = 2 ja λ 3 = 1. Myös relaatiokaaviolle meillä on n 0 = n 2 = 1 ja n 1 = n 3 = 2. [26]

Ominaisuudet

Parametrit PBIBD( m ) täyttävät yhtälöt: [27]

$vr=bk$
$\sum _{i=1}^{m}n_{i}=v-1$
$\sum _{i=1}^{m}n_{i}\lambda _{i}=r(k-1)$
${\displaystyle \sum _{u=0}^{m}p_{ju}^{h}=n_{j))$
${\displaystyle n_{i}p_{jh}^{i}=n_{j}p_{ih}^{j))$

PBIBD(1) on BIBD, PBIBD(2), jossa λ 1 = λ 2 on myös BIBD [28] .

PBIBD kahdella yhdistelmäluokalla

PBIBD(2)-järjestelmiä on tutkituimmin niiden yksinkertaisuuden ja hyödyllisyyden vuoksi [29] . Ne jakautuvat kuuteen tyyppiin [30] , jotka perustuvat Bosen ja Shimamoton luokitukseen tuolloin tunnetuista PBIBD(2) -järjestelmistä: [31] [32]

jaettu ryhmiin
kolmion muotoinen
kirjoita "latinalainen neliö"
syklinen
osittainen geometria
levätä

Sovellukset

Vuokaavioiden matemaattinen aihe syntyi kokeen suunnittelun tilastollisena perustana . Kaaviot ovat olleet erityisen hyödyllisiä varianssianalyysin (ANOVA) tekniikan sovelluksissa . Tämä alue on edelleen olennainen osa lohkokaavioiden käyttöä.

Vaikka biologiset sovellukset olivat lähde, skeemoja käytetään monilla muilla alueilla, joilla tehdään systemaattista vertailua, kuten ohjelmistotestauksessa .

Vuokaavion esiintyvyysmatriisi tarjoaa luonnollisen lähteen mielenkiintoisille lohkokoodeille , joita käytetään virheenkorjauskoodeina . Insidenssimatriisin rivejä käytetään myös symboleina pulssivaihemodulaatiossa [33] .

Tilastosovellukset

Oletetaan, että ihosyövän tutkijat haluavat testata kolmea erilaista aurinkovoidetta. He levittävät kahta erilaista voidetta koehenkilöiden käsien yläpuolelle. Ultraviolettivalolle altistumisen jälkeen ne kirjaavat ihoärsytysasteen auringonpolttamana. Hoitokertoja on 3 (voiteiden määrä), lohkokoko on 2 (käsien määrä per henkilö).

Vastaava BIBD-skeema voidaan saada R-package agricolaen R-funktiona design.bib , ja se määritellään seuraavassa taulukossa:

Kokemus	Lohko	Hoito
101	yksi	3
102	yksi	2
201	2	yksi
202	2	3
301	3	2
302	3	yksi

Tutkija valitsee lohkokaavioon parametrit v = 3 , k = 2 ja λ = 1 , jotka korvataan R-funktiolla. Muut parametrit b ja r määritetään automaattisesti.

Perussuhteita käyttämällä lasketaan, että tarvitsemme b = 3 lohkoa eli 3 kohdetta tasapainoisen epätäydellisen vuokaavion saamiseksi. Merkitsemällä lohkoja A , B ja C , jotta ei menisi sekaan, saamme lohkokaavion,

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

Vastaava ilmaantuvuusmatriisi on annettu taulukossa:

Hoito	Lohko A	Lohko B	Lohko C
yksi	0	yksi	yksi
2	yksi	0	yksi
3	yksi	yksi	0

Jokainen hoito sisältyy 2 lohkoon, joten r = 2 .

Vain yksi lohko ( C ) sisältää hoitoja 1 ja 2 samanaikaisesti, ja sama pätee hoitopareihin (1,3) ja (2,3). Siksi λ=1 .

Tässä esimerkissä ei ole mahdollista käyttää koko hoito-ohjelmaa (kaikki hoidot kussakin lohkossa), koska koehenkilöä kohden on 3 voidetta ja vain 2 kättä.

Katso myös

Muistiinpanot

↑ Colbourn, Dinitz, 2007 , s. 17-19.
↑ Stinson, 2003 , s. yksi.
↑ Todistuksen antoi Tarry vuonna 1900, ja hän osoitti, ettei ole olemassa 6:n kertaluvun ortogonaalista latinalaista neliöparia . 2-kaavio ilmoitetuilla parametreilla vastaa viiden keskenään ortogonaalisen kuuden kertaluvun latinalaisen neliön olemassaoloa.
↑ 1 2 3 Colbourn, Dinitz, 2007 , s. 27.
↑ Näitä kaavioita kutsutaan myös projektiivisiksi tai neliökaavioiksi . Näitä vaihtoehtoisia nimiä käytettiin yritettäessä korvata termi "symmetrinen", koska näissä piireissä ei ole mitään symmetristä (termin tavallisessa merkityksessä). Termiä projektiivinen käytti P. Dembowski ( Dembowski 1968 ), analogisesti yleisimmän esimerkin, projektitiivisten tasojen kanssa. Termiä neliö käytti P. Cameron ( Cameron, van Lint 1991 ), joka heijastaa yhtäläisyyttä v = b ilmaantuvuusmatriisille. Kumpaakaan termiä ei käytetty korvaavana ja piirejä kutsutaan edelleen symmetrisiksi .
↑ Stinson, 2003 , s. 23, Lause 2.2.
↑ Ryser, 1963 , s. 102-104.
↑ 1 2 Hughes ja Piper, 1985 , s. 109.
↑ Hall, 1986 , s. 320-335.
↑ Assmus, Key, 1992 , s. 55.
↑ Martin, Singerman, 2008 , s. neljä.
↑ Salwach, Mezzaroba, 1978 .
↑ Kaski, Östergård, 2008 .
↑ Aschbacher, 1971 , s. 279-281.
↑ Stinson, 2003 , s. 74, Lause 4.5.
↑ Hughes ja Piper 1985 , s. 156, Lause 5.4.
↑ Hughes ja Piper 1985 , s. 158, seuraus 5.5.
↑ Beth, Jungnickel, Lenz, 1986 , s. 40 Esimerkki 5.8.
↑ Stinson, 2003 , s. 203, seuraus 9.6.
↑ Hughes ja Piper 1985 , s. 29.
↑ Cameron, van Lint, 1991 , s. 11, Ehdotus 1.34.
↑ Hughes ja Piper 1985 , s. 132, Lause 4.5.
↑ Cameron, van Lint, 1991 , s. 11, Lause 1.35.
↑ Colbourn, Dinitz, 2007 , s. 114, huomautukset 6.35.
↑ Street, Street, 1987 , s. 237.
↑ Street, Street, 1987 , s. 238.
↑ Street, Street, 1987 , s. 240, Lemma 4.
↑ Colbourn, Dinitz, 2007 , s. 562, huomautus 42.3(4).
↑ Street, Street, 1987 , s. 242.
↑ Tämä ei ole matemaattinen luokitus, koska yksi tyypeistä on "kaikki muu".
↑ Bose, Shimamoto, 1952 .
↑ Raghavarao, 1988 , s. 127.
↑ Noshad, Brandt-Pearce, 2012 , s. 968–971.

Kirjallisuus

Michael Aschbacher. Symmetristen lohkorakenteiden kollineaatioryhmistä // Journal of Combinatorial Theory, Series A. - 1971. - Vol. 11 , no. 3 . — S. 272–281 . - doi : 10.1016/0097-3165(71)90054-9 .
E. F. Assmus, J. D. Key. Mallit ja niiden koodit. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
Thomas Beth, Dieter Jungnickel, Hanfried Lenz. suunnitteluteoria. - Cambridge: Cambridge University Press , 1986. - ISBN 978-0-521-44432-3 .
RC Bose. Huomautus Fisherin epätasa-arvosta tasapainoisille epätäydellisille lohkomalleille // Annals of Mathematical Statistics . - 1949. - S. 619-620 .
RC Bose, T. Shimamoto. Osittain tasapainotettujen epätäydellisten lohkosuunnitelmien luokittelu ja analysointi kahdella liitännäisluokalla // Journal of the American Statistical Association. - 1952. - T. 47 . - S. 151-184 . - doi : 10.1080/01621459.1952.10501161 .
P. Cameron, JH van Lint. Suunnitelmat, kaaviot, koodit ja niiden linkit. - Cambridge University Press, 1991. - V. 22. - (London Mathematical Society Student Texts). - ISBN 978-0-521-41325-1 .
Charles J. Colbourn, Jeffrey H. Dinitz. Kombinatoristen mallien käsikirja. — Boca Raton: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
RA Fisher. Ongelman eri mahdollisten ratkaisujen tarkastelu epätäydellisissä lohkoissa // Annals of Eugenics . - 1940. - T. 10 . - S. 52-75 .
Marshall Hall Jr. kombinatorinen teoria. - New York: Wiley-Interscience, 1986. - ISBN 0-471-09138-3 .
D. R. Hughes, E. C. Piper. suunnittelun teoria . - Cambridge: Cambridge University Press, 1985. - ISBN 0-521-25754-9 .
Petteri Kaski, Patric Östergard. Kaksitasoa on täsmälleen viisi k = 11 // Journal of Combinatorial Designs. - 2008. - T. 16 , no. 2 . — S. 117–127 . - doi : 10.1002/jcd.20145 .
ES Lander. Symmetrinen mallit: Algebrallinen lähestymistapa. - Cambridge: Cambridge University Press, 1983.
CC Lindner, CA Rodger. Suunnittelun teoria . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
Damaraju Ragharao. Konstruktiot ja kombinatoriset ongelmat kokeiden suunnittelussa . – New York: Dover, 1988.
Damaraju Raghavarao, L.V. Padgett. Lohkomallit: analyysi, kombinatoriikka ja sovellukset. – World Scientific, 2005.
Herbert John Ryser. Kombinatorinen matematiikka (Carus Monograph #14). - Mathematical Association of America, 1963.
Chester J. Salwach, Joseph A. Mezzaroba. Neljä kaksitasoa, joissa k = 9 // Journal of Combinatorial Theory, Series A. - 1978. - V. 24 , no. 2 . - S. 141-145 . - doi : 10.1016/0097-3165(78)90002-X .
SS Shrikhande, Bhat-Nayak Vasanti N. Joidenkin tasapainotettujen epätäydellisten lohkosuunnitelmien ei-isomorfiset ratkaisut I // Journal of Combinatorial Theory . – 1970.
Douglas R. Stinson. Kombinatoriset mallit: rakenteet ja analyysi. - New York: Springer, 2003. - ISBN 0-387-95487-2 .
Anne Penfold Street, Deborah J. Street. Kokeellisen suunnittelun kombinatoriikka. - Oxford UP [Clarendon], 1987. - s. 400+xiv. — ISBN 0-19-853256-3 .
JH van Lint, RMWilson. Kombinatorian kurssi . - Cambridge: Cambridge University Press, 1992.
Pablo Martin, David Singerman. Biplanesista Kleinin kvarticille ja Buckyballille . - 2008 - 17. huhtikuuta.
Mohammad Noshad, Maite Brandt-Pearce. Poistettu PPM käyttämällä symmetrisiä tasapainotettuja epätäydellisiä lohkomalleja // IEEE Communications Letters. - 2012. - Heinäkuu ( nide 16 , numero 7 ). - doi : 10.1109/LCOMM.2012.042512.120457 .
P. Dembowski. Äärilliset geometriat. - Springer, 1968.

Linkit

DesignTheory.Org : Kombinatoristen, tilastollisten ja kokeellisten lohkosuunnitelmien tietokannat. Ohjelmistot ja muut resurssit, joita ylläpitää Lontoon yliopiston Queen Mary Collegen matemaattisten tieteiden korkeakoulu.
Suunnitteluteoriaresurssit : Peter Cameronin web-pohjaisten suunnitteluteoriaresurssien sivu.
Weisstein , Eric W. Block Designs at Wolfram MathWorld .