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