【摘 要】
:
图着色问题是图论中经典的研究课题,在上个世纪70年代首次被证明为NP-hard问题.图着色问题不仅在图论发展中发挥了重要作用,而且广泛应用于现实生活中,如航空流量管理、时间
论文部分内容阅读
图着色问题是图论中经典的研究课题,在上个世纪70年代首次被证明为NP-hard问题.图着色问题不仅在图论发展中发挥了重要作用,而且广泛应用于现实生活中,如航空流量管理、时间表安排、任务调度、频率分配等.因此对其进行研究具有非常重要的理论和现实意义.鉴于图着色问题的多样性,其相关研究多以某些特定形式的着色问题为研究对象.本课题利用矩阵的半张量积方法,进一步深入研究图着色问题中的鲁棒图着色、T-着色、列表着色、超图的Conflict-free着色以及模糊图的着色等问题.对这些特定形式的着色问题,给出若干新的代数结果和算法,并将研究结果应用于考试时间表问题和无线通讯中的频率分配问题.主要包含如下研究内容:1.研究鲁棒图着色问题及其在考试时间表中的应用,提出一些新的结果和算法.运用矩阵半张量积将鲁棒图着色问题表示成一类矩阵代数形式的优化问题,并设计一个新的算法以寻找鲁棒性最好的所有着色方案.进一步,研究鲁棒图着色问题的等价问题,给出一个充要条件,由此建立一个新的算法寻找鲁棒性最好的所有着色方案.另外作为应用,讨论一类考试时间表问题,得到一个设计切实可行的时间表方案的方法.两个例子的计算结果说明新结论和算法的有效性.2.运用矩阵半张量积,研究简单图的T-着色和列表着色及其在频率分配中的应用.首先,运用矩阵半张量积研究T-着色问题,得到可T-着色的两个充要条件,并在此基础上,建立一个新的算法以寻找T-着色方案.其次,运用半张量积研究列表着色问题,得到列表着色的充要条件,并由此得到列表T-着色的充要条件.最后,将所得的结果应用于频率分配问题,以证明所得结果的有效性和应用性.3.运用矩阵半张量积,研究超图的Conflict-free着色问题,得到几个新的结果和算法.通过超图的势矩阵和特征逻辑向量,得到Conflict-free着色的两个充要条件,在此基础上,建立一个可以确定Conflict-free着色方案的新算法.最后,将理论结果应用于频率分配问题,说明所得结果的有效性和应用性.4.研究模糊图的稳定点集和着色问题.首先,通过定义特征逻辑变量,利用逻辑函数的矩阵表示,得到模糊稳定点集的代数描述.基于此,建立一个新的算法以寻找模糊图的所有稳定点集.其次,利用矩阵半张量研究模糊图的着色问题,对于模糊图的可着色性给出两个充要条件,在此基础上建立一个新的算法,确定所有模糊着色方案及模糊图的色数.最后,举例说明结论的有效性.
其他文献
<正>近年,随着短效、强效的全身麻醉药物和麻醉性镇痛药物以及高质量的医疗设备如麻醉机、监护仪在临床麻醉中的应用和普及,加上手术和病人的需求,气管内插管的全身麻醉技术
随着Web服务方式的发展,新型的数据资源Web API大量地涌现出来。为了更加方便地管理快速增长的Web API,人们基于Web API的描述文本使用标签信息对Web API进行标记,而如何正确
【正】 为了充分满足读者各方面的需要,图书馆编制了不同用途的目录。各个图书馆应该编制哪些目录?它们的职能及相互关系如何?它们反映藏书的完备程度怎样?要解决这一系列的
跨期选择(intertemporal decision-making)描述了人们对于发生在不同时间点的事件的利益、后果(consequence)进行权衡从而做出的审慎决策。而在跨期选择中往往出现一种稳定的具有明显偏向性的决策偏好,即与当前或短期的(short-term)获益相比较,人们通常对那些长远的(long-term)获益赋予更小的权重和偏好,称为延迟折扣(delay discounting)
1.故障现象一台长江牌QY16T型汽车起重机的起重臂杆由基本臂和2节伸缩臂组成,起重臂杆的伸缩动作正常,但将2节伸缩臂伸到头开始缩臂时,全机开始抖动,压力表摆动很大,特别是臂
D2D网络作为当今信息网络架构关键技术之一,一方面可以有效提高系统频谱利用率并降低蜂窝网络中基站负荷,另一方面D2D网络与社会网络的结合实现了物理传输与社会属性的融合,
自主导航是全球卫星导航系统(Global Navigation Satellite System:GNSS)未来发展的必然趋势,基于星间链路的星间测量和数据传输是维持自主导航的基础。依靠星间链路,卫星导航系统不仅可以在依赖较少甚至不依赖地面站的情况下,自主进行星历、钟差解算以及导航电文播发,为用户提供导航服务,同时还解决了我国区域测控网布站局限性的问题。因此,星间链路的研究成为我国北斗建设的重中之
铝合金因具备优良的导电性、导热性和比强度,广泛运用于航天航空、船舶化工、数码3C、建筑型材等领域。但铝合金电极电位为负,活性强易发生各类腐蚀。工业应用中,需对铝合金进行表面防护处理。铬酸盐转化处理是铝合金传统表面防护技术,可有效提高铝合金的耐蚀性及与有机涂层的结合力。但铬酸盐转化液中含六价铬等毒性物质,对人身健康及环境危害极大,因此开发无铬转化技术越发重要。钛/锆转化处理技术因其膜层耐蚀性优良、成
将含有Ca^2+的壳聚糖溶液与含有CO3^2-的碱溶液用离子可渗透膜隔离,根据膜渗透原理,使膜内壳聚糖与碱液原位沉析,生成碳酸钙,得到具有高强度的碳酸钙(CaCO3)/壳聚糖(CS)三维复合材料.XRD
一辆美款奥迪A6轿车,装备2.8L发动机和自动变速器,在某单位维修空调系统之后,出现接通点火开关后,仪表盘上的安全气囊警告灯一直点亮的现象。使用故障检测仪进行检查,结果无