（应用数学专业论文）区组大小为3的最优循环填充.pdf

区组大小为3 的最优循环填充 摘要 摘要 ( t ，k ，文) 填充设计是指一个有序对( v 唇) ，其中y 是一个口元集合，b 是 y 中k 元子集( 称为区组) 的多重集合，满足y 中任意点对最多出现在a 个 区组中，记为p ( k ，a ；u ) 一个p ( k ，a ； ) ，( k 层) ，的自同构是一个双射砂：v y ，满足诱导映射 盯：召_ 召也是二一个双射。如果一个p ( k ，a ；v ) 具有一个长度为v 的单圈所构 成的自同构，那么它称为循环的当一个循环p ( k ，a ；u ) 不包含短轨道时，记 为c p ( k ，入；u ) 对于给定的u ，k ，a ，具有最大基区组数的循环p ( k ，a ； ) 称为最优的，并 称这个最大基区组数为循环填充数特别地，将c p ( k ，a ；v ) 的循环填充数记 为c d ( v ，k ，a ) 若在最优循环p ( k ，入；口) 中任意点对恰好出现在入个区组中， 则该设计也称为循环平衡不完全区组设计，记作c b ( k ，入；u ) e r n i ef b r i c k e l l 和v i c t o rk w e i 【7 】确定了当入= 1 时的循环填充数 c d ( v ，3 ，入) 对于入 l 的情形，m 。j c o l b o u r n 和c j c o l b o u r n 【2 0 1 确定 了c b ( 3 ，入；u ) 的存在性本文研究入 1 时最优c p ( 3 ，入；u ) 的存在性完全 确定了当a 1 ，k = 3 时的循环填充数c d ( v ，3 ，a ) ，即： c d ( v ，3 ，入) = 【华卜1 ， 【半j ， 当t j 三1 0 ( m o d1 2 ) 且a 三2 ( r o o d1 2 ) 时， 或当u 兰6 ，1 2 ( m o d2 4 ) 且a 兰5 ( r o o d1 2 ) 时， 或当 兰2 ( m o d4 ) 且a 三6 ( r o o d1 2 ) 时， 或当u 兰2 ( r o o d2 4 ) 且入三7 ( m o d1 2 ) 时， 或当u 三1 8 ( m o d2 4 ) 且入三1 1 ( r o o d1 2 ) 时， 其余情况 关键词：循环填充设计，差三角，最优性 作者：张晗 导师：王健敏( 副教授) o p t i m a lc y c l i cp a c k i n g sw i t hb l o c k s i z et h r e ea b s t r a c t o p t i m a lc y c l i cp a c k i n g sw i t hb l o c ks i z et h r e e a b s t r a c t l e tu ，k ，ab ep o s i t i v ei n t e g e r sa n d 移七a ( u ，七，入) 一p a c k i n gi sap a i r ( v8 ) ， w h e r evi sav - s e to fe l e m e n t s ( p o i n t s ) a n d 召i sac o l l e c t i o no fk - s u b s e t so fv ( b l o c k s ) ， s u c ht h a te v e r yp a i ro fp o i n t so c c u r si na tm o s t 入b l o c k si n 召，d e n o t e db yc p ( k ，入；u ) a na u t o m o r p h i s mo fap ( k ，a ； ) ，( v 层) ，i sab i j e z t i o n 砂：v v ，s u c ht a h tt h e i n d u c e dm a p p i n g 盯：召_ 峥bi sa l s oab i j e c t i o n ap ( k ，入；u ) i s c y c l i ci f i ta d m i t sa c y c l i ca u t o m o r p h i s mg r o u po fo r d e rut h a ti ss p a n n e db yau c y c l e ac y c l i cp ( k ，a ；u ) h a v i n go n l yf u l lb l o c ko r b i t si sd e n o t e db yc p ( k ，a ；可) a c y c l i cp ( k ，入；口) i ss a i dt ob eo p t i m a li fi th a sm a x i m u mp o s s i b l en u m b e ro fb a s e b l o c k s ，w h i c hi sc a l l e dc y c l i cp a c k i n gn u m b e r i np a r t i c u l a r ，t h ec y c l i cp a c k i n gn u m b e r o fc p ( k ，入；u ) i sd e n o t e db yc d ( v ，七，入) 。i fe v e r yp a i ro fp o i n t so c c u r si ne x a c t l y 入 b l o c k s ，t h ed e s i g ni sr e f e r r e dt oa sac y c l i cb a l a n c e di n c o m p l e t eb l o c kd e s i g n ，d e n o t e d b yc b ( k ，a ；t ，) e r n i ef b r i c k e l la n dv i c t o rk w e i 7 】h a v ed e t e r m i n e dt h ec y c l i cp a c k i n gn u m - b e r sc d ( v ，3 ，1 ) f o r 入 1 ，m j c o l b o u r na n dc j c o l b o u r n 【2 0 】h a v ed e t e r m i n e d t h ee x i s t e n c eo fac b ( 3 ，入；口) i nt h i sp a p e r ，w er e s e a r c ht h ee x i s t e n c eo fo p t i m a l c p ( 3 ，入； ) w i t ha 1 ，a n dd e t e r m i n et h ec y c l i cp a c k i n gc d ( v ，3 ，a ) ，i e ， f 【掣卜l ，i fv 三1 0 ( m o d1 2 ) a n da 三2 ( r o o d1 2 ) ， c d ( v ，3 ，入) = o ri f 兰6 ，1 2 ( r o o d2 4 ) a n d 入墨5 ( m o d1 2 ) ， o ri fu 三2 ( r o o d4 ) a n d 入三6 ( r o o d1 2 ) ， o ri fu 三2 ( r o o d2 4 ) a n d 入三7 ( m o d1 2 ) ， o ri fu 三1 8 ( m o d2 4 ) a n d 入三1 1 ( r o o d1 2 ) ， 【掣j ， o t h e r w i s e k e y w o r d s ：c y c l i cp a c k i n gd e s i g n ，d i f f e r e n c et r i p l e ，o p t i m a l i i w r i t t e nb yz h a n gh a n s u p e r v i s e db yp r o f w a n gj i a n m i n 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学或其它教 育机构的学位证书而使用过的材料对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人承担本声明的法律责任 研究生签名： 主丝堕日期：鱼里l 羔 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合 作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文 档的内容和纸质论文的内容相一致除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布 ( 包括刊登) 授权苏州大学学位办办理。 研究生签名：乏丝堕日期：翟怛 导师签名：蜥日期：率3 区组大小为3 的最优循环填充一引言 1 1 定义 一引言 ( ，七，入) 填充设计是指一个有序对( v 召) ，其中y 是一个u 元集合，召是 y 中k 元子集( 称为区组) 的多重集合，满足y 中任意点对最多出现在a 个 区组中，记为pc k ，a ；u ) ，对于给定的u ，k ，a ，具有最大基区组数的p ( k ，h ) 称 为最优的 一个p ( k ，入；u ) ，( v 日) ，的自同构是一个双射妒：v _ y ，满足诱导映 射盯：b _ 召也是一个双射，其中对任意的b = 6 ”b k ) b ，o ( b ) = 【妒( b ，) ，砂( a 。) ，妒( 6 。) ) 如果一个p ( k ，h u ) ，( v 召) ，具有一个长度为v 的单圈构 成的自同构，那么它称为循环的因此它的点集y 和自同构群跟加法群磊 是等价的 设b = 6 l ，k ) 是循环p ( k ，a ；u ) ，( v 召) ，的一个区组，令b + 江( b l + l 。，b k + i ) ，其中所有的加法都是在磊中进行的我们称 扫+ i l i 磊) 是b 所在的区组轨道( o r b i t ) 记为c l ( b ) 若i c l ( b ) i = 口，则称这个区组轨道是长 的，否则称为短的若一个循环p ( k ，a ；u ) 不包含短轨道，则记为o p ( k ，a ； ) 设b 是一个循环p ( k ，入；u ) 的区组集，s 是召的一个多重子集，若多重 集【c l ( s ) l s s ) = b ，则称s 是循环p ( k ，a ；u ) 的一个基区组集 对于给定的u ，七，a ，具有最大基区组数的循环p ( k ，a ；u ) 称为最优的，并 称这个最大基区组数为循环填充数特别地，将c p ( k ，入；u ) 的循环填充数记 为c d ( v ，七，入) 1 2 研究背景 有关填充设计的问题很多学者已经做了大量的工作，h a n a n i 【1 2 】确定 了最优p ( 3 ，a ；v ) 的存在性b r o u w e r 【2 】ib i l l i n g t o n 【8 】s t a n t o n 【8 】，s t i n s o n 【8 】i 区组大小为3 的最优循环填充 一引言 h a n a n i 【1 3 】和s c h 6 n h e i m 【1 7 j 等人解决了最优p ( 4 ，a ；u ) 的存在性问题虽然 等人对k = 5 的情形做了很多工作，但是最优p ( 5 ，入；v ) 的存在性至今没有解 决 循环填充与光正交码关系密切，正如文献 7 】指出最优c p ( k ，1 ；v ) 等价 一个最优u ，k ，p - 光正交码 v i c t o rk w e i 和e r n i ef b r i c k e l l 【7 】确定了最优 c p ( 3 ，1 ；口) 的存在性 确定最优c p ( k ，1 ；v ) 的存在性是一个比较困难的问题尽管很多学者做 了大量的工作，对于七4 的最优c p ( k ，l ；u ) 的存在性至今没有解决 当a 1 时，m j c o l b o u r n 和c j c o l b o u r n 【2 0 】确定了c b ( 3 ，入；u ) 的存 在性，其结论可叙述成如下定理： 定理1 1 【2 0 】设整数u 3 ，一个c b ( 3 ，入；u ) 存在的必要条件，即： ( 1 ) 入三1 ，5 ，7 ，l l ( m o d1 2 ) 且u 三1 ，3 ( m o d6 ) ； ( 2 ) 入兰2 ，1 0 ( r o o d1 2 ) 且u 兰0 ，1 ，3 ，4 ，7 ，9 ( m o d1 2 ) ； ( 3 ) a 三3 ，9 ( r o o d1 2 ) 且u 三l ( m o d1 2 ) ； ( 4 ) 入三4 ，8 ( m o d1 2 ) 且u 兰0 ，l ( m o d3 ) ； ( 5 ) a 三6 ( m o d1 2 ) 且u 三0 ，l ，3 ( m o d4 ) ； ( 6 ) 入三0 ( r o o d1 2 ) 且口3 这个条件也是充分的，除了两个例外： ( ，入) g _ ( 9 ，1 ) ，( 9 ，2 ) ) 1 3 研究问题和主要结论 本文研究入 l 的最优c p ( 3 ，a ；v ) 的存在性问题v 个点可以产生 芈个点对，每个区组需要用掉地2 型个点对，故有【蚩2 j 个区组，由 于v p ( 3 ，a ；u ) 只包含长轨道，故它最多包含【罢j 个基区组因此，我们 有下述定引理 2 区组大小为3 的最优循环填充 一引言 引理1 2 设u ，入为正整数，则有c d ( v ，3 ，入) 【半产j 定理1 1 已经提供部分结果，其中若c b ( 3 ，h ) 不包含短轨道，则它就 是一个最优c p ( 3 ，a ；口) ；若c b ( 3 ，a ； ) 有短轨道，根据m j c o l b o u r n 和c j c o l b o u r n 2 0 】的构作可知，仅有一个短轨道删除在此短轨道中的基区组， 就能产生一个最优c p ( 3 ，a ； ) 由此可得到如下引理 引理1 3 当a 与 满足下列条件之一 ( 1 ) 入兰l ，5 ，7 ，l l ( m o d1 2 ) 且u 三1 ，3 ( m o d6 ) ； ( 2 ) 入兰2 ，l o ( m o d1 2 ) 且u 兰0 ，1 ，3 ，4 ，7 ，9 ( m o d1 2 ) ； ( 3 ) 入三3 ，9 ( m o d1 2 ) 且u 三l ( m o d1 2 ) ； ( 4 ) 入三4 ，8 ( r o o d1 2 ) 且u 三0 ，l ( m o d3 ) ； ( 5 ) a 三6 ( r o o d1 2 ) 且t ，兰0 ，l ，3 ( m o d4 ) ； ( 6 ) a 三o ( m o d1 2 ) 且t ，3 时，除了两个例外：( u ，a ) g ( ( 9 ，1 ) ，( 9 ，2 ) ，有c d ( v ，3 ，入) = 【堑j 本文的主要结论以下面定理的形式给出： 定理1 4 g d a ( u ，a ) = 当u = 1 0 且a 兰2 ( r o o d1 2 ) 时， 或当u 兰6 ，1 2 ( r o o d2 4 ) 且a 兰5 ( r o o d1 2 ) 时， 或当 兰2 ( r o o d4 ) 且a 三6 ( r o o d1 2 ) 时， 或当t j 兰2 ( r o o d2 4 ) 且a 三7 ( m o d1 2 ) 时， 或当u 三1 8 ( r o o d2 4 ) 且a 三1 1 ( m o d1 2 ) 时， 其余情况 3 区组大小为3 的最优循环填充 二 预备知识 二 预备知识 为了给出本文的主要结果，我们需要介绍一些相关的定义和预备知识 在一个循环p ( k ，a ； ) 中，对任意口磊 o ) ，记a o 为基区组使用差a 的 次数，称重集d l ( v ，后，a ) = 以。l a 毛) 为此循环填充设计的差剩余，其中 以。表示d l ( v ，k ，入) 包含a a 口个a 设s = ( 口，b ，c ) 是循环p ( k ，a ； ) ，( k 召) 的任意一个基区组集，我们称 m i n ( a b ，6 一n ) ，m i n ( a c ，c n ) ，m i n ( b c ，c 一6 ) ) 为基区组s 的差三角显然，若_ 【z ，y ，z ) 是一个差三角，则z ，y ，z 都是不超过詈的正整数，三者的关系为茁+ y = z 或。+ y + z = u 当z + y = z 时差三角对应的一个基区组为 o ，z ，z ) 当 zq - y + z = u 时，差三角 z ，y ，z ) 对应的一个基区组为 o ，z ，u z ) 早在1 8 9 7 年，h e f f t e r 【1 9 】提出了两个差问题，本文推广了h e f f t e r 的差问题，构作一个 最优c p ( k ，a ；u ) 等价于在重集 o a l l o 墨) 上构造尽可能多的差三角，使 得每个满足1 口詈的口至多出现a 次，并且当u 为偶数时，a = ；至多 出现嘲次与一个最优c p ( k ，入；u ) 对应的差三角集记为芦( 御，七，入) 由于一个区组( a ，b ，c ) ，不论a ，b ，c 的奇偶性如何 士( 口_ 6 ) ，士( n c ) ，士( 6 一c ) ) 中的奇数的个数为0 或4 ，即构作一个最优c p ( k ，a ；u ) 对应的差三角集时所 用的奇差个数必为4 的倍数所以对于某些u 和入，循环填充数c d ( v ，3 ，入) 达 不到引理1 2 中的上界，通过分析我们有一下引理： 引理2 1 若u 兰1 0 ( m o d1 2 ) 且入= 2 ，或者u 三2 ( m o d4 ) 且入= 6 ，则 c d ( v ，3 ，入) = 【学j - 1 证明：当 三1 0 ( m o d1 2 ) 且a = 2 时，令 = 1 2 m + 1 0 ，m 0 由引理 1 2 ，c d ( 1 2 mq - - 1 0 ，3 ，2 ) 【型号产业j _ 型号产丑= 4 m + 3 即若区组个数为4 m + 3 则差要全部用完奇差个数为( 6 m + 5 ) 2 = 1 2 m + 1 0 ，不是4 的倍数，矛盾故 c d ( 1 2 mq - 1 0 ，3 ，2 ) = l 2 ( 1 2 m + 6 1 0 - 1 ) j l 一1 = 4 m + 2 当u 三2 ( r o o d4 ) 且a = 6 时的情 形与之类似 4 口 区组大小为3 的最优循环填充 二 预备知识 引理2 2 若”三6 ，1 2 ( r o o d2 4 ) 且a = 5 ，u 兰2 ( r o o d2 4 ) 且入= 7 ，或者 兰 1 8 ( r o o d2 4 ) 且a = 1 1 ，则c d ( v ，3 ，入) = 【掣卜1 证明：当u 三6 ( m o d2 4 ) 且a = 5 时，令t ，= 2 4 m + 6 ，m 0 由引理1 2 ，c d ( 2 4 m + 6 ，3 ，5 ) 【业尘譬业j - 韭纽等丝盥= 2 0 m + 4 ，若区组个数为2 4 m + 6 ，则有一个差 没有用，只可能是半差1 2 m + 3 ，奇差个数为( 1 2 m + 3 ) 5 1 = 6 0 m + 1 4 ，不是4 的 倍数，矛盾故c d ( 2 4 m + 6 ，3 ，5 ) = 【生掣j 一1 = 2 0 m + 3 当 兰1 2 ( r o o d2 4 ) 且a = 5 ，u 三2 ( r o o d 2 4 ) 且入= 7 ，或者u 兰1 8 ( m o d2 4 ) 且入= 1 1 时的情形与 之类似 最后，我们还需要一下简单递推构作： 口 c d ( v ，3 ，1 2 m ) + c d ( v ，3 ，入) = c d ( v ，3 ，1 2 m + a ) ，其中1 入 0 ， 因为c d ( 1 2 m + 2 ，3 ，2 ) = 【坐掣j _ 4 m ，当m 2 时考虑下面的差三角五2 m + 2 ，3 ，2 ) ： ( 2 m - 2 r - 2 ，2 m + r + 2 ，4 m - r ) o r m 一2 ；( 2 m - 2 r - 1 ，4 m + r + 2 ，6 l n - r + 1 ) o _ r _ m - 1 ( 2 m - 2 r - 1 ，2 m + r ，4 i n r - 1 ) o r m - 1 ；( 2 m + 2 ，4 m + r + 2 ，6 m - r ) 0 一 r 一 0 ，c d ( 1 2 m + 8 ，3 ，2 ) = 【呈【丝掣j = 4 m + 2 ，当m 1 时考虑下面的差三角集五1 2 卅8 3 ，2 ) ： ( 2 m - 2 r ，2 m + r + 2 ，4 m r + 2 ) 0 r m - 1 ；( 2 m - 2 r - 1 ，4 r e + r + 5 ，6 i n r + 4 ) 0 一 r 一 m - 1 ( 2 m - 2 r - 1 ，2 m + r + l ，4 m - r ) o 一 r 一m l ；( 2 m - 2 r ，4 m + r + 3 ，6 卜r + 3 ) o r l 时考虑下面的差三角五1 2 m + 1 1 ，3 ，2 ) ： ( 2 m - 2 r ，2 r e + r + 3 ，4 l _ r + 3 ) o r m - 1 ；( 2 m 一2 r + l ，4 m + r + 4 ，6 m r + 5 ) o r m ( 2 i i 卜2 r + 1 ，2 m + r + 3 ，4 卜r + 4 ) o r m ；( 2 m - 2 r ，4 m + r + 5 ，6 m - r + 5 ) o 一 1 时考虑下面的差三角五- ：m ，3 s ) ： ( 2 m - 2 r - 2 ，2 m + r + l ，4 m r - 1 ) o r m 2 ；( 2 m - 2 r - 1 ，2 m + r + l ，6 m - r ) 0 一 r 一 m - 1 ( 2 m - 2 r - 1 ，2 m + r ，4 m - r - 1 ) 0 一 r 一 m - 1 采取两次； ( 2 m - 2 r - 2 ，4 m + r + l ，6 m _ r - 1 ) 0 一 r 一m - 2 采取两次 ( 2 m ，3 m ，5 m ) ( 4 m ，4 m ，4 m ) 五1 2 m ，3 ，3 ) 对应一个最优c p ( 3 ，3 ；1 2 m ) ，d l ( 1 2 m ，3 ，3 ) = ( 5 m ，6 m ，7 m 当m = l 时，u = 1 2 ，c d ( 1 2 ，3 ，3 ) = 5 ，曩1 2 3 3 ) 为： ( 2 ，4 ，6 ) ，( 1 ，3 ，4 ) ，( 2 ，3 ，5 ) ，( 2 ，3 ，5 ) ，( 1 ，4 ，5 ) 五1 2 ，3 ，3 ) 对应一个最优c p ( 3 ，3 ；1 2 ) ，其d l ( 1 2 ，3 ，3 ) = l ，1 1 ，6 ) ) 当m - - 2 时，u = 2 4 ，c d ( 2 4 ，3 ，3 ) = 1 1 ，五2 3 ，3 t 3 ) 为： ( 1 ，l o ，1 1 ) ，( 2 ，6 ，8 ) ，( 4 ，5 ，9 ) ，( 1 ，6 ，7 ) ，( 2 ，9 ，1 1 ) ， ( 4 , 8 ，1 2 ) ，( 1 ，5 ，6 ) ，( 3 ，4 ，7 ) ，( 2 ，9 ，1 1 ) ，( 3 ，7 ，1 0 ) ，( 3 ，5 ，8 ) 五2 4 1 3 ，3 ) 对应一个最优c p ( 3 ，3 ；2 4 ) ，其d l ( 2 4 ，3 ，3 ) = 1 0 ，1 4 ，1 2 当v = 1 2 m + 4m o 时， 由于1 2 m + 4 c b ( 3 ，2 ) ，c d ( 1 2 m + 4 ，3 ，3 ) = 【坐掣j _ 4 m + l ，且1 2 m + 4 c p ( 3 ，1 ) ，c d ( 1 2 m + 4 ，3 ，1 ) = 【学j _ 2 m 又由于c d ( 1 2 m + 4 ，3 ，2 ) = 【业掣卜 8 区组大小为3 的最优循环填充 三 主要结果的证明 6 m + 1 ，所以c d ( 1 2 m + 4 ，3 ，3 ) = c d ( 1 2 m + 4 ，3 ，2 ) + c d ( 1 2 m + 4 ，3 ，1 ) ，故- 万( 1 2 m “3 ，3 ) = 五1 2 m + 4 ，3 ，2 ) u 五1 2 m + 4 ，3 ，1 ) 对应一个最优c p ( 3 ，3 ；1 2 m + 4 ) 当u = 1 2 m + 8m o 时， c d ( 1 2 m + 8 ，3 ，3 ) = 【盟掣卢6 m + 3 ，由引 理3 1 的证明中的得五1 2 m + 8 ，2 ) 对应一个最优c p ( 3 ，2 ；1 2 m + 8 ) ，其d l ( 1 2 m + 8 ，3 ，2 ) = 1 时可在此基础上添加差 三角集五： ( 2 m - 2 r ，2 m + r + 2 ，4 m - r + 2 ) o r m - l ；( 2 m - 2 r - 1 ，4 m + r + 3 ，6 m r + 2 ) o o 时 c d ( 1 2 m + 2 ，3 ，3 ) = l 业学j - 6 m ，由引理3 1 中的i 得；五1 2 m + 2 ，3 ，2 ) 对应一 个最优c p ( 3 ，2 ；1 2 m + 2 ) 其d l ( 1 2 m + 2 ，3 ，2 ) = 2 m + 1 ，l o r e + l 且i 五1 2 m + 2 ，1 ) l = 4 m 当m 2 时可在此基础上添加差三角集y 2 ： ( 2 m - 2 r - i ，2 m + r + 1 ，4 m - r ) 0 r m - 1 ；( 2 m - 2 r - 2 ，4 m + r + 2 ，6 m - r ) o 一 l 时考虑下面的差三角集曩t 2 m + 6 3 ，。) ： ( 2 m - 2 r ，2 m + r + l ，4 i y 卜r + 1 ) 0 r m - 1 ；( 2 m - 2 r - 1 ，4 m + r + 2 ，6 n 卜r + 1 ) 0 一r 一 m - 1 ( 2 m - 2 r ，2 m + r + 2 ，4 i i 卜r + 2 ) 0 r m - 1 ；( 2 m - 2 r - 1 ，4 m + r + 3 ，6 i n r + 2 ) 0 一 r 一m - 1 ( 2 m - 2 r - 1 ，2 m + r + l ，4 m - r ) 0 r m - 1 ；( 2 m - 2 r ，4 m + r + 3 ，6 i n - r + 3 ) 0 一 1 时考虑下面的差三角集曩1 2 仇+ l o ，3 3 ) ： ( 2 m - 2 r ，2 m + r + 2 ，4 卜r + 2 ) 0 r m - 1 ；( 2 m 一2 r + 1 ，4 m + r 十3 ，6 m r + 4 ) 0 一 r 一m ( 2 m 一2 r + l ，2 m + r + 2 ，4 m r + 3 ) o r m ；( 2 m - 2 r ，4 m + r + 4 ，6 h 卜r + 4 ) 0 一 r 一 m - 1 ( 2 m - 2 r ，2 m + r + 3 ，4 m - r + 3 ) 0 一 r 一 m 一1 ；( 2 i n 一2 r + 1 ，4 m + r + 4 ，6 m - r + 5 ) 0 一 r 一 0 当v = 6 mm o 时分四种情形讨论：设v = 2 4 t ，2 4 t + 6 ，2 4 t + 1 2 ，2 4 t + 1 8t o i v = 2 4 tt o ，c d ( 9 4 t ，3 ，5 ) = 【芈卢2 0 t - 1 1 1 区组大小为3 的最优循环填充 三 主要结果的证明 考虑下面的差三角- 万( 2 4 1 3 ，5 ) ： ( 4 t - 2 r - 2 ，4 t + r + l ，8 t - r - 1 ) 0 r 2 t - 2 ；( 4 t - 2 r - 1 ，8 t + r + 1 ，1 2 t - r ) 0 一r 一2 t - 1 ( 4 t 一2 r - 2 ，4 t + r + l ，8 t r - 1 ) 0 r 2 t - 2 ；( 4 t 一2 r - 1 ，8 t + r ，1 2 t r - 1 ) 0 一 r 一 2 t i ( 4 t - 2 r - 1 ，4 t + r + l ，8 t - r ) 0 一 r 一 2 t 1 采取两次； ( 4 t 2 r - 2 ，8 t + r + l ，1 2 t - r - 1 ) 0 一r 一2 t 一2 采取两次 ( 2 t - 2 r - 1 ，5 t + r + 2 ，7 t - r + 1 ) 0 一r 一 t - 2 ；( 1 ，5 t ，5 t + 1 ) ；( 2 t + l ，4 t + 1 ，6 t + 2 ) ； ( 4 t 一2 r - 3 ，4 t + r + 2 ，8 t r - 1 ) 0 r b - 3 ；( 4 t - 2 r - 2 ，8 t + r + l ，1 2 t - r - 1 ) 0 一 r 一 2 t - 2 ( 4 t - 1 ，6 t + l ，1 0 t ) ；( 4 t ，4 t ，8 t ) ；( 4 t ，8 t ，1 2 t ) ( 4 t ，6 t ，1 0 t ) 采取两次 五2 4 t 1 3 ，5 ) 对应一个最优o p ( 3 ，5 ；2 4 t ) ，其d n ( 2 4 t ，3 ，5 ) = 1 2 t ) 当m = l 时，t ，= 2 4 ，o d ( 2 4 ，3 ，5 ) = 1 9 ，五2 4 ，3 5 ) 为： ( 1 , 5 ，6 ) ，( 2 ，9 ，i t ) ，( 4 ，8 ，1 2 ) ，( 3 ，7 ，1 0 ) ，前面四个差三角采取两次； ( 3 , 5 ，8 ) ，( 1 ，6 ，7 ) ，( 2 ，9 ，1 1 ) ，( 2 ，5 ，7 ) ，( 1 ，9 ，1 0 ) ， ( 3 , 8 ，1 1 ) ，( 4 ，6 ，1 0 ) ，( 1 ，1 0 ，1 1 ) ，( 2 ，6 ，8 ) ，( 4 ，5 ，9 ) ，( 3 ，4 ，7 ) 五2 4 ，3 ，5 ) 对应一个最优o p ( 3 ，5 ；2 4 ) ，其o n ( 2 4 ，3 ，5 ) = 0 时，由引理2 2 得，c d ( 2 4 t + 6 ，3 ，5 ) = 【里掣j 一1 = 2 0 t + 3 考虑下面的差三角五z 4 t + e ，s ，s ) ： ( 4 t 2 r ，4 t + r + l ，8 t r + 1 ) 0 一r 一 2 b - 1 采取两次； ( 4 t 一2 r - 1 ，8 t + r + 2 ，1 2 t r + 1 ) 0 _ r 2 t - 1 采取两次 ( 4 t 一2 r ，4 t + r + 2 ，8 t - r + 2 ) 0 r 2 t - 1 ；( 4 t - 2 r - 1 ，8 t + r + 3 ，1 2 t - r + 2 ) 0 一 r 一 2 t - 1 ( 4 t - 2 r - 1 ，4 t + r + 2 ，8 t r + 1 ) 0 r 2 t - 1 ；( 4 t - 2 r ，s t + r + 3 ，1 2 t r + 3 ) 0 一 r 一 2 t - 1 ( 4 t - 2 r - i ，4 t + r + 2 ，8 t - r + 1 ) 0 一r 一2 t - 1 ；( 4 t - 2 r ，8 t + r + 2 ，1 2 t r + 2 ) 0 一 r 一 o ，由引理2 2 得，c d ( 2 a t + 1 2 ，3 ，5 ) = 【型兰专幽j 一1 = 2 0 t + 8 虑下面的差三角五2 4 2 3 t 5 ) ： ( 4 t 一2 r ，4 t + r + 3 ，8 t - r + 3 ) 0 r 2 t - 1 ；( 4 t - 2 r + l ，s t + r + 4 ，1 2 t - r + 5 ) 0 一 r 一2 t ( 4 t - 2 r + l ，4 t + r + 2 ，8 t - r + 3 ) 0 r 2 t ；( 4 t - 2 r ，s t + r + 5 ，1 2 t - r + 5 ) 0 r _ 2 t 一1 上面四个组差三角分别采取两次 ( 4 t - 2 r + l ，4 t + r + 3 ，8 t - r + 4 ) o r 2 t ；( 4 t 一2 r ，8 t + r + 5 ，1 2 t r + 5 ) 0 r _ 2 t - 1 ( 4 t + 2 ，6 t + 3 ，1 0 t + 5 ) 采取两次，( 4 t + 2 ，8 t + 4 ，1 2 t + 6 ) 五2 4 州2 ，3 ，5 ) 对应一个最优c p ( 3 ，5 ；2 4 t + 1 2 ) ，d l ( 2 4 t + 1 2 ，3 ，5 ) = 【8 t + 4 ，1 6 t + 8 ， 1 0 t + 5 ，1 4 t + 7 ，( 1 2 t + 6 ) 3 当m = 0 时，u = 1 2 ，c d ( 1 2 ，3 ，5 ) = 8 ，五1 2 ，3 5 ) 为： ( 1 , 3 ，4 ) ，( 2 ，4 ，6 ) ，( 2 ，5 ，5 ) ，前面三个差三角分别采取两次； ( 1 , 2 ，3 ) ，( 1 ，3 ，4 ) 曩1 2 ，3 ，5 ) 对应一个最优c p ( 3 ，5 ；1 2 ) ，其d l ( 1 2 ，3 ，5 ) = 1 ，1 1 ，3 ，9 ，5 ，7 ，6 ) i v v = 2 4 t + 1 8t o ，c d ( 2 4 t + 1 8 ，5 ) = 【里丝掣j = 2 0 t + 1 4 考虑下面的差三角五2 4 m 8 3 ，5 ) ： ( 4 t - 2 r + l ，4 t + r + 4 ，8 t - r + 5 ) 0 r 2 t ；( 4 t - 2 r + 2 ，8 t + r + 7 ，1 2 t r + 9 ) 0 一r 一 2 t ( 4 t - 2 r + 2 ，4 t + r + 4 ，8 t - r + 6 ) 0 r 2 t ；( 4 t 一2 r + l ，8 t + r + 7 ，1 2 t - r + 8 ) 0 r _ 2 t 上面四组差三角分别采取两次 ( 1 , 7 t + 5 ，7 t + 6 ) ；( 2 t 一2 r - 1 ，5 t + r + 5 ，7 t - r + 4 ) 0 r _ t - 2 ；( 2 t + l ，4 t + 4 ，6 t + 5 ) ； ( 4 t - 2 r + l ，4 t + r + 5 ，8 t r + 6 ) 0 r t - 1 ；( 4 t 一2 r ，s t + r + 7 ，1 2 t - r + 7 ) 0 0 ，c d ( 1 2 m + 4 ，3 ，5 ) = 【坐掣j _ l o m + 2 根据m j c o l b o u r n 和c j c o l b o u r n 【2 0 】的证明，1 2 m + 4 ec b ( 3 ，4 ) 没有短轨道，c d ( 1 2 m + 4 ，3 ，4 ) = 【地等绁j 一 8 m + 2 又由于1 2 m + 4 c p ( 3 ，1 ) ，c d ( 1 2 m + 4 ，3 ，1 ) = 【塑学丑j _ 2 m 所以c d ( 1 2 m + 4 ，3 ，5 ) = c d ( 1 2 m + 4 ，3 ，4 ) + c d ( 1 2 m + 4 ，3 ，1 ) ，且令五1 2 m + 4 ，3 ，5 ) = 五1 2 m + 4 ，3 ，1 ) u 曩1 2 m “3 ，1 ) ，即可得曩1 2 m “3 ，5 ) 对应一个最优c p ( 3 ，5 ；1 2 m + 4 ) 根据m j c o l b o u r n 和c j c o l b o u r n 【2 0 】的证明，1 2 m + 1 0 c b ( 3 ，4 ) 没 有短轨道，当v = 1 2 m + l om o 时1 2 m + 1 0 ec p ( 3 ，5 ) 的证明同上 当u 兰5 ( m o d6 ) 且u 2 ( m o d4 ) 时，设v = 1 2 m + 5 ，1 2 m + l lm o v i 由于1 2 m + 5 c b ( 3 ，3 ) ，1 2 m + 1 1 c b ( 3 ，3 ) 没有短轨道，故情形跟 上面的证明类似 凸 引理3 5 当u - 2 ( r o o d4 ) 时 e c p ( 3 ，6 ) 证明：设v = 4 m + 2m 0 ，由引理2 1 得，c d ( 4 m + 2 ，3 ，厂 i - - l 1 6 ( 4 m + 6 2 - 1 ) j i l = 4 m 由引 理3 2 的证明中的i v ，v ，v i ，得4 m + 2 ec p ( 3 ，3 ) ，且c d ( 4 m + 2 ，3 ，3 ) = 【出掣j - 2 m 曩4 m + 2 ，3 ) 对应个最优c p ( 3 ，3 ；4 m + 2 ) 的差三角集，则只需要将五4 m +