定义 给定正整数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)覆盖设计。

【例2】若t-(v,k,λ)设计存在,则它既是最大t-(v,k,λ)填充设计,又是最小t-(v,k,λ)覆盖设计[2] 。

设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)的下界。我们有如下结果[2] 。

定理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)。因此有

相关查询: 正整数 covering
最新查询:无苏打奶盐饼干 新田由佳 timpano 杀孽萝莉 princetonreview 地心引力 石田妮可 班禅额尔德尼 非本土 应运元宝 不论如何 1990年以来中国常用人口数据集 鶨ؿ˹ 公共汽车 山摇地动 深黄色 截面积 追随者 下关镇 烦躁不安 纯白色 天地盟主燕王 水电费 真兽亚纲 Breakbeats 甜晒虾皮拌香菜 辅导书 分配工作 公务人员 爱心沙拉草莓 魔兽金币 高容量 怪盗丽娅 有机性 indicate 大亚湾 公检法司 伏龙桥 旁若无人 依山傍水 不尽相同 前所未有 土家族 蝴蝶斯瑞沃 Reversal 德语区 三分之一 卡西尼 中央委员 塔吉克斯坦 双丰收 Middlesex 有所作为 狮子滩水电站 恶口果报 慧远研究 木村英一 孔雀东南飞 米诺斯文明 Beautiful 斯信强 外景地 中医药 高坂昌信 呛拌酸辣土豆丝 重病人 再保险 宗主权 气象系 治愈率 keil uvision2 布莱德·克洛宁 内外部 氧化汞 人事部 实地调查 寄生虫病 者之书 安吉·艾佛哈特 矩阵式
友情链接: 知道 电影 百科 好搜 问答 微信 值得买 巨便宜 天天特价 洛阳汽车脚垫 女装 女鞋 母婴 内衣 零食 美妆 汽车 油价 郑州 北京 上海 广州 深圳 杭州 南京 苏州 武汉 天津 重庆 成都 大连 宁波 济南 西安 石家庄 沈阳 南阳 临沂 邯郸 保定 温州 东莞 洛阳 周口 青岛 徐州 赣州 菏泽 泉州 长春 唐山 商丘 南通 盐城 驻马店 佛山 衡阳 沧州 福州 昆明 无锡 南昌 黄冈 遵义
© 2025 haodianxin 百科 豫ICP备14030218号-3 消耗时间:0.055秒 内存2.83MB