论文部分内容阅读
令H为简单图,g为简单图的集合.图H的一个分解指的是对其边集的划分.如果图H可以分解成边不交的子图,每一个子图都同构于g中的一个图,则称该分解为一个(H,g)-分解.如果g只包含一个简单图G,则称为(H,G)-分解.本文中讨论的问题都与图分解有紧密的联系.图填充、图覆盖和图嵌入问题一直是图分解方向的重要问题.本文讨论了型为gn的(K4-e)-MGDP所有可能的余边图的存在性问题和简单的型为gn的(K4-e)-MGDC所有可能的溢边图的存在性问题.在STS到(K3+e)-设计最小嵌入问题研究的基础上,确定了对于第二小的|V∪ W|,STS(V,B)嵌入到(K3+e)-设计(V ∪ W,C)的必要条件是充分的.此外,提出了可分组核心设计的概念,并研究了型为gn的(K4-e)-GDND的存在性.本文结构组织如下.第1章简要介绍图分解的背景,基础知识和本文的主要结果.第2章中,分别讨论了型为g(n,h)区组为(K4-e)的不完全可分组设计和型为(g,h)n区组为(K4-e)的不完全可分组设计的构造方法.第3章中,首先给出了几个特定参数的(K4-e)-MGDP的不存在性证明,然后通过直接构造和递归构造的方法得到一些(k4-e)-MGDP的小阶数结果,最后应用(K4-e)-MGDP的构造方法并结合两种(K4-e)-IGDD的存在性结果,证明了对于任意的g>1,能够确定出型为gn的(K4-e)-MGDP所有可能的余边图.第4章中,首先讨论了区组为(K4-e)的最大可分组填充和最小可分组覆盖之间的关系,然后对证明过程中需要用到的组合工具进行回顾和说明,接着通过直接构造和递归构造的方法得到一些(K4-e)-MGDC的小阶数结果,最后应用(K4-e)-MGDC的构造方法并结合两种(K4-e)-IGDD的存在性结果,对于简单的型为gn的(K4-e)最小可分组覆盖,验证了所有可能的溢边图.第5章中,引入图嵌入的概念,在STS到(K3+e)-设计最小嵌入问题研究的基础上,确定了对于第二小的|V∪W|,STS(V,B)嵌入到(K3+e)-设计(V∪W,C)的必要条件是充分的.第6章中,引入可分组核心设计的概念,通过直接构造和递归构造的方法研究型为gn的(K4-e)-MGDP和(K4-e)-MGDC的存在性,从而确定型为gn的(K4-e)-GDND的存在性.