覆蓋設計

覆蓋設計

覆蓋設計(covering design)是t設計的一種推廣,設X為v元集,B為X的某些k元子集的族,若X的任一t元子集至少包含在B的λ個成員(區組)中,則稱(X,B)為t-(v,k,λ)覆蓋設計,t-(v,k,λ)設計也是一個覆蓋設計。對給定的參數t,v,k,λ,使t-(v,k,λ)覆蓋設計存在的最小區組數稱為覆蓋數,記為Cλ(v,k,t)。哈拿匿(H.Hanani)證明:對每一正整數λ及v≥3有Cλ(v,3,2)=Bλ(v,3,2)+ε,其中,當λ(v-1)≡0(mod 2)且v≡λ≡2(mod 3)時ε=1,否則ε=0,米爾斯(W.H.Mills)等人對每一正整數λ及v≥4給出了覆蓋數Cλ(v,4,2)的確切值,當t≥3時,C1(v,4,3)=B1(v,4,3),其中v不恆等於7(mod 12)。

基本介紹

  • 中文名:覆蓋設計
  • 外文名:covering design
  • 所屬學科:數學(組合學)
  • 簡介:t設計的一種推廣
基本介紹,例題解析,相關定理,

基本介紹

定義 給定正整數t,v,k,λ,設X為一個v元集,B為由X的k元子集(稱為區組)所組成的子集族,若X的任意一個t元子集都至少包含在λ個區組中,則稱(X,B)為一個t-(v,k,λ)覆蓋設計(covering design)。令
Cλ(v,k,t)={min b|存在區組數為b的t-(v,k,λ)覆蓋設計},
Cλ(v,k,t)叫覆蓋數(covering number),若(X,B)是區組數為Cλ(v,k,t)的t-(v,k,λ)覆蓋設計,則叫做最小(或最優)t-(v,k,λ)覆蓋設計,通常將C1(v,k,t)簡記作C(v,k,t)。

例題解析

【例1】設X=Z10
A:{0,1,2,3},{0,4,5,6},{1,4,7,8},{2,5,7,9},{3,6,8,9},
B:{0,1,2,9},{0,3,4,8},{0,5,6,7},{1,2,3,4},{1,2,5,6},
{1,2,7,8},{3,4,5,6},{3,4,7,9},{5,6,8,9}.
則(X,A)是一個2-(10,4,1)填充設計,(X,B)是一個2-{10,4,1}覆蓋設計,設A'為A的任一子集,則(X,A')也是2-(10,4,1)填充設計。設B'為在B中添加X的若干4元子集而得,則(X,B')也是2-(10,4,1)覆蓋設計。
【例2】若t-(v,k,λ)設計存在,則它既是最大t-(v,k,λ)填充設計,又是最小t-(v,k,λ)覆蓋設計。
設x為實數,用[x]表示不超過x的最大整數,[x]為不小於x的最小整數,令
覆蓋設計
覆蓋設計
當λ=1時,將U1(v,k,t)記作U(v,k,t),將L1(v,k,t)記作L(v,k,t)。

相關定理

關於填充數Pλ(v,k,t)的上界和覆蓋數Cλ(v,k,t)的下界。我們有如下結果。
定理1(Schönheim界)
證明顯然有
即當t=1時結論成立,今設t≥2,(X,A)為一個t-(v,k,λ)填充設計。對任意x∈X,A中包含x的全體區組去掉點x後作成X\{x}上的一個(t-1)-(v-1,k-1,λ)填充設計,因此其區組數≤Pλ(v-1,k-1,t-1)。因此有
,從而由式(3)及歸納法即得式(1),同理可得
由式(4)及歸納法得式(2),從而即得結論。
當t=2時,H.Hanani進一步證明了以下結論。
定理2設λ(v-1)≡0(mod(k-1))。
(i)若λv(v-1)/(k-1)≡1(mod k),則
(ii)若λv(v-1)/(k-1)+1≡0(mod k),則

相關詞條

熱門詞條

聯絡我們