赋权图的区间着色和图的着色算法

本文提出了图的区间着色模型,并对相容性图给出了区间着色的多项式算法,同时改进了求图的着色问题的算法。     

图着色问题的逆序蚁群算法研究

针对经典的图着色问题,依据传统图着色算法中逆序图着色的着色思想,结合蚁群算法的搜索机制,给出了逆序蚁群着色算法.根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点,使得算法具有较强的搜索全局最优解的能力.利用计算机生产大量随机图作为测试实例,对比逆序着色算法和逆序蚁群算法,实验结果说明逆序蚁群着色算法提高了求解质量,加快了收敛速度,证明了其优良特性.同时算法效率的提高,也保证了该算法可适用于较大规模的着色问题求解.此外,还进行了一系列对比试验,得出了关键参数的合理取值范围.     

图顶点m着色的改进算法

对于解决图顶点着色问题，目前较常使用ＤＦＳ算法，而由于该算法存在效率不高问题，故提出ＤＦＳ改进算法，极大提高了该算法的效率，对于较难的图顶点着色问题，利用该改进算法更为有利。     

区间图和强弦图的全着色及最优算法

证明对于任意区间图和强弦图－全着色猜想成立，并且给出了区间图和强弦图的最优线性地，其算法复杂度仅为Ｏ（Ｖ＋Ｅ）。     

基于遗传机制的图着色分配算法的研究

高层次综合中通过对冲突围着色方式把操作，变量值，数据传输映到共享资源中，然而寻找图着色所需的最小颜色数目是个ＮＰ难题，现将遗传算法与图着色分配算法有机结合在一起，提出了基于遗传机制的图着色分配算法，最后通过实验验证了该算法的有效性。     

修改一类G着色图的一个算法

给出了修改一类G着色图的一算法，并证明了通过第n次循环获得的G－V0的第n 1个着色图一定不同于前n个G－V0的着色图中的任何一个，和具有两个同一分支的连续循环过程不可能无休止地进行下去。     

解决图着色问题的膜进化算法

图着色问题是图论中比较热门的NP难问题之一。针对该问题,有许多启发式求解算法,但都存在求解的质量不高,计算时间较长等问题。近些年提出的膜进化算法,在处理NP难问题中展现出了独特的优势。基于膜进化算法框架,提出了解决图着色问题的膜进化算法,把图着色问题和膜结合,设计了复制、融合、分裂、溶解、融合分裂、禁忌搜索6种膜进化算子。这些算子在演变的过程中使膜和膜结构发生进化,从而找到更优解,最后求得解决方案。在DIMACS的40个挑战数据集上面进行了实验,与3个最新的图着色算法比较的结果表明：在保证解的质量的情况下,文中提出的膜进化算法能有效降低求解的时间,其中有58%的实例占优。     

对启发式算法实现图着色的优化

针对传统教科书中的图着色算法进行了分析研究,通过对算法执行步骤的跟踪分析,提出了两点改进方法,从而省去了大量的重复计算,大大提高了算法的效率.     

强边着色猜想问题的最优图

著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.     

关于边着色临界图的一个问题

H.P.Yap在[1]中提出这样一个问题,是否存在偶阶边着色8临界图,它除了有一个2度点和两个3度点外其余的都是8度点?作为本文定理推论的一个特殊情形给出了这个问题的否定性答案。     

蚁群优化图着色算法在智能小区中的运用

当智能小区的地图网格中的颜色数太多时,经蚁群算法处理的信息会出现杂乱无章的现象.对蚁群算法进行优化,增添褪色过程并加入参数Max,能减小并控制着色色数,实现四色着色,使得小区里的各种动态数据和信息在地图网格中更加清晰且直观地展现.     

Halin图的圈着色

对3连通图Halin 图,确定了其圈色数,并得到较好结果     

关于强边着色猜想的最优图问题

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.     

乘积图与正则图的满着色

图G=(V，E)的一个正常着色就是将G的顶点划分为独立集，或称之为色类，记为П=|V1，V2，…VK|．对于任一色类Vi中的点v，如果它与其余色类中至少一个点相邻，则”被称为是满色的．如果在一个正常着色中，所有点都是满色的，则称这样的着色是满着色．如果一个图存在满着色，定义图的满着色数为使得图存在满着色的最小颜色数，记为xf(G)．另外，记f(G)为使图存在满着色的最大颜色数．在这篇文章中，我们研究了一些乘积图的满着色，得出一些关于正则图的满着色的结果．     

Halin图的圈着色

对3－连通图Halin图，确定了其圈色数，并得到较好结果。     

一些图的星着色数

由A .Vince定义的星着色数推广了一般的着色数的定义 .关于星着色数 ,给出一些有用的结果 ,并且得到了满足 χ(G) =χ (G)的一些图集     

图的着色与分类

本文给出了两组新的４类子集簇,并给出几个距离集Ｄ是３类子集的充分条件。     

混合图的边着色

著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。     

关于图的非正常边着色

图Ｇ的非正常边着色，即（ｍ·ｄ）一边着色是把边集Ｅ（Ｇ）划分成ｍ个子集Ｅ１，Ｅ２，…，Ｅｍ，使得每一边子集的导出子图Ｇ〔Ｅｉ〕，ｉ＝１，２，…，ｍ的最大度最多是ｄ。Ｗｏｏｄａｌ问：对奇数ｄ和自然数ｍ，最大度是ｍｄ的第二类图中哪些是（ｍｄ）一边可着色的？哪些不是？本文对Ｗｏｏｄａｌ的这一公开问题给出了一些明确的解答。