[科普中國]-威爾森基本構作法

威爾森基本構作法(Wilson's fundamental construction)是由若干已知可分組設計構作新的可分組設計的方法，該方法由威爾森(R.M.Wilson)提出，是構造可分組設計的一個基本方法。設(X，G，A)是一個可分組設計GDD[K，λ，M;v](稱為基本的GDD)，若有權函數(shù)w：x→Z+∪{0}，使對A中每一個區(qū)組A，均存在可分組設計GDDK，μ，{w(x)|x∈A};∑x∈Aw(x)(稱為輸入設計)，則存在一個可分組設計GDDK，λμ，∑x∈Gw(x)|G∈G;∑x∈Xw(x)。

基本介紹下述“Wilson基本構作法”(WFC)是構作可分組設計的最重要的遞歸方法。

定理1(Wilson)設D=(X，G，A)為一個(K0,λ)-GDD，定義X上的一個權函數(shù)w：X→Z+∪{0}，若對每一個區(qū)組B ∈A，都存在一個(K，μ)-GDD。其型為{w(x)|x∈B]，則存在一個(K，λμ)-GDD，其型為

定理1中的設計D叫主GDD(master GDD)。相應于B的型為 的(K,μ)-GDD叫做輸入設計(input design或ingredient),為應用wilson的基本構作法，需要選擇適當?shù)闹鱃DD與輸入設計。定理3的Hanani的“截短法”(truncation)，為我們提供了從一個橫截設計出發(fā)構作一系列GD設計的有效方法1。

威爾森基本構作法的證明證 設x∈X，作集合 ，使當x≠y時都有 ,令

對任意B∈A。在 上構作一個(K,1)-GDD,它的組的集合為 ,它的區(qū)組集記作BB，令1

B=BB．

對任意G∈G，令H(G)= ,再令

H={H(G)|G∈G].

則(Y,H,B)便是所求的型為 的(K， )-GDD。 L留E J

對給定正整數(shù)k≥3，令

Rk={r|存在B(k,1；(k-1)r+1))．

相關結論及概念作為定理1的一個簡單推論。我們證明集合Rk的PBD閉性1。

定理2(Hanani)設k≥3。則Rk是PBD閉集。

證 由定理1．4．1。B(k。1；u)的存在性等價7=GD(k。1。k一1；V一1)的存在性。因此

Rk=．[r I存在GD(k。1。k一1；(k一1)r))． (7．2．5)從而若能證明對任一u E B(Rk)。都有GD(k。1。k一1；(k一1)u)存在即得定理．

設K冬Rk。(X。B)為一個B(K。1；口)．對任意r E K都有GD(k。1。尼一1；(忽一1)r)存在．若令G={{z]．I z E x)。則(x。G。B)便是一個GD(K。1。1；u)．對任意z E X。都令叫@)=k一1．由于對每一個B E B都存在一個GD(七。1。忌一1；(尼一1)IBI)。因此由定理7．2．5便得到一個GD(k。1。k一1；(k一1)u)。從而u E Rk．即得定理1。

定理3 設m，k與s為正整數(shù)，k≥2，K= ．若TD(k+s,1；m)存在且 為滿足條件0≤gi≤m的整數(shù)i=1,2,…,s,則必須存在型為 的(K,1)-GDD。

證 設所給TD(k+s，1；m)的組為 對1≤i≤s,在Gk+i中去掉m-gi個點。再從原TD(k+s,1；m)的區(qū)組中也去掉這些點,如此便得到所要求的(K,1)-GDD。

下述定理給出由可分解設計構作GD設計的一個方法。

定理4 若RB(k，1；v)存在。則型為 的(k+1,1)-GDD存在。

證 若RB(k，1；v)存在。則它恰有r=(v-1)/(k一1)個平行類。每個平行類由v/k個區(qū)組組成,對1≤i≤r-1,在第i個平行類的每個區(qū)組添加一個點 之后仍作為區(qū)組,將第r個平行類中的各個區(qū)組當作組。再將 也當作組。如此便得到所求的(k+1,1)-GDD。

本詞條內容貢獻者為:

王海俠 - 副教授 - 南京理工大學