图中点对偶的几个着色定理及算法

探讨了简单图Ｇ＝（Ｎ，Ｅ）中不邻接点的着色问题，给出连通的简单图中，点对偶在ｒ（Ｇ）＝ｋ）着色中为同色和异色的性质，色数的存在区间等，提出了求简单图色数的一种较有效的算法。     

地图的着色及着色算法

本文对地图着色的问题进行了一定的分析和讨论,并提出了地图着色的一个新算法,并将此算法和一些其它算法作了比较,说明了该算法的着色优点.     

图着色问题的蚂蚁算法研究

随机蚂蚁着色算法是根据蚂蚁算法的搜索机制和反馈功能提出的解决图着色问题的新算法,继承了蚂蚁算法快速收敛以及跳出局部最优解的优良特性,结合传统图着色算法的着色思想,提出了逆序蚂蚁着色算法和贪心蚂蚁着色算法,进一步提高了求解质量,加快了收敛速度.实验结果证明了逆序蚂蚁着色算法和贪心蚂蚁着色算法的优良特性.为了合理选取蚂蚁着色算法参数,进行了大量随机图着色实验分析,得出了关键参数的最佳取值范围.     

图着色问题的细胞神经网络算法研究

应用细胞神经网络模型，系统地研究了图着色的ＣＮＮ算法，构造了能量函数，建立了相应的数学关系和表达工，与图着色的其他算法相比较，此算法的模型具有结构简单，易于实现的特点。     

图着色问题的细胞神经网络算法研究

应用细胞神经网络（ＣｅｌｕｌａｒＮｅｕｒａｌＮｅｔｗｏｒｋｓ—ＣＮＮ）模型,系统地研究了图着色的ＣＮＮ算法,构造了能量函数,建立了相应的数学关系和表达式．与图着色的其他算法相比较,此算法的模型具有结构简单,易于实现的特点．     

重图边着色的两个新结果

利用Ｈ．Ｐ．Ｙａｐ在文献［２］中给出的方法,给出了关于重图边着色的两个新结果,为较精确地估计重图的边色数提供了可行的方法。     

基于独立集划分的图着色算法

针对经典的图着色问题,在顶点集随机划分的基础上,设计了一种寻求集合个数最少的独立集划分遗传算法.运行算法获得的独立集个数即为图的色数.算法引入了模块化函数思想,采用了单向传递交叉算子.通过贪婪局部优化初始种群和杂交后代个体,使算法具有较好的收敛速度.对四个经典算例的仿真结果表明,本文提出的算法可获得问题的高质量解,是一种有潜力的算法.     

图着色问题的新遗传算法

针对遗传算法求解图着色问题需多次产生初始种群的问题,提出了一种改进算法．该算法采用比较机制,淘汰不可行的基因,然后使用动态的适应度函数,使得有效个体以较大的概率存活到下一代种群中,从而达到无需多次产生初始种群的目的．与传统框架下的算法相比,新算法求得最优解的时间至少缩短了51％,且具有从一个局部最优解快速跳到下一个局部最优解,最终收敛到全局最优解的优点．     

基于微流控技术图顶点着色问题的DNA计算模型

为减少DNA计算中的人为操作,实现对生化操作的精确控制,设计了一种基于微流控技术求解图顶点着色问题的微流控DNA计算模型。通过温度来控制微反应器中DNA链库与磁珠探针的杂交与变性,并利用不同电极间的电位差来驱动DNA分子在微通道内移动以实现整个计算过程。分析表明,采用本文模型可以自动化地求解任意一个图顶点着色问题,提高了DNA计算的可靠性。     

n-太阳图的线图及全图的团覆盖数与团划分数

主要讨论ｎ－太阳图的线图及全图的团覆盖数和团划分数,得出了ｎ－太阳图的线图及全图的覆团盖数与团划分数相等且都是ｎ的倍数。     

k色图的连通性

研究和讨论了图的顶点着色问题中k色图的连通性,利用归纳与迭代的方法证明了对于任何k色连通图G,存在顶点V(G)的一个着色X1,X2,…,Xk,使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen,Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.     

平面测试问题的一种新型的神经网络算法

给出了平面测试问题的一种新型的神经网络算法。该算法不仅能够测试可平面图、寻找非平面的最大可平面子图，而且能够把一个可平面图嵌入在一条直线上。并通过实验验证了算法的可行性。这个算法可用于印刷板电路及大规模集成电路的布线。     

关于最大团问题的一种新算法

提出了关于最大团问题的一种新思路--基于平均度排序的局部枚举算法.对于一般的随机图G而言,图中含有最大团(d(G) 1)-团的概率要明显大于δ(G)-团或△-团.此算法通过了在随机图上进行实算的测试.实际计算结果表明:基于平均度排序的枚举算法比目前一般的基于枚举思想的算法更有效,其程序易于并行执行,值得进一步研究.     

用"遗传"算法求任意图的所有哈密顿回路

给出求解任意图所有哈密顿回路的“遗传”算法．首先,使用“继承”法,求完全图的所有哈密顿回路,既从Kk的哈密顿回路求Kk 1的哈密顿回路,直到Kn的哈密顿回路;然后,使用“选择”算法,将Kn中所有哈密顿回路在实际图中有不存在边的哈密顿回路去掉,最后得到任意图Gn的所有哈密顿回路,如果全部去掉,则该图不是哈密顿图．     

基于遗传算法的近似最大连通分量的抽取算法

提出了一种基于遗传算法的近似连通图的抽取算法，通过定义编码、种群初始化方法和交叉变异修正使得遗传算法可以解决最大连通分量的抽取问题．为验证该算法，将该算法与RACLIQUE进行了比较．实验结果表明本文提出的算法在解MCP问题时，执行的速度受节点规模变化小，效率优于RACLIQUE算法．     

整数距离图G（Dm，3）的点线性荫度

整数距离图G（D）以全体整数为顶点集，顶点u，v相邻当且仅当│u-v│∈D，其中D是一个正整数集．对于m〉3，设Dm，3={1，2，…，m│＼│3}，本文得到了G（Dm,3）的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值．