區(qū)塊設(shè)計之理論

1、第一章區(qū)塊設(shè)計之介紹§1.1 區(qū)塊設(shè)計之理論組合設(shè)計是從一個有限集合中，選取出子集所成之集合，而此集合之元素滿足某些條件。若此子集含k 個元素，我們稱此為k 子集，在設(shè)計理論上稱之為區(qū)塊。為方便起見，我們將集合 a,b,c 記為 abc，其它之集合亦同。如果 x B，則我們稱元素 x 在區(qū)塊 B 中，或稱區(qū)塊 B 中包含有元素 x。以下我們介紹二個簡單的設(shè)計。問題 1.1：設(shè) V = 1,2,3,4 ，求一個 V 中 2 子集之集合 D，使得 V 中任 2 個元素恰好落在唯一的區(qū)塊中？答案：D = 12,13,14,23,24,34問題 1.2：設(shè) V = 1,2,3,4,5,6,7

2、 ，求一個 V 中 3 子集之集合 D，使得每個元素出現(xiàn) 3 次，並且任兩個區(qū)塊的交集只有 1 個元素？答案： 123,145,167,245,267,346,357設(shè) V 為 v 個元素之集合 。一個在集合 V 上的區(qū)塊設(shè)計是 V 中 k 子集 (稱之為區(qū)塊 )所成之集合 D，且滿足 V 中每個元素出現(xiàn)在 r 個區(qū)塊中（即每個元素出現(xiàn)r 次）。為了方便，此區(qū)塊設(shè)計之區(qū)塊個數(shù)，我們用b 表示之，且稱此設(shè)計 (V, D)為 (v,b,r,k)區(qū)塊設(shè)計。定理 1.3：在任一個 (v,b,r,k)區(qū)塊設(shè)計中， vr = bk。証明：在 (v,b,r,k)區(qū)塊設(shè)計 D 上，有 v 個元素，每元素出現(xiàn)

3、r 次，顯然此集合 D 共出現(xiàn) vr 個元素，但從另一角度來看， D 中共有 b 個區(qū)塊，且每個區(qū)塊中均有 k 個元素，顯然此集合共出現(xiàn) bk 個元素。綜合上述二個觀察，我們得到 vr = bk。在集合 S = 1,2,3 上的區(qū)塊設(shè)計有下列數(shù)種， D1 = 123, D 2 = 123,123, D 3= 123,123,123, 。不過這些設(shè)計上的區(qū)塊就是集合 S 本身，且重覆選取此區(qū)塊，雖然它也是某種區(qū)塊設(shè)計，但我們對它較不感興趣。因此我們定義所謂不完全設(shè)計。一個區(qū)塊設(shè)計是不完全設(shè)計，如果區(qū)塊大小小於所有的元素，也就是k<v。若 k = v，則稱其為完全設(shè)計。對於任意在S 中的 x

4、, y 元素，x,y 是指同時包含有x, y 的區(qū)塊之個數(shù)，我們稱之為x 與 y 之共價數(shù)。例如：對於組合設(shè)計D =123,456,712,345,671,234,567，1,2= 2，即同時出現(xiàn)1 與2 之區(qū)塊個數(shù)有2 個123 與712，其他1,3= 1,1,4 = 0, .，亦同。定義 1.4：若一個不完全區(qū)塊設(shè)計，如果對在集合S 中任取二個元素x 與 y，其共價數(shù)為一常數(shù)，則稱其為平衡不完全區(qū)塊設(shè)計 ，簡稱 BIBD (balance incompleteblock design)，亦稱 (v, b, r, k,)-設(shè)計。例 1.5 (7,7,3,3,1)-設(shè)計： 124, 235,

5、346, 457, 561, 672, 713。(7,7,4,4,2)-設(shè)計： 1234, 1256, 1357, 1467, 2367, 2457, 3456(6,10,5,3,2)-設(shè)計： 123, 124, 135, 146, 156, 236, 245, 256, 345, 346如果= 0（也就是同時出現(xiàn)兩元素之區(qū)塊個數(shù)為零），換句話說，即是在任一區(qū)塊中根本就沒有超過兩個元素的，這時區(qū)塊只有1 個元素，亦即k 1。例如在集合S = 1,2,3 上 , 若=0，顯而易見的是區(qū)塊設(shè)計D=1,2,3,1,2,3,1,2,3,1,2,3,.。在這種結(jié)果下產(chǎn)生的區(qū)塊設(shè)計，我們並沒有太大的興趣，

6、因此我們均設(shè)>0。給一 (v, b, r, k,)-設(shè)計 (V,D)，它的對偶設(shè)計的定義如下：集合S 為 V中所有2 子集所成之集合 ，(集合 S 共有 v(v 1) 個元素 )，它的區(qū)塊是 xy | xB, yB, x2y ，其中 B D。所以，此設(shè)計 (V,D)的對偶設(shè)計之區(qū)塊個數(shù)亦為b 個。新設(shè)計中每個元素均落入個新區(qū)塊，且新的區(qū)塊之大小為k(k 1) 個元素。2例 1.6：求(4,4,3,3,2)-設(shè)計之對偶設(shè)計 ，其中 (4,4,3,3,2)-設(shè)計為 123,124,134,234。解：其對偶設(shè)計考慮在集合 S = 12,13,14,23,24,34上，而新的區(qū)塊將原區(qū)塊 12

7、3換成 12,13,23 ，124 換成 12,14,24 ，134 換成 13,14,34 ，234 換成 23,24,34。則其對偶設(shè)計為 (6,4,2,3)區(qū)塊設(shè)計：12,13,23,12,14,24,13,14,34,23,24,34但此設(shè)計並不是平衡不完全設(shè)計。因為 12,34 0，但 12,131。定理 1.7： (v, b, r, k,)- 設(shè)計之對偶設(shè)計是一種區(qū)塊設(shè)計，其所考慮之集合是v(v 1) 個元素，共有 b 個區(qū)塊，每個元素落在個區(qū)塊，而區(qū)塊所含的元素個數(shù)2為 k(k 1) 。2定理 1.8：對於任一個 (v, b, r, k, )-設(shè)計，則有(v-1) = r(k-1

8、) 之關(guān)係式。證明：由前述定理知道 (v, b, r, k,)-設(shè)計之對偶設(shè)計為 (v , b , r ),-設(shè)k計，,其中 v=v(v 1) ， b= b，r=，k= k (k 1) 。22v r= b k .(1)v(v1)bk (k1).(2)22vr = b k(2)v(v1)bk(k 1) = vr(k 1)222(v-1) = r(k-1)(v, b, r, k,)-vr = bk(v-1)=r(k-1)5v, b, r, k,(v, b, r, k,)-(v, k,)-vkbr平衡不完全區(qū)塊設(shè)計的基本定理：vt1 t2tvbB1 B2 .BbvbAA i , j1if ti B

9、jai , jotherwise0A(7,7,3,3,1)-124235 346 4575616727131000101110001001100011011000010110000101100001011。又如 (7,7,4,4,2)-設(shè)計： 1234 ， 1256， 1357， 1467， 2367，2457，3456 ，其關(guān)聯(lián)矩陣為1111000110011010101011001011011001101011010011110從矩陣 A 的定義，知道每一列 ”1”的個數(shù)為 r （元素重複數(shù)），而每一行 ”1” 的個數(shù)為 k（區(qū)塊內(nèi)所含之元素個數(shù)） 。設(shè) J 為每個位置均為 1 之矩陣，而

10、 I n 為 n 階單位矩陣。設(shè)區(qū)塊設(shè)計的 v b 階關(guān)聯(lián)矩陣為A ，則有Jv A = k Jv b和A Jb = r Jv b。（說明：其為顯然，因為矩陣A 之每一列 ”1”之個數(shù)為 r，而每一行的 ”1”之個數(shù)為 k，由線性代數(shù)矩陣運算即可得上式。）反過來說，任給一個佈於 0,1 上的 v b 階矩陣 A，若其滿是上面兩個等式，則其必為某一區(qū)塊設(shè)計的關(guān)聯(lián)矩陣。定理 1.9：如果 A 是(v,b,r,k, )-設(shè)計之關(guān)聯(lián)矩陣，則有下列二恆等式 AA T = (r- )I v + Jv和Jv A = k Jv b反之，若存在一個佈於 0,1 上的 vb 階矩陣 A ，滿是上面兩個等式k<

11、v，則 A必為某一 (v,b,r,k, )-設(shè)計的關(guān)聯(lián)矩陣。ij= A(i)B(j),其中 A(i)(j)表列矩陣 B 之第 j證明：已知 (AB),表示矩陣 A 之第 i 列， B行。所以r ifij(AA T )ij = A(i) (A T )(j) = A(i) A(j) =ijif因此，rAA T=r= (r- )I v + Jvr反之，若存在一個佈於 0,1 上的 v b 階矩陣 A，滿是二兩等式AA T = (r- )I v+Jv 與 Jv A = k Jv b，我們定義子集 B1, B2, Bb 如下i Bj 若且為若 aij = 1。則此區(qū)塊設(shè)計為一個 (v,b,r,k, )-

12、設(shè)計，其關(guān)聯(lián)矩陣為 A 。r由上面定理之証明得知TrAA =，而此方陣之行列式值我們r可經(jīng)由一些矩陣的基本運算求得：rdet(AA T) = detrrrrrrrr00= det0r0=00r( 1)000r vr00det0r000r= (r -)v-1 r + (v-1) 1.10bvdet(AA T) = (r -)v-1r + (v-1).(1)(v-1) = r(k-1)(1)det(AA T) = (r - )v-1r + r(k-1) = (r - )v-1rk(v-1) = r(k-1)k < vr >r-> 0det(AA T) > 0AA Tv =

13、rank(AA T)rank(A)minv,bb vA0,1v bJv A = k Jv b A Jb = r Jv b A Jv A = k Jv b A Jb = r Jv b Jb A T = r Jb v A T Jv = k Jb vAT(v,b,r,k)-v= bb= vr= kk= rb B1, B2, , Bb v t1, t2, , tv v C1, C2, , Cv b u1, u2, , ubuiCjtjBi1.11(6,4,2,3)-123,145,246,356A110010101001011001010011A T11100010011001010100101112

14、,13,14,23,24,34v = 4, b = 6, r = 3, k = 2(v,b,r,k)-(b,v,k,r)-(vr =bkk<vr<b(b, v, k, r)-r<b)BIBDBIBD(BIBDb v)1.12(v,b,r,k, )-BIBDv = b“ ” v b b > v v b BIBD“ ”：若 v = b，因為 vr = b k，所以得到 r = k。現(xiàn)在只需證明 JA T = kJ 和 A T A= (k- )I +J 即可。(1) 已知 JA = k J 和 AJ = r J。因為 r = k，所以可得到JA = k J-(1)和AJ = k J-(2)將 (2)式做轉(zhuǎn)置動作，則 (AJ )T= JAT = k J，故得證。(2) 已知 AA T = (k- )I +J 並且 det(AA T) > 0，因為 det(AA T) = det(A)det(A T)0則 det(A)0，所以 A 為非奇異的，即A 有反矩陣，因此AJ = kJ , J = kA-1J ,A-1 J = k-1J。T-1T-1利用 AA= A (AA )A = A (k- )I +JA則 A TA = A-1 (k- )I A +