若干图的等全着色及彩虹支配问题的研究

若干图的等全着色及彩虹支配问题的研究

论文摘要

图的等全着色是图的着色问题中的难题之一。对图的等全着色问题的研究不仅具有重要的理论意义,而且在安排课表、频率分配等领域有很广泛的应用。图的彩虹支配问题是图的支配问题中比较活跃的研究领域之一。图的彩虹支配问题的研究在优化理论、通讯网络设计与分析、网络搜索、模式识别等许多领域有很广泛的应用,对其研究具有现实意义。目前国内外已有结果给出对于最大度不超过3的图的等全着色数小于等于5的界,还给出路径、圈、太阳图的2-彩虹支配数的精确值,但未给出广义Petersen图P(n,2)和P(2k+1,k)的2-彩虹支配数的精确值。本文主要通过计算机计算及数学推理相结合的方法,研究了图的等伞着色及2-彩虹支配问题。对3-正则图如Flower snark及其相关图、Goldberg snark及其相关图、TwistedGoldberg snark及其相关图和Blanu(?)a snark图的等全着色进行研究。给出这些图的等全着色数为4.本文还对广义Petersen图P(n,2)和P(2k+1,k)的2-彩虹支配问题进行研究。给出对于所有的n,广义Petersen图P(n,2)的2-彩虹支配数的精确值为:而对于任意k≥2时,广义Petersen图P(2k+1,k)的2-彩虹支配数为:还给出广义Petersen图P(n,2)的2-彩虹支配方式。

论文目录

  • 摘要
  • Abstract
  • 引言
  • 1 基本概念
  • 1.1 图
  • 1.2 路与图的连通性
  • 1.3 正则图与完全二部图
  • 1.4 子图与生成子图
  • 1.5 导出子图与边导出子图
  • 1.6 图的同构
  • 1.7 弦图、n-太阳图
  • 2 图的等全着色和彩虹支配问题进展
  • 2.1 图的等全着色问题及进展
  • 2.1.1 着色的起源及发展
  • 2.1.2 着色的基本概念
  • 2.1.3 着色的计算复杂性
  • 2.1.4 着色的应用
  • 2.1.5 等全着色的发展
  • 2.2 图的彩虹支配问题及进展
  • 2.2.1 支配的起源及发展
  • 2.2.2 支配的基本概念
  • 2.2.3 支配的计算复杂性
  • 2.2.4 支配集的应用
  • 2.2.5 彩虹支配的发展
  • 2.3 本文工作
  • 3 若干snark及其相关图的等全着色问题
  • k的等全着色'>3.1 Flower snark及其相关图Fk的等全着色
  • k*的等全着色'>3.2 图Fk*的等全着色
  • k与Twisted Goldberg snark及其相关图Gk*的等全着色'>3.3 Goldberg snark及其相关图Gk与Twisted Goldberg snark及其相关图Gk*的等全着色
  • k1的等全着色'>3.4 Type 1 Blanu(?)a snark图Bk1的等全着色
  • k2的等全着色'>3.5 Type 2 Blanu(?)a snark图Bk2的等全着色
  • 4 广义Petersen图P(n,2)彩虹支配问题
  • 结论
  • 参考文献
  • 攻读硕士学位期间发表学术论文情况
  • 致谢
  • 相关论文文献

    • [1].彩虹[J]. 中国循证儿科杂志 2019(06)
    • [2].风雨过后是彩虹[J]. 民族音乐 2020(01)
    • [3].彩虹谷[J]. 美与时代(中) 2020(01)
    • [4].风雨见彩虹[J]. 农业发展与金融 2020(04)
    • [5].都市彩虹[J]. 美与时代(城市版) 2020(03)
    • [6].风雨彩虹映射中国之光[J]. 当代世界 2020(06)
    • [7].山边那一道美丽彩虹——记兵团劳动模范杨彩虹[J]. 兵团工运 2020(01)
    • [8].雨霁彩虹垂[J]. 中国海事 2020(07)
    • [9].添彩文体标志[J]. 包装工程 2020(14)
    • [10].天边的那一道彩虹[J]. 美术观察 2020(07)
    • [11].彩虹瀑[J]. 中国工会财会 2020(09)
    • [12].“背包客”金彩虹:工作着是快乐的[J]. 劳动保障世界 2019(13)
    • [13].寻找彩虹[J]. 美术观察 2019(07)
    • [14].童心飞扬的“彩虹”[J]. 思维与智慧 2018(01)
    • [15].彩虹[J]. 中国建材 2018(07)
    • [16].胜利彩虹[J]. 电视指南 2015(09)
    • [17].彩虹赞[J]. 曲艺 2017(11)
    • [18].架彩虹[J]. 中国报业 2018(21)
    • [19].彩虹[J]. 实用中医药杂志 2016(12)
    • [20].神奇的彩虹[J]. 当代音乐 2017(03)
    • [21].《彩虹》[J]. 大众文艺 2017(09)
    • [22].彩虹总在风雨后[J]. 成才与就业 2017(Z2)
    • [23].风雨彩虹[J]. 国土资源科普与文化 2017(03)
    • [24].彩虹[J]. 道路交通管理 2017(10)
    • [25].彩虹[J]. 社会科学动态 2017(09)
    • [26].彩虹金箍棒[J]. 美术观察 2017(11)
    • [27].废墟与彩虹[J]. 中国报业 2016(01)
    • [28].彩虹梦[J]. 成才与就业 2016(05)
    • [29].遇见彩虹[J]. 基建管理优化 2016(03)
    • [30].无尽的彩虹[J]. 美术观察 2014(12)

    标签:;  ;  ;  

    若干图的等全着色及彩虹支配问题的研究
    下载Doc文档

    猜你喜欢