【正文】 keyword: BIBD， Rotational RBIBD ,Optimal kcirculant design 南通大學畢業(yè)論文 XVIII 目 錄 摘 要 .............................................. XVI ABSTRACT ............................................. XVII 第一節(jié) 引言 ............................................. 1 第二節(jié) 轉(zhuǎn)動可分解設計的構(gòu)造 .............................. 3 第三節(jié) 轉(zhuǎn)動可分解設計的應用 ............................. 10 第四節(jié) 結(jié)束語 .......................................... 16 參考文獻 ............................................... 17 致 謝 ............................................... 18 南通大學畢業(yè)論文 1 第一節(jié) 引言 一個區(qū)組設計 )λ,( kvB 是一個二序組 ),( ΒX ，其中 X 為一個 有限集， Β 為 X 的一個子集族， Β 的元素稱為 區(qū)組 .進一步，設 v 與 ? 為給定的正整數(shù)， k 是給定的正整數(shù)，若區(qū)組設計 ),( ΒX 滿足： (i) vX? ； (ii)對任意 Β?B ，都有 kB? ； (iii)X 中任意一對不同的點都恰好同時包含在 ? 個區(qū)組中，當 2??kv 時，則稱為 平衡不完全區(qū)組設計 ，記為BIBDkv ?),( λ . 易知， BIBDkv ?),( λ 的必要條件是??? ??? ??? )).1(( m od0)1( )),1( m od (0)1( kkvv kv?? （ 1） 當 53 ??k 時，平衡不完全區(qū)組設計的存在性由 Hanani[6]在 1975 年證明 . 若 ),( ΒX 是一區(qū)組設計， Β?p ，若 p 構(gòu)成 X 的一個劃分，則稱 p 為此設計的一個 平行類 .如果區(qū)組 Β 能被劃分成平行類，則稱此設計為 可分解 的 .如果一個 BIBDkv ?),( λ 是可分解的，則稱為 可分解平衡不完全區(qū)組設計 ，記為 RBIBDkv ?),( λ [12]. 易知， RBIBDkv ?),( λ 存在的必要條件為??? ??? ? )).1( m od (0)1( ),( m od0 kv kv? （ 2） 3?k 時， RBIBDkv ?),( λ 的存在性主要依賴于 2,1?λ 的情形 . )1,3(),( ?λk 的存在性問題，也是歷史上著名的 Kirkman 女生問題，經(jīng)過一百多年的研究，于 1971 年由 RayChaudhuri和 Wilson[9]解決 .而 )2,3(),( ?λk 的情形由 Hanani[4]于 1974 年解決 . 4?k 時 ， RBIBDv ?),4,( λ 的存在性主要依賴于 3,1?λ 的情形 .1972 年， Hanani[13]等解決了1?λ 時的情形，即 RBIBDv ?)1,4,( 的存在性 .Baker 解決了 )3,4(),( ?λk 的情形，即RBIBDv ?)3,4,( 的存在性 .而 RBIBDv ?)1,5,( 的存在性問題在國內(nèi)外多位學者的共同努力下，已接近完整解決 . 對一般的 k ， RayChaudhuri 和 Wilson[14]和 Lu[10]證明了 RBIBDkv ?),( λ 的“漸近存在性” . 若 ),( ΒXD? 為 BIBDkkv ?? )1,( ，其中 ? }{1 ?? ?VZX ，令1)(α1)(α:α ??????????????vZiiiiXX ，南通大學畢業(yè)論文 2 ? 為 X 的映射， Β?B ， },...,{ 21 kaaaB ? ；令 )} ,(),...,(),({ 21 kaaaB ???? ? }|{ αα ΒΒ ?? BB ，若 ΒΒ ?α ，則稱 ? 為 D 的一個自同構(gòu) .此時 BIBDkkv ?? )1,( 稱為 Rotational 步， Β 在 ? 的作用下，產(chǎn)生軌道，軌道長度為 1?v .每個軌道中取一個代表，構(gòu)成 D 的一個基區(qū)組 .如果這個基區(qū)組構(gòu)成了 X 的一個劃分，即基區(qū)組是 D 的一個平行類，稱此平行類為 D 的基平行類 . 此時 )1,( ?kkv Rotational BIBD 是可分解的 . 稱其為)1,( ?kkv Rotational RBIBD. 例 設 ? }{14 ??ZX ，取基區(qū)組為 ),13,5,4(1 ?B )11,10,7(2 ?B , )8,3,1(3 ?B , )6,2,0(4 ?B , ),12,9(5 ??B ， 利用上面給出的定義，我們可以得到： 1B :)12,4,3()11,3,2()10,2,1()9,1,0()8,0,13()7,13,12()6,12,11()5,11,10()4,10,9()3,9,8()2,8,7()1,7,6()0,6,5()13,5,4( 2B :)10,9,6()9,8,5()8,7,4()7,6,3()6,5,2()5,4,1()4,3,0()3,2,13()2,1,12()1,0,11()0,13,10()13,12,9()12,11,8()11,10,7( 3B :)7,2,0()6,1,13()5,0,12()4,13,11()3,12,10()2,11,9()1,10,8()0,9,7()13,8,6()12,7,5()11,6,4()10,5,3()9,4,2()8,3,1( 4B :)5,1,13()4,0,12()3,13,11()2,12,10()1,11,9()0,10,8()13,9,7()12,8,6()11,7,5()10,6,4()9,5,3()8,4,2()7,3,1()6,2,0( 5B :),11,8(),10,7(),9,6(),8,5(),7,4(),6,3(),5,2(),4,1(),3,0(),2,13(),1,12(),0,11(),13,10(),12,9(?????????????? 此時，稱 )2,3,14( BIBD 為 )2,3,14( Rotational RBIBD. 本文主要介紹不同構(gòu)的轉(zhuǎn)動可分解的構(gòu)造及其應用，不同構(gòu)的轉(zhuǎn)動可分解設計能在統(tǒng)計試驗的超飽和設計中設計最優(yōu)的 k循環(huán)的超飽和設計，它廣泛應用于計算機試驗、軟件測試、醫(yī)藥、工業(yè)和生物工程試驗領域 . 在實際中，超飽和設計對于因子篩選試驗很有幫助．現(xiàn)有的超飽和設計的構(gòu)造方法主要是 針對兩水平和高水平情形的．但是實際中，混水平超飽和設計有著更廣泛的用途．本文對此部分不做研究 . 南通大學畢業(yè)論文 3 第二節(jié) 轉(zhuǎn)動可分解設計的構(gòu)造 這一節(jié)主要介紹 不同構(gòu)的轉(zhuǎn)動可分解設計的定義及其構(gòu)造方法，同時利用計算機編程計算出了一些不同構(gòu)的轉(zhuǎn)動可分解設計的例子 . 定義 設 }Β,...,Β,Β{ 21 t 為 vZ 的 子 集 族 ， 若 *0 λΔΒΔ vti i Z?? ??Β，其中???????? },|{ bababa 稱為 ? 的差 . tikZZ ivv ,...,1,},0{\* ???? 且 , 則稱 Β 為?),( ?kv 差族，記為 DF .特別地，當 1?t 時，稱其為差集，記為 DS . 例 在 7Z 中， }0{\}5,2,4,3,6,1{}3,2,1{ΔΒ} } ,3,1,0{Β{ 7Z????????Β ，稱 Β 為 DS?)1,3,7( . 有了差族的定義，下面我們利用差族的定義來給出 Rotational RBIBD 的構(gòu)造方法 . 構(gòu)造方法： 設 ? }},...,{{1/1},...,{ 100202021 ????????? ?kikiii aaaBkviaaaBΒ 為 ? }{1 ??VZ上的 kv/ 個 k 元子集族，其中 1?? vij Za ，令 },|{ ?????? baBbabaB ， ?ΒΒ ??B BΔΔ， 若}0{\)1( 1??? VZkΔΒ ， ?Β??B BX， }Ζi|{ v ??????? ΒΒ BiBd ev ，則 )},{( 1 Β? devZV ?? 為一個 R otat ion alkkv ?? )1,( RBIBD，其中 Β 為其平行類 . 證明 ：令 ?????? ?1,| VZiBiBd e v ΒΒ ，由 }0{\)1( 1??? vZkΔΒ ，有 ),)(( 1 ΒdevZv ? ?? 為Rotational Β 構(gòu)成 ),)(( 1 ΒdevZv ? ?? 的一個平行類 . Βdev 可以劃分為 1?v 個平行類 .所以 ),)(( 1 ΒdevZv ? ?? 為 Rotational RBIBD. 因為本節(jié)研究的是不同構(gòu)的轉(zhuǎn)動可分解設計，所以下面我們給出不同構(gòu)的概念 . 定義 設 ??? γ21111 . . .,( pppXD ??? ΒΒ ， ? ?? 39。 I 本 科 畢 業(yè) 論 文 題 目 轉(zhuǎn)動可分解設計的構(gòu)造及其應用 II 畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。 3. )3(mod0?v , 6?v ,且 )4(mod2?λ . 4?k 時 ， RBIBDv ?),4,( λ 的存在性主要依賴于 3?λ 的情形 .1972 年， Hanani 等解決了 1?λ時的情形，即 RBIBDv ?)1,4,( 的存在性 .Baker 解決了 (k,? )=(4,3)的情形，即 RBIBDv ?)3,4,( 的存在性 . 定理 4 ([8])當且僅當下列條件之一成立時， RBIBDv ?),4,( λ 存在 . 1. )12(mod4?v ,且 1,2(mod3)λ ? ； 2. )4(mod0?v ，且 0(mod3)λ? 。121 ??? pppppp ?，則 1D 與 2D 是同構(gòu)的 .若不存在這樣的 β ，則 1D 與 2D 是不同 構(gòu)的 . 以下是通過上面的構(gòu)造方法，同時利用計算機編程計算出了一些不同構(gòu)的轉(zhuǎn)動可分解設南通大學畢業(yè)論文 4 計的例子 . 引理 存在一對不同構(gòu)的 ?)3,4,16( Rotational RBIBD. 證明：根據(jù)上面的構(gòu)造方法，在 ? }{15 ?Z 上構(gòu)造基平行類，其基區(qū)組見下表： 序號 基區(qū)組 1 基區(qū)組 2 初始區(qū)組 (0,1,2,5) (0,2,3,7) (3,8,11,12) (1,4,8,13) (4,6,10,13) (5,9,10,11) (7,9,14,?) (6,12,14,?) 通過驗證，滿足不同構(gòu) .所以存在一對不同構(gòu)的 ?)3,4,16( Rotational RBIBD. 引理 存在一對不同構(gòu)的 ?)3,4,20( Rotational RBIBD. 證明：根據(jù)上面的構(gòu)造方法，在 ? }{19 ?Z 上構(gòu)造基平行類 .其基區(qū)組見下表： 序號 基區(qū)組 1 基區(qū)組 2 初始區(qū)組 (3,4,5,18) (6,10,12,16) (1,2,8,12) (5,9,14,17) (0,7,10,14) (0,2,11,18) (6,9,15,17) (1,3,4,15) (11,13,16， ?) (7,8,13,?) 通過驗證，滿足不