-
覆蓋設計
鎖定
覆蓋設計(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)。
[1]
- 中文名
- 覆蓋設計
- 外文名
- 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)。
[2]
覆蓋設計例題解析
【例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)覆蓋設計。
設x為實數，用[x]表示不超過x的最大整數，[x]為不小於x的最小整數，令
當λ=1時，將U1(v，k，t)記作U(v，k，t)，將L1(v，k，t)記作L(v，k，t)。
覆蓋設計相關定理
定理1(Schönheim界)
證明顯然有
定理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)，則
