广义循环图彩虹支配问题的研究

发布时间：2017-10-16 16:10

  本文关键词：广义循环图彩虹支配问题的研究

  更多相关文章： 循环图 彩虹支配 2-彩虹支配数

【摘要】：图论不仅是组合数学的一个重要分支,而且还是离散数学的一个重要分支。图的彩虹支配及其相关问题,是近年来一个比较热门的研究问题。研究图的彩虹支配问题不仅具有重要的理论价值,而且具有重要的应用价值。它已被广泛地用来解决计算机科学、信息科学、网络理论等学科的问题,对其研究具有重大意义。本文主要研究的是广义循环图的2-彩虹支配问题,研究结果如下：(1).研究了广义循环图C(n；(1,2))的2-彩虹支配问题,求出了其2-彩虹支配函数的精确值；(2).研究了广义循环图C(n；{1,3}.)的2-彩虹支配问题,求出了其2-彩虹支配函数的精确值；(3).研究了广义循环图C(n；{1,2,...,k})的2-彩虹支配问题,求出了其2-彩虹支配函数的精确值。本文所研究的广义循环图的2-彩虹支配问题,是一个NP-完全问题。研究它不仅对彩虹支配问题有重大的意义,而且对其它的NP-完全问题也有借鉴作用。这些研究结果进一步丰富了循环图的彩虹支配的精确解。
【关键词】：循环图 彩虹支配 2-彩虹支配数
【学位授予单位】：内蒙古农业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-7
• 缩略语表7-8
• 1 引言8-13
• 1.1 基本概念9-13
• 1.1.1 图9
• 1.1.2 路与图的连通性9-10
• 1.1.3 正则图与完全二部图10-11
• 1.1.4 子图与生成子图11-12
• 1.1.5 弦图、n-太阳图12-13
• 2 图的彩虹支配问题发展13-19
• 2.1 支配的起源与发展13-14
• 2.2 支配的基本概念14
• 2.3 支配的计算复杂性14-16
• 2.4 支配集的应用16
• 2.5 彩虹支配的研究进展16-18
• 2.6 本文工作18
• 2.7 本章小结18-19
• 3 广义循环图C(n；{1,2})的2-彩虹支配问题19-27
• 3.1 广义循环图C(n；{1,2})的2-彩虹支配问题19-26
• 3.2 本章小结26-27
• 4 广义循环图C(n；{1，，3})的2-彩虹支配问题27-39
• 4.1 广义循环图C(n;{1,3})的2-彩虹支配数27-38
• 4.2 本章小结38-39
• 5 广义循环图C(n{1，2...,k})的2-彩虹支配问题39-46
• 5.1 广义循环图C(n;{1,2...,k})的2-彩虹支配问题39-45
• 5.2 本章小结45-46
• 6 总结46-47
• 7 展望47-48
• 致谢48-49
• 参考文献49-53
• 作者简介53

【参考文献】

中国期刊全文数据库 前8条

1 阎新芳,孙雨耕,胡华东;基于极大权的最小连通支配集启发式算法[J];电子学报;2004年11期

2 朱艺华;沈毅俊;吴小燕;汪加才;;移动自组网电力及负荷感知的构造最小连通支配集算法[J];电子学报;2006年11期

3 唐勇;周明天;;基于极大独立集的最小连通支配集的分布式算法[J];电子学报;2007年05期

4 阎新芳;刘爱琴;杨挺;;基于极小独立支配集的MANET虚拟骨干网算法[J];电子学报;2007年06期

5 邵泽辉;;网格图的2-彩虹控制数[J];成都大学学报(自然科学版);2013年01期

6 彭伟,卢锡城;移动自组网络中采用连通支配集的有效广播技术(英文)[J];软件学报;2001年04期

7 毛莺池;冯国富;陈力军;陈道蓄;;与位置无关的无线传感器网络连通性覆盖协议[J];软件学报;2007年07期

8 黄元江,汤德佑;传感器网络中基于连通支配集的路由算法[J];计算机工程与设计;2005年06期

中国博士学位论文全文数据库 前2条

1 赵承业;图的支配问题研究[D];大连理工大学;2007年

2 付学良;若干类图支配问题的研究[D];大连理工大学;2008年

中国硕士学位论文全文数据库 前2条

1 吉春年;广义Petersen图和循环图的罗马支配研究[D];大连理工大学;2008年

2 罗梅琴;若干图的等全着色及彩虹支配问题的研究[D];大连理工大学;2008年

本文编号：1043632