（应用数学专业论文）设计的染色及其相关问题的研究.pdf

中文摘要 设计的染色及其相关问题的研究 摘要 染色问题是图论中的经典问题 同时也是组合设计理论中的一项重要 研究课题 人们研究设计的染色最初是从超图开始的 从组合设计的观点 来看 一个超图是一个部分设计 自1 9 6 6 年e r d s s h a j n a l 和l o v d s z 开始研 究超图的染色以来 国内外许多学者在这方面已经做了大量的工作 并且 取得了许多优美结果 令 表示一个 阶完全图加上一个1 一因子 本 文主要研究当m 4 5 6 时风 的胁圈分解的平衡2 一染色和3 一染色问 题和区组长为5 的平衡不完全区组设计的2 一染色问题以及区组长为3 的可 分组设计的2 一染色和3 一染色问题 第二章主要研究m f 4 5 6 1 时凰 的m 一圈分解的平衡2 染色问题 通过直接构造和运用组合设计里的技巧和方法 我们证明了当m 4 5 6 时 对每个允许值口 都存在甄 的一个平衡2 一染色的m 一圈分解 第三章主要研究m 4 5 6 1 时凰 j 的m 一圈分解的平衡3 一染色问题 并完全解决了这一问题 同时为了解决凰 的平衡3 一染色的4 一圈分解的 存在性问题 我们证明了一个更一般的结论 即证明了当 m m 一1 时 不存在凰 的平衡 m 一1 一染色的m 圈分解 第四章主要研究b 5 a v 2 一染色的存在性 对a 1 通过直接构造和 w i l s o n 递归构造方法 我们完全解决了这一问题 即证明了对任意的 1 5 m o d2 0 都存在一个2 一染色的b 5 1 对a 2 我们也讨论了b 5 2 2 一 染色的存在性 给出了部分结果 同时作为这一结果的一个推论 我们完 整解决了b 5 1 的分割集的存在性问题 第五章主要研究3 g d d g 2 一染色和3 一染色的存在性 并完全解决了 上海交通大学博士学位论文 这一问题 即证明了当且仅当 n 4 时 存在一个2 一染色的3 g d d g 对任意可允许的取值9 和札 都存在一个3 一染色的3 g d d g 同时我们也 对4 g d d g 2 一染色进行了讨论 并得到了部分结果 关键词 染色 平衡染色 圈分解 平衡不完全区组设计 可分组设计 a b s t r a c t r e s e a r c ho nc o l o r i n g so fd e s i g n sa n dr e l a t e d p r o b l e m s a b s t r a c t t h ec o l o r i n gp r o b l e mi sac l a s s i c a lp r o b l e mi ng r a p ht h e o r e t i c a l a n di ti sa l s oo n eo f t h ef u n d a m e n t a la n di m p o r t a n tp r o b l e m si nc o m b i n a t o r i a ld e s i g nt h e o r y p e o p l eb e g a n t os t u d yc o l o r i n gp r o b l e m sf i r s tf r o mh y p e r g r a p h s f r o mt h ev i e w p o i n to fc o m b i n a t o r i a l d e s i g nt h e o r gah y p e r g r a p hi sap a r t i a ld e s i g n m a n yb e a u t i f u lr e s u l t sh a v eb e e ng o t s i n c e1 9 6 6 w h e ne r d s s h a j n a la n dl o v d s zb e g a nt os t u d yc o l o r i n go fh y p e r g r a p h s i nt h i sd i s s e r t a t i o n w em a i n l ys t u d yt h ee x i s t e n c eo fe q u i t a b l y2 c o l o r a b l ea n d3 一 c o l o r a b l em c y c l ed e c o m p o s i t i o n so fk u i i e c o p l e t eg r a p ho fo r d e r p l u saf a c t o r f o rm 4 5 6 a n dt h ep r o b l e mo f2 c h r o m a t i cb 5 a u f o ra 一1 2 w ea l s os t u d y t h ee x i s t e n c ep r o b l e mf o rc o l o r i n go fu n i f o r mg r o u pd i v i s i b l ed e s i g n sw i t hb l o c ks i z e s 3a n d4a n d i n d e x1 i nc h a p t e r2 w ei n v e s t i g a t et h ee x i s t e n c ep r o b l e mf o re q n i t a b l y2 c o l o r a b l em c y c l ed e c o m p o s i t i o n so f 玩 if o rm 4 5 6 u s i n gd i r e c tc o n s t r u c t i o n sa n d t e c h n i q u e si nc o m b i n a t o r i a ld e s i g nt h e o r gw ec o m p l e t e l ys o l v ei t w ep r o v et h a tf o r e v e r ya d m i s s i b l eo r d e r1 j t h e r ee x i s t sa l le q u i t a b l y2 c o l o r a b l em c y c l ed e c o m p o s i t i o n o f 凰 jf o rm f 4 5 6 i nc h a p t e r3 w ei n v e s t i g a t et h ee x i s t e n c ep r o b l e mf o re q u i t a b l y3 c o l o r a b l em c y c l ed e c o m p o s i t i o n so f 凰 f o rm 4 5 6 a l s ou s i n gd i r e c tc o n s t r u c t i o n sa n d t e c h n i q u e si nc o m b i n a t o r i a ld e s i g nt h e o r 弘w ec o m p l e t e l ys o l v ei t i no r d e rt op r o v et h e e x i s t e n c ep r o b l e mo fe q u i t a b l y3 c o l o r a b l e4 c y c l ed e c o m p o s i t i o n so fk u i w ep r o v e m o r eg e n e r a lr e s u l t ss h o w i n gt h a tt h e r ea r en oe q u i t a b l yf t 7 7 一1 一c o l o r a b l em c y c l e 3 坐 竺型望嬖 生竺堕兰垒兰竖些 竺 坚望型型堡 d e c o m p o s i t i o n so f 虬 i f o rv m m 一1 i nc h a p t e r4 w ei n v e s t i g a t et h ee x i s t e n c ep r o b l e mf o r2 c h r o m a t i cb 5 入 s f o ra 1 u s i n gd i r e c ta n dw i l s o nf o u n d o a n e n t mc o n s t r u c t i o n w eg i v eac o m p l e t e s o l u t i o nt ot h ee x i s t e n c eo f2 c h r o m a t i cb 5 1 v s w ep r o v et h a tf o re v e r yve1 5 f r o o d2 0 t h e r ee x i s t sa2 c h r o m a t i cb 5 1 口 a n df o ra 2 w e o b t a i np a r t i a l r e s u i t s a sac o n s e q u e n c eo ft h ea b o v er e s u l t s w ec o m p l e t e l ys o l v et h ee x i s t e n c eo f b l o c k i n gs e t si nb 5 l v s i nc h a p t e r5 w eg e n e r a l i z et h ec o n c e p to fc o l o r i n gt og r o u pd i v i s i b l ed e s i g n s w ei n v e s t i g a t et h ee x i s t e n c ep r o b l e mf o r2 c h r o m a t i c 3 c h r o m a t i c 3 g d d s g w e c o m p l e t e l ys o l v et h e m s h o wt h a tt h e r ee x i s t sa 2 c h o r a m i c3 g d d g i fa n do n l yi f 3 4 f o re v e r ya d m i s s i b l ev a l u eo f g 札 t h e r ee x i s t sa 3 c h o r a m i e3 g d d g w ea l s oi n v e s t i g a t et h ee x i s t e n c eo f2 c h r o m a t i c4 g d d g a n do b t a i np a r t i a lr e s u l t s k e yw o r d s c o l o r i n g e q u i t a b l ec o l o r i n g c y c l ed e s i g n b a l a n c e di n c o m p l e t e b l o c kd e s i g n g r o u pd i v i s i b l ed e s i g n 4 第一章绪论 1 1 研究背景 染色问题是图论中的经典问题 同时也是组合设计理论中的一项重要 研究课题 人们研究设计的染色最初是从超图开始的 从组合设计的观点来 看 一个超图是一个部分设计 自1 9 6 6 年e r d s s h a j n a l 2 3 和l o v f i s z 4 1 4 2 开 始研究超图的染色以来 国内外许多学者在这方面已经做了大量的工作 并且取得了许多漂亮的结果 5 8 令虬 表示一个秽阶完全图加上一个1 一 因子 本文主要研究当m 4 5 6 时凰 的胁圈分解的平衡2 染色和 3 染色问题和区组长为5 的平衡不完全区组设计的参染色问题以及区组长 为3 的可分组设计的2 染色和3 染色问题 1 图的圈分解及其染色问题 定义1 1 1 设g 和h 为图 h 的一个g 分解是这样的一个集合9 g 1 g 1 g p 满足对每一个i 1 i p 都有q 同构与g 并且g 划分图 日的边的集合 定义1 1 2 设v v x 1 z 为顶点集 e 乩z 2 x 2 z 3 z m x l 为边的集合 则称图g y g e 为m 一圈 记为 z z 2 z 我们称图 h 的一个m 一圈分解c 为h 的一个m 一圈分解或者圈设计 一般地 研究最多的是h 个顶点上的完全图 h 玩一i 完全 图去掉一个1 因子以及h i 完全图加上一个1 一因子 易知 的僻圈分解存在的必要条件是 k 三圳 毗 u 第一章绪论 一 的 d 圈分解存在的必要条件是 1 1 2 b a l s p a c h h g a v a l s 和m s a j n a 3 4 3 证明了上述必要条件也是充分的 定理1 1 3 3 4 3 设u m 都是正整数 条件门 1 纠也是充分的 定理1 1 4 3 4 3 设口 m 都是正整数 必要条件n 1 纠也是充分的 则甄的一个m 圈分解存在的必要 则凰一j r 的一个m 圈分解存在的 对于凰 的僻圈分解 我们易知其存在的必要条件是 口 m 口兰0 r o o d2 v 2 三0 r o o d2 m m 雪a j n a 4 4 证明了这个必要条件也是充分的 1 1 3 定理1 1 5 4 4 1 设 m 都是正整数 则 j 的一个m 圈分解存在的必 要条件 i 3 也是充分的 为方便叙述 我们将满足条件 1 1 1 的 的值为甄的胁圈分解存在 的允许值 类似的称呼也适用于 一 虬 定义1 1 6 设v h 为图日的顶点集 s 为颜色集饵中的元素我们称为颜 色 c 为图h 的一个m 一圈分解 我们称映射妒jv h 一s 为c 的一个染 色 如果l s i k 不妨设s s 1 8 2 8 k 则称妒为c 的一个舡染色 如果 对于任意的c c 都有l 妒 c i 1 其中妒 c u e c 妒 z 则称妒为c 的一 r m2吼 现陋 耐 o m 三 b 2 盯 o 一 三 移 口 i i 上海交通大学博士学位论文 个弱舡染色 如果存在c 的一个弱缸染色 但不存在c 的一个弱 m 一1 染色 则称k 为设计c 的弱色数 如果m 3 甄的一个3 圈分解实际上就是一个s t e i n e r 三元系 关于 s t e i n e r 三元系的染色问题 目前已经有了很多的研究 1 2 1 8 2 8 5 2 5 3 铜 也可 参考文献 1 9 这本书里第1 8 章的一篇综述文章 我们在下面的平衡不完全 区组设计的染色里有介绍 对于m 4 时甄的4 圈分解的弱染色 b u r g e s sa n dp i k e 1 4 证明了下 面的结论 定理1 1 7 1 4 1 对任意的整数k 2 都存在虬的一个弱肛染色的彳一圈分 解 定理1 1 8 1 4 1 对任意的整数k 2 都存在一个正整数讥 使得对所有允 许值口 都存在凰的一个弱肛染色的4 一圈分解 另外 q u a t t r o e c h if 5 0 m a r yw a t e r h o u s e 5 9 等对凰的4 圈分解的染色方 式进行了研究 g i o n f r i d d oa n dq u a t t r o c c h i 2 7 也研究了玩的4 圈分解的一 类特殊染色 在他们的构造里 允许出现一个圈的点都是同色的 z d v o r d k j k d r a 2 1 等对圈分解的染色方式的复杂性也有研究 c h e n m e if u h u n g l i n f u 1 6 17 等对圈长不全相同的玩的圈分解的染色也有研究 并也得到一些 不错的结果 2 0 0 4 年 p e t e ra d a m s d a r r y nb r y a n t 1 等提出了圈分解的平衡染色的概 念 并研究了甄和 一j 的圈分解的平衡染色问题 定义1 1 9 设c 为图日的一个m 圈分解 i p 为c 的一个缸染色 显然c 的 一个k 一染色诱导出c 中每个圈的一个染色 设啦为一个m 圈c c 中染 为颜色巩的顶点的个数 如果对任意的i j 1 2 七 都有i n i 一嘶i 1 则称i p 为此m 圈c 的一个平衡舡染色 如果对于c 中每个m 一圈c 妒都 9 第一章 绪论 是c 的一个平衡k 染色 则称妒为m 圈分解c 的一个平衡k 一染色 此时 我们称m 一圈分解c 是平衡k 染色的 m 4 时圈分解的染色问题的研究 般仅限于k 比较小的情形 比如 k 2 和3 对于甄的协圈分解的平衡2 染色 由简单的推理易知 如果 m 为偶数 这样的胁圈分解的平衡2 染色不存在 也就是说凰的偶圈分 解的平衡筘染色不存在 事实上 由于每个平衡2 染色的偶圈中染为同一 颜色的顶点的个数都是相同的 所以 必须是偶数 另一方面 圈中每个 点的度数都是2 所以 的每个顶点的总的度数口一1 是偶数 这与可是偶 数矛盾 对于m 是奇数 p e t e ra d a m s d a r r y nb r y a n t 和m a r yw a t e r h o u s e 2 2 证明了m 5 时凰的似圈分解的平衡二染色的存在性 定理1 1 1 0 2 的一个平衡乒染色的5 一圈分解存在的充分必要条件是 秽 5 v v 一1 三0 m o d1 0 对甄一 的胁圈分解的平衡二染色 文献 2 给出了如下的结果 定理1 1 1 1 2 设m 4 5 6 则对于每个可允许的取值 都存在甄一j 的一个平衡出染色的仇 圈分解 对圈分解的3 染色的研究 p e t e ra d a m s 1 1 等给出了下面的结果 定理1 1 1 2 1 k v i 的一个平衡g 染色的4 一圈分解存在的充分必要条件 是t 4 6 8 1 0 1 2 1 8 i 完全图凰的一个平衡乒染色的彳一圈分解存在的充 分必要条件是 9 定理1 1 1 3 1 k v i 的一个平衡舅染色的5 一圈分解存在的充分必要条件 是 三0 2 m o d1 0 t 21 0 完全图凰的一个平衡乒染色的5 圈分解存在 的充分必要条件是t 三1 5 m o d1 0 口25 1 0 上海交通大学博士学位论文 定理1 1 1 4 1 凰一i 的一个平衡乒染色的乒圈分解存在的充分必要条件 是口兰0 m o d6 口 6 j 完全图甄的一个平衡乒染色的乒圈分解存在的 充分必要条件是t 三9 r o o d l 2 9 对于甄 的胁圈分解的平衡染色问题的研究还没有 本文第二章和 第三章研究m t 4 5 6 时凰 的胁圈分解的平衡2 染色和平衡3 染色 问题 2 平衡不完全区组设计及其染色问题 定义1 1 1 5 设钉 k a 为给定的正整数 y 为一口元集合 b 为y 的k 元子 集 称为区组 的集合 如果满足y 中任意一对不同的元素都恰好同时包 含在a 个区组中 则称有序对 v b 为平衡不完全区组设计 记为b k a 移 通常称b 3 a 口 为三元系 记为t s v a t s v 1 叫作口阶s t e i n e r 三元系并 记作s t s v 由简单的推理易知平衡不完全区组设计b a a 口 存在的必要条件是 钉 k a 扣一1 兰0 m o d k 一1 1 1 4 a v v 一1 三0 m o dk k 一1 对于k 5 的b k a 钞 h a n a n i 3 0 在1 9 7 5 年完全解决了其存在性问题 定理1 1 1 6 3 0 设k 5 则对任意给定的正整数a 除去b 5 2 1 5 不存在 外 b k a 存在的必要条件以 也是充分的 定义1 1 1 7 设d k 召 为一个平衡不完全区组设计b k a 口 s 为颜色 集 我们称映射妒 y s 为d 的一个染色 如果j s i m 则称妒为d 的 一个m 一染色 对每个8 s 称集合妒q s 为一个染色类 如果对于任意的 第一章绪论 b b 都有i 妒 b i 1 阳 b 叫 其中妒 口 乩 8 妒 则称妒为d 的一个 弱m 一染色 强m 一染色 如果存在口的一个弱m 一染色 强m 一染色 但不 存在口的一个弱 m 一1 染色 强 m 1 染色 则称m 为设计口的弱色 数 强色数 对平衡不完全区组设计染色的研究大多数研究其色数问题 因此文中 如果不特别说明 提到一个平衡不完全区组设计d 的弱胁染色暖m 染 色 m 都是指的此设计的弱色数陋色麴 根据定义可知 在设计口一个弱 染色里 要求没有区组是单染色的 也就是不存在这样的区组 区组里面 所有的点都是同一种颜色 由简单的计数讨论可知 5 3 不存在非平凡的二 染色的t s v a 这里a 为任意的正整数 v 4 对于三元系的3 染色问题 a r o s e 5 2 利用b o s e 构造方法 3 6 和s k o l e m 序列方法 5 6 j 给出了下面的结果 定理1 1 1 8 5 2 对任意的t 兰1 3 m o d6 口 7 都存在一个弱乒染色的 s t s v 对a 1 的三元系的3 染色 s t i n s o n 和w a l l i s 利用类似于b o s e 构造法 和s k o l e m 序列方法 给出了其3 染色的完整解决 定理1 1 1 9 1 0 5 5 j 设a 为任意的正整数 对每个允许值口 t 25 都存在 一个弱乒染色的t s v a 对于s t e i n e r 三元系的任意 n 染色问题 m d eb r a n d e s 1 2 等给出了一 个界 定理1 1 2 0 1 2 对任意的m 3 都存在一个正整数v m 使得对任意的v t 兰1 3 m o d6 都存在一个弱m 染色的s t s v 对区组长为4 的平衡不完全区组设计的染色问题 h o f f m a n l i n d e r p h e l p s 3 2 3 3 r o s a c o l b o u m 5 4 以及f f r a n e k t s g r i g g 2 4 1 等证明了下面的定理 1 2 上海交通大学博士学位论文 定理1 1 2 1 2 4 3 2 3 3 5 4 1 设a 为任意的正整数 对每个允许值口 口 4 都 存在一个弱参染色的b 4 a 口 对于b 4 1 v 的任意僻染色问题 v a c l a vl i n e k 和b w a n t l a n d 3 9 给出 了一个界 定理1 1 2 2 3 9 对任意的m 2 都存在一个正整数 使得对任意的t v r n u 三1 4 r o o d1 2 都存在一个弱m 一染色的b 4 1 口 对k 5 已有结果很少 目前仅知道b 5 1 2 1 即4 阶的射影平面和唯 一的循环b 5 1 4 1 是弱2 染色的 参见文献 5 4 定义1 1 2 3 设d v b 为一个设计 x y 如果对任意的区组b 8 都 有口n x 0 b n y x o 则称x 是设计口的一个分割集 关于分割集 在射影平面方面已经有了大量的研究 见 1 0 3 1 4 5 4 8 4 9 5 7 等 后来人们将分割集的概念引入到其他的设计 目前已经有了大量的结果 见1 4 5 6 7 2 0 2 2 2 5 2 6 3 2 3 3 3 7 等 但这些结果大部分都是关于区组长k 4 的扣设计的分割集存在性问题0 2 时一个t 设计就是一个平衡不完全区 组设计 根据分割集以及2 染色的定义可知 一个设计带有分割集的充分 必要条件就是这个设计是二染色的 其染色类即为一个分割集 因此 对 于区组长为3 和4 的平衡不完全区组设计分割集的存在性已经解决了 对 区组长为5 的平衡不完全区组设计的分割集 已有结果很少 本文第四章研究a 1 2 时b 5 h 的二染色和分割集问题 3 可分组设计及其染色问题 定义1 1 2 4 设玑a 为两个正整数 k 和m 为两个正整数的集合 一个可分 组设计 c o d 记作g d k a m 口 是一个满足下列条件的三元组 x 9 8 1 3 第一章 绪 论 俐x 是个口元集 毋是x 的一个划分 其元称为组 对任意的g 9 有 g i m 俐移是x 的子集佛为区组 族 对任意的b b 有l b f k i 俐任意b 8 g 孚有i b n g f 1 似 x 中任意一对属于不同组的点对缸 疗恰好出现在8 的a 个区组 中 如果入 1 g d k a m v 简记为g d k m 设 墨毋 b 为一g d k a m t 称多重集 i g l g 9 为这个g d d 的组型 通常将组型简记为 n g gi g 将型为兀g 口i g i 的g d k a m 仃 记为 k a 一g d d g 口i a l 同时 将 e1 一g d d i i g 口l g f 简记为k g d d i i g 口f c l 如果k 一 耐 m d 则 称g d k a m 口 为均匀的 简记为g d k a 9 u 对于均匀g d d 即 k a g d d g 通过简单的计数可知 k a 一g d d g 存 在的必要条件是 瞄篡弛 l 5 定理1 1 2 5 2 l 当k 3 时 3 a 一g d d 9 存在的必要条件p 1 髟也是充分的 定理1 1 2 6 2 1 当k 4 时 除去4 一g d d 2 4 与4 一g d d 6 4 这两个设计不存 在外 4 a 一g d d g 存在的必要条件以 j 髟也是充分的 由定义可知 一个b k a u 就是一个组型为1 的 k a 一g d d 即 k a 一 g d d 1 而对 k a 一g d d 1 即b k a 的染色问题已经有了很多研究 但 1 4 上海交通大学博士学位论文 对于可分组设计的染色问题还没有详细的研究 本文第五章对均匀可分组 设计的染色进行了初步研究 第一章绪论 1 2主要结果 在第二章 我们通过直接构造以及将w i l s o n 基本构造方法运用到图的 圈分解上 完全解决了当m 4 5 6 时 的平衡2 染色的胁圈分解 的存在性问题 定理2 3 4 设m 4 5 6 存在凰 j 的一个平衡易染色的m 一圈分解的充 分必要条件是t m 口2 0 r o o d2 m 在第三章 我们运用类似第二章的方法与技巧 完全解决了当m 4 5 6 时凰 的平衡3 染色的僻圈分解的存在性问题 定理3 1 4 当且仅当 4 1 2 时 存在凰 j 的一个平衡乒染色的4 一圈 分解 定理3 2 8 存在 f 的一个平衡乒染色的乒圈分解的充分必要条件是 t 三0 m o d1 0 秽 1 0 定理3 3 3 存在亿 j r 的一个平衡乒染色的口圈分解的充分必要条件是 t 兰0 m o d6 t 6 在第四章 我们主要研究区组长为5 的平衡不完全区组设计的2 染色 问题 通过直接构造和运用w i l s o n 基本构造方法建立了下面的定理 定理4 2 1 3 对任意的移兰1 5 r o o d2 0 都存在一个参染色的b 5 l 定理4 3 52 染色的b 5 2 口 存在的必要条件t 三1 5 m o d1 0 也是充分 的 除了口 1 5 以及下面可能的例外 俐引理4 3 3 中1 4 个未解决的以及引理4 3 4 中3 3 个未解决的 俐口兰3 1 7 1 9 1 r o o d1 0 0 上海交通大学博士学位论文 同时作为定理4 2 1 3 的一个推论 我们完全解决了b 5 1 移 的分割集的 存在性问题 即得到了下面的结果 定理4 4 2 对任意的 三1 5 r o o d2 0 都存在一个带有分割集的b 5 1 可 在第五章 我们对可分组设计的染色进行了初步研究 主要研究3 g d d g 的2 染色和3 染色问题 并完全解决了这一问题 我们还研究4 g d d 9 的2 染色 得到部分结果 定理5 2 1 存在一个易染色的3 g d d g 的充分必要条件是乱 3 或者彳 定理5 2 1 0 存在一个乒染色的3 g d d g 的充分必要条件是 t l 3 u 一1 g 三0 m o d2 u u t 9 2 三0 m o d6 第二章m 4 5 6 时甄 的m 圈分解的平衡2 染色 关于圈分解的染色 已经有了不少结果 p e t e ra d a m s d a r r y nb r y a n t 和 m a r yw a t e r h o u s e 1 2 1 等解决了当m 4 5 6 时凰以及甄 j 的胁圈分解 的平衡参染色和平衡3 染色问题 在本章中 我们研究了当m 4 5 6 时 凰一 的m 圈分解的平衡2 一染色问题 并给出了完整的解答 如不特意说明 本章我们所用到的两种颜色分别为黑色和白色 b 和钟 表示凰 j r 的顶点中分别染为黑色和白色顶点的个数 此外 我们把连接 两个黑色 白色 顶点的边称为一个单色黑边 白边 把连接两个不同色顶 点的边称为双色边 2 1 i 的4 圈分解的平衡2 染色 对平衡2 染色的4 圈来说 易知每个平衡冬染色的垂圈都恰好包含 两个染为黑色的顶点和两个染为白色的顶点 并且这四个顶点的的安排方 式只有两种 口口 类型1类型2 图表1 平衡2 染色的垂圈的染色方式 对于凰 的平衡2 染色的垂圈分解的构造还是比较简单的 我们直 接列出凰 j 的所有的边 然后对这些边进行4 圈排列 使得这样得到的 每个4 圈都是平衡2 染色的 我们得到了下面这个关于甄 的平衡2 染 上海交通大学博士学位论文 色的4 圈分解的定理 定理2 1 1 存在玩 j 的一个平衡易染色的4 一圈分解的充分必要条件是 口i0 m o d4 v 4 证明 由定理1 1 5 可知 当且仅当t 三0 r o o d4 口 4 时 存在甄 的一个4 圈分解 由于 是偶数 所以我们把 2 个顶点染为黑色 另外 材 2 个顶点染为白色 注意到在k v l 的任何一个垂圈分解里总共有 移2 个 乒圈 设虬 j 的顶点集为铷u 0 1 p 一2 t 我们把下标为0 的顶点染 为黑色 把下标为1 的顶点染为白色 设1 因子i 为 j k v r 2 一j 州 其中 j 0 1 扣一4 4 k z 2 则我们得到 4 个类型为2 见图表1 的垂圈 训j l 孚刊 孚卅t 其中j 0 1 扣一4 4 由下面的垂圈我们可以得到剩下的 一2 8 个 类型为1 的垂圈 见图表1 u 0 0 j l d z 1 其中j 0 1 p 一4 2 l 1 2 警一j 易检验这就是 的一个平 衡2 染色的4 圈分解 口 2 2 凰 州 勺5 圈分解的平衡2 染色 对圈长为奇数的圈 如果在这个圈里有b 个顶点染为黑色 硼个顶点 染为白色 则不可能出现b w 事实上 对于圈长为奇数的圈分解的任何 一个圈都必须满足l b 一刮 1 一个平衡2 染色孓圈的染色方式只有四种情 形 见下图表2 qoqo 类型1类型2类型3 类型4 图表2 平衡2 染色的5 圈的染色方式 为了构造虬 j 的平衡2 一染色的5 圈分解 我们需要引进下面的成对 平衡设计的概念 定义2 2 1 设口和a 为给定的正整数 k 为一正整数的集合 成对平衡设 计记作 t k a 一p b d 是一个三元组 v8 其中v 是一个t 元集 召是y 的子集依为区组 族 满足任意b b 都有i b l k 并且y 任意一对不同 的点恰好包含在a 个区组中 整数可称为这个p b d 的阶 如果a 1 我们把 t k 1 p b d 简单地记为 u k 一p b d 我们用 口 忌 矿 一 p b d 表示这样的一个t 阶p b d 在这个p b d 里 只有一个区组长为s 的区 组 其他的区组长都为k 关于成对平衡设计 p b d 已经有了很深的研究 得到了一些漂亮的结 果 下面的引理对证明本节的主要定理是非常有用的 引理2 2 2 2 7 1 对任意的正整数z 存在 4 2 x l 3 j p b d 或者似 1 t 3 5 抄 p b d 由上面的这个引理 我们得到了一个关于区组长为3 的可分组设计的 结果 即下面的一个推论 2 0 上海交通大学博士学位论文 推论2 2 3 对任意的正整数石 存在一个g d 3 2 2 x 或者g d 3 2 4 4 2 x 证明 将 2 z 1 3 一p b d 或者 2 z 1 3 5 p b d 见上面的引理 删去一 个点 a 对于 2 x 1 3 5 p b d n 不包含在区组长为5 的那个唯一的区 组中 并且把那些截短了的区组 即原来包含点 a 的区组 看作组 这样就 分别得到了一个g d 3 2 2 x 或者g d 3 2 4 2 z 口 我们用缉 表示一个有p 个部 每个部都含有n 个顶点的多部图 虽 然存在k 3 5 的一个平衡2 一染色的5 圈分解 见 2 但为了本节证明的方便 我们重新给出其构造如下 引理2 2 4 2 存在恐 5 的一个平衡廖染色的乒圈分解 证明 设9 3 5 的顶点集为u 哦m 1 电 三个部分别为饿m 1 如 i i l 2 3 1 2 3 将 吼 2 t 4 i l i 1 2 3 中的每个点染为黑色 将其余的点染为白色 下面即为k a a 的一个平衡2 染色的5 圈分解 1 1 1 2 0 1 0 2 0 3 1 x 3 2 0 a 2 2 2 3 1 1 1 3 0 1 4 2 4 3 1 l 3 3 0 1 0 a 2 2 3 1 1 2 2 1 0 2 2 3 3 1 3 2 2 3 0 1 4 3 3 l 1 3 2 l 4 2 0 3 3 1 3 a 2 1 2 3 4 2 1 2 1 3 0 2 4 3 4 1 1 2 3 3 2 2 2 1 0 3 3 2 1 3 2 2 4 3 2 1 3 2 3 3 4 2 4 1 0 3 1 1 4 2 1 3 4 1 0 2 3 1 0 2 3 3 4 1 2 2 1 2 4 3 3 2 4 1 2 3 口 下面我们直接构造口 1 0 和仃 2 0 时甄 j 的平衡2 染色的5 圈分 解 这两个直接构造对后面的递归构造 即证明本节的主要结果是非常有 帮助的 引理2 2 5 存在尬o 的一个平衡乒染色的乒圈分解 2 1 堑三主竺 i 堕坠 塑苎 望坌竖塑 堑墨茎堡 证明 设凰 j 的顶点集为历 将 0 1 5 中的每个点染为黑色 将其余的点染为白色 设1 一因子 中的边为 0 9 t l 7 t 2 4 3 5 6 8 下面即为甄o 的一个平衡二染色的5 圈分解 0 1 5 7 8 o 3 2 8 9 0 5 9 3 6 0 7 1 4 9 1 2 4 8 6 1 3 4 7 9 1 7 3 5 8 2 0 4 6 9 2 4 5 6 7 3 5 2 6 8 口 引理2 2 6 存在k 2 0 的一个平衡曩染色的5 圈分解 证明 设k 2 0 i 的顶点集为 将 0 1 1 1 中的每个点染为黑色 将 其余的点染为白色 设1 一因子j 中的边为 o 1 6 1 1 7 2 6 3 4 5 1 5 7 1 0 8 1 3 t 9 1 9 1 1 1 8 1 2 1 4 下面的分解即为鲍o j 的一个平衡 二染色的5 圈分解 1 2 1 3 1 1 1 0 o 1 3 1 4 0 2 5 1 2 1 4 3 1 2 1 3 1 5 0 4 6 1 2 1 4 4 3 1 0 1 3 1 6 2 6 1 0 1 2 1 5 1 4 3 1 3 1 7 1 6 9 1 2 1 6 0 3 5 1 3 1 8 3 1 1 1 1 2 1 7 0 5 1 1 2 1 8 0 6 1 1 1 2 1 9 2 1 0 4 1 2 6 1 4 1 8 1 2 9 4 1 5 7 1 3 1 9 1 7 3 1 3 0 9 1 9 8 1 3 2 6 1 8 4 1 3 7 1 8 9 8 1 4 1 5 3 6 7 1 4 1 6 4 2 9 1 5 5 1 7 2 8 1 4 1 7 7 0 8 1 6 1 7 4 5 1 1 1 4 1 8 2 7 加 1 6 1 8 5 7 8 1 4 1 9 7 4 1 1 1 6 1 9 6 8 1 0 1 4 5 1 6 3 2 1 6 0 1 1 1 8 1 1 5 1 6 9 5 6 1 5 1 7 8 5 1 0 1 5 1 8 8 3 9 1 5 1 9 4 8 1 1 1 5 2 1 1 1 9 5 1 6 7 1 0 1 7 6 1 7 1 8 l l 7 9 1 7 1 9 1 0 9 1 1 1 7 3 1 9 9 1 1 8 1 9 0 1 1 0 有了上面的准备工作 下面我们证明本节的主要定理 口 上海交通大学博士学位论文 定理2 2 7 存在凰 f 的一个平衡孚染色的乒圈分解的充分必要条件是 t i0 r o o d1 0 1 0 证明 由定理1 1 5 可知 当且仅当 三0 m o d1 0 时 存在致 j 的 一个5 圈分解 设u 1 0 x 茁 1 由推论2 2 3 可知 对任意的正整数z 都 存在一个g d 3 2 2 x 或者g d 3 2 4 2 z 给这个g d d 的每个点都赋权5 即把一个顶点变为5 个 并将其中的三个点染为黑色另两个点染为白色 对组长为2 的组 赋权5 以后得到1 0 个点 设在1 一因子j 里有两个单色黑 边 一个单色白边和两个双色边以此1 0 个点为顶点集 类似地 对组长为 4 的组 赋权5 以后得到2 0 个点 设在1 因子j 里有三个单色黑边 一个 单色白边和六个双色边以此2 0 个点为顶点集 由引理2 2 4 我们可以用 5 的一个平衡二染色的5 圈分解去替代这 个g d d 的每个区组 进而 由引理2 2 5 和2 2 6 我们可以用所o 和鲍o 的一个平衡筘染色的5 一圈分解分别去替代这个g d d 的组长为2 的组和组 长为4 的组 很容易验证这样得到的甄 j 的一个5 圈分解是平衡参染色 的 口 2 3 凰 的6 圈分解的平衡2 染色 对6 圈 我们采用和垂圈差不多的方法去构造 一个6 圈的平衡二染 色的可能的染色方式见下面的图表3 ooo 类型1类型2类型3 图表3 平衡2 一染色的6 圈的染色方式 首先我们直接构造甄 和甄 e 的平衡2 染色的昏圈分解 引理2 3 1 存在鼠 的一个平衡乒染色的乒圈分解 证明 设甄 f 的顶点集为磊 将顶点0 1 和2 染为黑色 3 4 和5 染 为白色 设1 因子 中的边为 o 3 1 2 4 5 下面即为拖 的一个 平衡2 染色的6 圈分解 引理2 3 2 存在 6 的一个平衡乒染色的6 圈分解 口 证明 设 6 的顶点集为e 僦u m 1 一 5 t 两个部分别为m 1 5 t 江 1 2 将顶点仉 邑 电 江1 2 染为黑色 将剩下的顶点染为白色 下面即为 甄 e 的一个平衡2 染色的昏圈分解 0 1 0 2 4 1 5 2 1 l 3 2 2 1 2 2 0 1 1 2 3 1 5 2 4 1 4 2 2 l 3 2 5 1 1 2 4 1 2 2 1 0 2 3 l 3 2 0 1 4 2 3 l 2 2 5 1 5 2 2 t 0 2 5 1 4 2 1 1 1 2 口 为了证明本节的主要结果 我们需要引进图的并的概念 设g 和日为图 两个图g 和日的并 记作g vh 是这样的一个图 顶点集为v g uy 日 边集为e g ue h u l y g t y 日 定理2 3 3 存在 j 的一个平衡参染色的乒圈分解的充分必要条件是 兰0 r o o d6 t f 26 上海交通大学博士学位论文 证明 由定理1 1 5 可知 当且仅当口三0 r o o d6 t 26 时存在甄 j r 的一个6 圈分解 设口 6 x z 1 设 的琢点集为uk 其中 k m 1 矿一 5 i 将顶点0 t 1 i 五 i 1 2 染为黑色 将剩下的顶点染 为白色 设1 因子j 中的边为 o i 3 1 t 2 i 托 5 i i 1 2 z 由引理2 3 2 我们可以用甄 的一个平衡2 一染色的6 圈分解去替代 k v k 1 i m m 一1 时 不存在 的一个平衡 m 一1 染色的僻圈分解 本章所用到的三种颜色分别为白色 黑色和灰色 我们用w 表示白色 b 表示黑色 9 表示灰色 另外 表示一个有n 个部的多部图 每个部 的大小为均为mg 也表示一个有n 个都的图 每个部的大小都是p 但 不同于 办它只有相邻的部之间才有边相连 第一个部和最后一个部看 作相邻的部 3 1甄 分解为4 圈的平衡3 染色 在本节 我们研究玩 j 分解为垂圈的平衡3 染色问题 假定已经用m 一1 种颜色对一个图g 的顶点集进行染色 我们现在希望 能找到这个图g 的一个平衡 一1 一染色的胁圈分解 在这个圈分解里 每一个平衡 m 一1 染色的7 n 圈都必须满足其中有2 个点为同一种颜色 其他的m 一2 个点每个点都是不同的颜色 现在考虑第i 个颜色 简称颜色 i 和所有这样的m 圈 有2 个点同为颜色 我们将这样的m 圈分为种情 形 一种情形为包含一个单色边 即连接同为颜色i 的点的边 仇一圈 另一 种情形为不包含这样的一个单色边 含有单色边的m 圈的个数反过来又限 制了图g 中边的个数 因此图g 中每种颜色的顶点个数都有一个限制 这 就限制了图g 的阶数 事实上 如果凰 j 可以分解为平衡 m 一1 一染色 的m 圈 下面的定理给出了其阶数t 的一个上限 上海交通大学博士学位论文 定理3 1 1 用m 一1 种颜色对甄 的口个顶点染色 如果存在凰 的一 个平衡 m 一1 一染色的m 圈分解 则u m m 一1 证明 设翰为虬 j 中染为颜色i 的顶点个数 江1 2 m 一1 假定 凰 j 的胁圈分解中有q t 个i n 圈 每个僻圈都包含一个单色边 连接同 为颜色i 的点的边 则对每一个i q 是凰 中同为颜色i 的单色边的个 数 故 1 啦 言x i x i 一1 其中五为1 一因子j 中同为颜色i 的单色边的个数 所以 m 1m 11 o t 玩 戤一1 4 i 1i 1 上面的等式必须小于或者等于 j 中胁圈的总数 因此我们得到下面的 不等式 喜 知一m 丽1 1 矿 以 墨一 石 2 由于秽 箸1 两边同时乘以2 m 并移项可得 m 巧2 吼 2 十m 戤一2 m 又毫1 0 所以 i 1 m l m 一1m 一1 m 瓤2 鼢 2 m 鼢 对上面不等式的左边利用c a u c h y s c h w a r t z 不等式 z 瓤 2 m 一1 可得 击 m p 1 咫 m p 1 2 m 擎 故 者 蚤墨 2 m 三 因此 戤s m m 一1 口 前面我们从单色边的角度对筑