论文部分内容阅读
组合设计理论是离散数学的一个重要分支,这一理论的基本问题即是各类设计的存在性与构作,自1847年Kirkman[64,108]解决一类经典的设计即Steiner三元系的存在性问题以来,关于组合设计的研究得到了蓬勃的发展.近几十年来可分解设计尤其得到重视,历史上著名的Kirkman女生问题即是研究λ=1时的可分解三元系(即Kirkman三元系)的存在性,这一问题历经一百多年,已经由Ray-Chadhuri与Wilson[86]和陆家羲[79]分别独立地予以解决. 区组设计的存在性问题可以看作图分解为完全子图的问题.如Steiner三元系即为完全图的3阶完全图分解.在区组设计之后,圈设计自然地成为了图的分解问题的一个重要的研究对象.关于这一问题的研究最早可以追溯到20世纪60年代,Kotzig[67]和Rosa[90]解决了完全图K2xk+1的七-圈分解问题.从那以后,圈分解问题尤其是完全图的可分解的圈分解问题引起了很多专家学者的关注.关于这一问题已有数百篇文章发表. 在完全图的圈分解问题中,Oberwolfach问题是其中重要的一类.这一问题是Ringle于1967年在德国Oberwolfach召开的图论会议上提出的,它研究的是是否可以把完全图分解成一些2-因子(2-正则生成子图),使得所有的2-因子都同构于一个给定的2-因子F.当F由长为3的圈组成时,此问题即是Kirkman女生问题,而当F为一个Hamilton圈时,这一问题就是完全图的Hamilton圈分解问题. Hamilton-Waterloo问题是Oberwolfach问题的一个推广.对于给定的2-因子R和S,Hamilton-Waterloo问题研究是否能把完全图Kn(当n为奇数时)或Kn-In(当n为偶数时,In为Kn的一个1-因子)分解为若干个2-因子,使得其中r个2-因子同构于R,另外s个同构于S.当给定的两个2-因子分别由长为p和q的圈组成时,我们称这样的2-因子分解是均匀的,此时记2-因子分解为HW(n;r,s;p,q).本文将对均匀情形的Hamilton-Waterloo问题展开研究,重点研究其中一类2-因子为Hamilton圈,另一类2-因子由k长圈构成(记为Ck-因子)的情形,其中k为任意给定正整数. 本文第一章将详细介绍Hamilton-Waterloo问题的历史,研究进展,研究方法及本文的主要结果. 在第二章中我们首先给出HW(n;r,s;p,q)存在的必要条件.然后分奇数阶完全图和偶数阶完全图两种情况,对HW(n;r,s;n,2k+1)的存在性展开研究,证明了当Hamilton圈的个数大于一个依赖于n和k的数时,相应的2-因子分解是存在的. 第三章对n为偶数时HW(n;r,s;n,3)的存在性进行深入的研究.当n=0(mod18)时,我们利用拟Kirkman三元系的相关结果,除了3个情形外,证明了对于任意满足第二章给出的必要条件的n,HW(n;r,s;n,3)均是存在的.当n三6(mod18)时,我们利用Kirkman3-标架设计的结果,除了r=1的情形之外,完全确定了HW(n;r,s;n,3)的存在性, 第四章对任意的正整数k,研究HW(n;r,s;n,4k)的存在性.我们利用完全二部图的圈分解的有关结果,证明了HW(n;r,s;n,4k)存在的充分必要条件是s=0或s≠0且n≡0(mod4k). 最后以对已有工作的总结和对未来工作的展望作为结束.