基于矩阵半张量积方法的几类图着色问题研究及应用

发布时间：2017-07-29 18:33

  本文关键词：基于矩阵半张量积方法的几类图着色问题研究及应用

  更多相关文章： 鲁棒图着色 列表着色 T-着色 conflict-free着色 频率分配 矩阵半张量积

【摘要】：图着色问题是图论中经典的研究课题,在上个世纪70年代首次被证明为NP-hard问题.图着色问题不仅在图论发展中发挥了重要作用,而且广泛应用于现实生活中,如航空流量管理、时间表安排、任务调度、频率分配等.因此对其进行研究具有非常重要的理论和现实意义.鉴于图着色问题的多样性,其相关研究多以某些特定形式的着色问题为研究对象.本课题利用矩阵的半张量积方法,进一步深入研究图着色问题中的鲁棒图着色、T-着色、列表着色、超图的Conflict-free着色以及模糊图的着色等问题.对这些特定形式的着色问题,给出若干新的代数结果和算法,并将研究结果应用于考试时间表问题和无线通讯中的频率分配问题.主要包含如下研究内容：1.研究鲁棒图着色问题及其在考试时间表中的应用,提出一些新的结果和算法.运用矩阵半张量积将鲁棒图着色问题表示成一类矩阵代数形式的优化问题,并设计一个新的算法以寻找鲁棒性最好的所有着色方案.进一步,研究鲁棒图着色问题的等价问题,给出一个充要条件,由此建立一个新的算法寻找鲁棒性最好的所有着色方案.另外作为应用,讨论一类考试时间表问题,得到一个设计切实可行的时间表方案的方法.两个例子的计算结果说明新结论和算法的有效性.2.运用矩阵半张量积,研究简单图的T-着色和列表着色及其在频率分配中的应用.首先,运用矩阵半张量积研究T-着色问题,得到可T-着色的两个充要条件,并在此基础上,建立一个新的算法以寻找T-着色方案.其次,运用半张量积研究列表着色问题,得到列表着色的充要条件,并由此得到列表T-着色的充要条件.最后,将所得的结果应用于频率分配问题,以证明所得结果的有效性和应用性.3.运用矩阵半张量积,研究超图的Conflict-free着色问题,得到几个新的结果和算法.通过超图的势矩阵和特征逻辑向量,得到Conflict-free着色的两个充要条件,在此基础上,建立一个可以确定Conflict-free着色方案的新算法.最后，，将理论结果应用于频率分配问题,说明所得结果的有效性和应用性.4.研究模糊图的稳定点集和着色问题.首先,通过定义特征逻辑变量,利用逻辑函数的矩阵表示,得到模糊稳定点集的代数描述.基于此,建立一个新的算法以寻找模糊图的所有稳定点集.其次,利用矩阵半张量研究模糊图的着色问题,对于模糊图的可着色性给出两个充要条件,在此基础上建立一个新的算法,确定所有模糊着色方案及模糊图的色数.最后,举例说明结论的有效性.
【关键词】：鲁棒图着色 列表着色 T-着色 conflict-free着色 频率分配 矩阵半张量积
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要9-11
• ABSTRACT11-14
• 第一章 绪论14-24
• 1.1 图着色理论的研究背景及现状14-20
• 1.2 矩阵半张量积的研究现状20-21
• 1.3 本文的主要内容21-24
• 第二章 预备知识24-36
• 2.1 矩阵半张量积的基本概念及性质25-30
• 2.2 逻辑函数的矩阵表示30-33
• 2.3 图论的基本概念及性质33-35
• 2.4 小结35-36
• 第三章 鲁棒图着色及其在考试时间表中的应用36-54
• 3.1 引言36-37
• 3.2 鲁棒图着色37-47
• 3.2.1 等罚值的鲁棒图着色39-46
• 3.2.2 不等罚值的鲁棒图着色46-47
• 3.3 考试时间表中的应用47-49
• 3.4 例子49-52
• 3.5 小结52-54
• 第四章 T-着色和列表着色及其在频率分配中的应用54-72
• 4.1 引言54-55
• 4.2 T-着色55-59
• 4.3 列表着色59-63
• 4.4 列表T-着色63
• 4.5 频率分配中的应用63-65
• 4.6 例子65-69
• 4.7 小结69-72
• 第五章 Conflict-free着色及其在频率分配中的应用72-80
• 5.1 引言72-73
• 5.2 Conflict-free着色73-77
• 5.3 频率分配中的应用77-79
• 5.4 小结79-80
• 第六章 模糊稳定点集和模糊图着色80-98
• 6.1 引言80-81
• 6.2 模糊稳定点集81-85
• 6.3 模糊图着色85-93
• 6.3.1 交通信号灯问题85-87
• 6.3.2 模糊图着色87-93
• 6.4 例子93-96
• 6.5 小结96-98
• 第七章 结论与展望98-100
• 7.1 结论98
• 7.2 展望98-100
• 参考文献100-112
• 致谢112-114
• 攻读博士学位期间完成的论文及参与的科研项目114-116
• 附件（文章）116-133
• 附件（表）133

【参考文献】

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

1 ;Logic and logic-based control[J];Journal of Control Theory and Applications;2008年01期

2 LIU ZhenBin;WANG YuZhen;LI HaiTao;;Two kinds of optimal controls for probabilistic mix-valued logical dynamic networks[J];Science China(Information Sciences);2014年05期

3 李志强;宋金利;;布尔控制网络的能控性与能观性(英文)[J];控制理论与应用;2013年06期

4 葛爱冬;王玉振;魏爱荣;;基于矩阵半张量积方法的随机模糊系统控制器设计[J];山东大学学报(工学版);2013年03期

本文编号：590563