摘要
基本的图的弱染色问题是图的全染色问题的一个过渡问题,这种方式与使用顶点可区别染色研究全染色的问题的角度正相反。弱染色研究染色条件的组合性质。弱染色算法的研究也是从研究基本的图染色问题算法开始,常见的算法类型有顺序算法、仿生算法和其他智能算法,其中很多都能在工程应用中取得令人满意的效果。使用图的谱性质研究染色问题是一种独特的算法,虽然目前这种算法的性能还不能与一些强大的算法相比美,但是也受到许多染色算法性能评估研究的关注。 时下,已出现一部分文献将团、二分和染色等问题统一纳入到图划分问题下,基于这一观点,本文给出假设:存在一种顶点相似关系能够通过谱聚类产生图的染色。由此通过点染色问题一步步进入弱染色问题,研究弱染色条件之间的关系。 本文的内容摘要如下: (1)首先对已有的染色概念和理论进行总结。通过整理现有染色概念对染色条件进行分类,给出第一类染色条件和第二类染色条件的概念,引申出弱染色问题;介绍度基准和谱基准的染色算法,指出两者算法在性质上的不同,同时由经典的MostNeg算法和Alon算法总结出谱基准算法中的一些共性;通过策略性质的染色算法的分析指出染色算法不只是组合优化,也要使用一些其他技术。 (2)由谱基准算法的特点自然地将问题转向谱聚类问题,通过谱聚类概念分析谱聚类原理,确定其在染色问题算法设计中需要注意的环节;由相似度概念试探性地引入网络研究中的顶点相似度,并分析这种结构关系是否适用于通过谱聚类形成顶点集合的染色划分。 (3)设计一系列实验验证弱染色条件的关系。通过顶点染色实验给出基于Jaccard指数的RatioCut染色算法和基于邻接矩阵的NCut染色算法,指出染色可能受顶点关系和Laplacian矩阵两者共同影响;使用转换模型实现边染色和弱染色,通过直接转换模型对顶点的邻接、边的邻接和点边关联这三种关系进行转换,并给出转换后的染色结果,指出这种转换对染色性能的影响,并且由此推出在谱特性的染色中,这三类关系是异质关系。
NETL