图分解及相关问题

图分解及相关问题

论文摘要

令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的存在性.

论文目录

  • 致谢
  • 中文摘要
  • 英文摘要
  • 第1章 绪论
  •   1.1 背景介绍
  •   1.2 主要结论
  • 第2章 基本构造
  • (n,h)的(K4-e)-IGDD'>  2.1 型为g(n,h)的(K4-e)-IGDD
  • 4-e)-IGDD'>    2.1.1 由可解设计构造(K4-e)-IGDD
  •     2.1.2 膨胀构造
  •     2.1.3 填洞构造
  • n的(K4-e)-IGDD'>  2.2 型为(g,h)n的(K4-e)-IGDD
  •     2.2.1 由2-标架得到的构造
  •     2.2.2 由成对平衡设计得到的构造
  •     2.2.3 膨胀构造
  •     2.2.4 填洞构造
  • 第3章 图填充问题
  •   3.1 基本知识介绍
  •   3.2 不存在性证明
  •   3.3 直接构造和递归构造
  •   3.4 定理3.1.4的证明
  •     3.4.1 g=2,3,4的情形
  •     3.4.2 g=6,7,8,9的情形
  •     3.4.3 g=11,12,13,14的情形
  •     3.4.4 一般的g的情形
  • 第4章 图覆盖问题
  •   4.1 基本知识介绍
  •   4.2 与最大可分组填充的关系
  •   4.3 将要用到的组合工具
  •   4.4 小阶数的例子
  •   4.5 主要定理的证明
  • 第5章 图嵌入问题
  •   5.1 基本知识介绍
  •   5.2 基本构造
  •   5.3 主要定理证明
  •     5.3.1 小阶数例子的构造方法
  •     5.3.2 v≡1(mod 6)的情形
  •     5.3.3 v≡3(mod 6)的情形
  • 第6章 可分组核心设计
  •   6.1 基本知识介绍
  •   6.2 可分组核心设计的直接构造与递归构造
  •     6.2.1 g=1,2,3,4的情形
  •     6.2.2 g=6,7,8,9,11,12,13,14的情形
  •     6.2.3 任意的g和主要定理
  • 第7章 待解决的问题
  • 参考文献
  • 附录A: 所有简单的八点六边图
  • 4的简单的(K4-e)-MGDC'>附录B: 型为24的简单的(K4-e)-MGDC
  • 附录C: 当v≡1,3(mod 6)时,嵌入问题小阶数例子的构造
  • 攻读博士期间完成论文情况
  • 学位论文数据集
  • 文章来源

    类型: 博士论文

    作者: 高玉峰

    导师: 常彦勋

    关键词: 图分解,图填充,图覆盖,图嵌入,核心设计,可分组设计,因子分解

    来源: 北京交通大学

    年度: 2019

    分类: 基础科学

    专业: 数学

    单位: 北京交通大学

    基金: 国家自然科学基金

    分类号: O157.5

    总页数: 115

    文件大小: 5543K

    下载量: 45

    相关论文文献

    • [1].不同指数的区组长为5的1-BSEC的存在性[J]. 福州大学学报(自然科学版) 2019(02)
    • [2].循环(3,1)-GDD(g~n)存在的必要条件[J]. 科学技术与工程 2009(13)
    • [3].基于可分组设计的部分重复码研究[J]. 通信学报 2015(02)
    • [4].关于FSOLS(2~nu~m)的存在性研究[J]. 宁波大学学报(理工版) 2008(04)
    • [5].区组大小为4的二重超单可分解的可分组设计[J]. 中国科学:数学 2011(03)
    • [6].区组大小为3的四重单纯支架[J]. 南京师大学报(自然科学版) 2010(01)
    • [7].一个新的超单可分组设计[J]. 佳木斯大学学报(自然科学版) 2009(01)

    标签:;  ;  ;  ;  ;  ;  ;  

    图分解及相关问题
    下载Doc文档

    猜你喜欢