图顶点m着色的改进算法

《图顶点m着色的改进算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第14卷第3期天津理工学院学报V01．14No．31998年9月JOURNALOFTIANJININSTITUTEOFTECHNOLOGYSep．1998图顶点772着色的改进算法李文王哲明t／一刘林0

2、t摘要对于解决图顶点着色问题，目前较常使用DFS算法，而由于该算法存在效率不高问题，故提出DFS改进算法，极大提高了该算法的效率，对于较难的图顶点着色问题，利用该改进算法更为有利．关键词NP完全问题Christofides算法分娄"船叽·肴已圉点色ImprovedAlgorithmsOilhowtoP

3、utmColorsontheVertexesofChartsLiWenWangZheminLuLin(TianjinInsitituteofTechnologyTianiin300191)AbstractNowadays，thepopularmethodtotheproblemofhowtOputmcolorsonthevertexesofchartsisDFSalgorithm，butitisinefficient，andneedtobeimproved．Theimprovedalgorithmisgiv—en．Theimprovedonehas

4、moreadvantageinsolvingdifficultcoloringprobleminapplication．KeywordsNPcompleteproblemChristofidesalgorithmDFSalgorithmmaximumindependenceset1问题的提出图顶点着色问题是对一个Ⅳ顶点的图G(V，E)，用种颜色给图G中所有顶点，，⋯逐一着上m色中的一种颜色，并且使任两个相邻顶点异色．该问题是一个NP完全问题．对图顶点m着色问题抽象为一般组合模型，就是求出对应于，，⋯的一个元组X一(，，⋯)，其中．∈M，M一{1，2

5、．3，⋯，卅}，且X满足于给定的约束条件，BoundN(，一)，即对所有的，，11≤iJN，若与相邻，则Il≠．求解该问题的算法有两类：Christofides算法和DFS算法(回朔算法)r】]1．1Christofides算法1)用代数法求出G的所有极大独立集(7，7}，⋯)；2)对其中之一，1≤it≤^，求出G一的所有极大独立集(，，⋯7)i3)类似于步骤2)，可以求出一组极大独立集(，坪，⋯)，对应G的一种典型上色；若m，算法正常结束；否则，回步骤2，直至算法正常结束．Christofides算法，不易实现，并且计算代价高，故使用较少．1．2

6、DFS回溯算法：1)假设m种颜色对应M一{1，2，3，⋯m，；2)按递增选色序．首先确定．r的值，井按约束条件逐一确定．r一，≈一．的值．若在给IJ定值时找不到满足约束条件Boundj(，．r”≈一，IJ)的任一值，则回溯到上一层，给≈一重新定一满足Bound／(，一IJ·)的值．若I一的下一“合适”值存在，则向下试探；否则，再回朔．收稿日期：1998一O3—051；乍出生．jj}=师维普资讯http://www.cqvip.com60天津理工学院学报l4卷DFS回溯算法简单易行，常被人们使用．但该算法的效率较低，这是因为没有利用回溯过程的失败经验

7、．以下用图G中硬点3着色为倒说明．假设用DFS算法已给G的、，⋯逐～着上一种满足约束条件的颜色，现对着色，由于"19，着1色将与、⋯口的当前色“冲突”，。着2色将与、。的当前色“冲突”，着3色将与的当前色“冲突”，按照DFS，先调整的着色，再调整的着色，然后，试给着色，⋯⋯，这样，经过漫长的过程才能对的着色调整)．事实上，由于口，、、已分别着上1、2、3色，且与它们均相邻，若-、、．的着色不调整，，就无法选择一个合适的着色．而对、，、的反复调整全身无用功．这是DFS法的·大弱点0]，因而采用“智能”回溯策略取代DFS的逐层回期策略，实现多次回溯．y

8、-(3)围1圈G顶点着色的一种格局田2田G点着色的一十解(v1．v2⋯．vI为着色)(括号中的色表示颜色标号)2DFS的改进算法假定给定问题有个顶点．有m种色可选，并假定“智能回溯法按深度优先顺序逐一对-，．⋯试着色，这与DFS法相同，以下是实现方法．2．1定义经验矩阵并置初值定义经验矩阵E[1：N，1：m]，并将Eli，。]一，(1Ⅳ)，即E的第i行全置为i，这里E中单元E[，力意睬着顶点着色(1≤i≤N；1≤Jm)．2．2簿记经验每当顶点，是着J色(1≤i≤N；1J≤m)时，按下列公式将ED，力置相应值．i，可着j色．着j色，与k个顶点rain

9、{index('e11)，index(2)，⋯．index(vn)}lr着色“冲突”时，E[i，力(1ki—1)，(1r)