覆盖设计
t设计的推广
覆盖设计(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)。
基本介绍
定义 给定正整数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λ(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),则
参考资料
最新修订时间:2024-07-01 12:06
目录
概述
基本介绍
例题解析
参考资料