健壮性图着色问题算法及科学应用.doc

健壮性图着色问题算法及应用中山大学硕士学位论文健壮性图着色问题算法及应用姓名:莫瑜申请学位级别:硕士专业:计算机软件与理论指导教师:郭嵩山20060501摘要Problem―RGCP是经典图着色问健壮性图着色问题RobustGraphColoring题的一种新的扩展,它在许多领域有广泛应用。本论文提出了一个求解小规模数据RGCP的精确解算法。通过改进已有邻域结构,优化了大规模数据RGCP近似解算法。新的基于局部搜索的近似算法,在解质量和时问效率方面都优于已有算法。进一步地,刽‘对区问图的健壮性图着色问题,利用罚分潜在的约束,本文提出若干新的算法。壤后,还将健壮性图着色问题算法应用到飞机场调度问题中。关键字:健壮性图着色问题,区nj|J图,局部搜索,飞机场调度问题ABSTRACTtraditionalTheanewvariantoftheRGCPRobustGraphColoringproblemisinhasnumerousrealworld(Problem(ItpracticalapplicationsGCPGraphColoringisinthisAnexactforRGCPofsmallpaper(Also,algorithmgraphspresentedtheheuristicthethisstructure,andexistingneighborhoodoptimizespaperimprovesresultsofthenewlocalforRGCPofsolvinglargegraphs(Theexperimentalgorithmarebetterthanthecurrentthehiddensearchones(Furthermore,plementaryedgesgraphs,manypenaltywillbeusethenewforRGCPoftheintervalalgorithmsgraphpresented(Finally,wetosolvetheRGCPairportassignmentproblem(algorithmGraph,LocalSearch,AirportAssignmentKeywords:RobustGraphColoring,IntervalProblem11引言健壮性图着色问题RobustGraphColoringProblem(ROCP是经典图着色问题GraphColoringProblem(GCP的扩展。严格地说,本文讨论的着色问题都是点着色VertexColoring,区别于边着色EdgeColoring。顾名思义,就是给图的顶点一种可行的颜色方案,使其满足某种约束。经典的图着色问题,要求着色方案必须保证相邻的两个顶点具有不同的颜色。图着色问题的研究被广泛应用到实际问题中。随着应用的深入,实际的问题提出了新的约束:着色方案不但要保证相邻的顶点具有不同的颜色,还要对不相邻的顶点之间可能相邻的约束加以考虑。我们把满足这种加强的约束需求称为着色方案的健壮性,因而引出的新的问题,也就是健壮性图着色问题。第1章(简介图着色问题在增加健壮性考虑之后,扩展为健壮性图着色问题。在第2章中,我们介绍经典的图着色问题。进而从图着色问题的应用出发,引出健壮性图着色问题。从中我们可以看到研究健壮性图着色问题“与生俱来”的应用意义。最后,总结健壮性图着色问题的研究现状。plete的,但对于规模比较小的图,还是希望能够求出它的最优解。第3章提出一个跟色多项式求解思路类似搜索算法。它可以使用点着色数的下界进行剪枝,提高了RGCP精确解搜索算法的效率。在第4章中,讨论当图的规模增大的时候,求解,般图RGCP的近似算法。针对之前算法存在的不足进行了改进,并比较改进前后算法的计算结果。我们可以发现很多实际应用中的图都是区间图,因而希望能找到充分利用区间图特点的RGCP算法。在第6章中,证明了单单依靠区间图本身拓扑结构上的特殊性并不能简化RGCP算法。虽然如此,通过利用区间图上罚分的一些约束假设,本文提出了一系列的针对区间图的RGCP算法。第7章中,前面讨论的RGCP算法被应用到飞机场调度问题中。最后,第8章中,总结全文,并提出不足之处和以后改进的方向。第2章(问题描述2(1图着色问题在讨论健壮性图着色问题之前,我们先看看经典的图着色问题的定义图着色问题GraphColoringProblem(ocP给定一个图G矿,E,找出最如果能用C种颜色给图G的顶点着色,称对图G进行了c(着色,也称G是c(可着色的。若图G是c(可着色的,但不是c(11一可着色的,称图G是c(***。umber,记为zGc。也就是说,点着色数za是可行着色方案需要的最少颜色数。图着色问题中最小整数C就是图G的点着色数zG1。plete的。目