求顶点着色问题的一种新方法

《求顶点着色问题的一种新方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第l9卷第3期重庆工学院学报2005年3月Vo1．19No．3JournalofChongqingInstituteofTechnologyMar．2005【计算机与自动化】求顶点着色问题的一种新方法胡青龙，何军(1．西昌学院工程技术系，四川西昌615013；2．重庆师范大学经济与政治学院，重庆400047)ANewMethodofVerterColouringHUQing．1ong，HEJun(1．EngineeringDepartment，XiehangCollege，Xichang，

2、615013，China；2．DepartmentofEconomicsandPolitics，ChongqingNormalUniversity，Chongqing400047，China)Abstract：Thispaperputsforwardanewmethodofvertexcolouringofagraph，thatis，togetakindofsubdivision(V1，，⋯⋯)ofthevertexsetV(G)ofagraphG(i．e．，permutingitsrowandcor-respondingseries)

3、bymeansoftransformationofsimilitudeandpermutation．Keywords：Vertexcolouring；adjacentmatrix；permutationmatrix；directionadjointmatrix；lexico—graphicorder；partitionofavertexset1预备知识独立集，(G)的独立集分划(V，，⋯，)，最小覆盖数，根据团的定义及独立集与团的关系，还能对于图的顶点着色问题(仅考虑连通的简单得到其补图的最小团覆盖数(即色数)和最大团图)，人们关心的往

4、往是色数及最小着色问题等一(数)．些相关问题，文献[1]介绍了一种求色数及最小着定义1．1用n种颜色对图G的顶点进行着色的方法，但这种方法容易忽略一部分情况，实际色，且没有相异的邻接顶点着色相同，则称为G的上，我们可以对这种方法作一些改进，即若图的边—个n一顶点着色(n—vertexcolouring)，简称n一按某种方式收缩，得到三角形(或完全四边形着色．)，那么我们判断一下图中是否含有团Ks(或定义1．2使图G为n一着色的最小数值称为)，若有，则最小色数为3(或4)即可停止计算．G的色数(chromaticnumber)，记作(G)

5、．如果文献[2]介绍了另外一种用线性整数规划的方法(G)=n，则G为n一色的(n—colouring)．来求图的着色问题．下面笔者将介绍的是如何利从顶点着色的定义可以看出，具有任何一种用邻接矩阵置换行和相应的列(即置换相似变换)相同颜色的所有顶点集为图的独立集(indepent来求图的色数及最小着色，同时还可以得到最大set)，因此图G的一个n一着色，也就是把(G)分·收稿日期：2004．10．13作者简介：胡青龙(1966一)，男，四川仪陇人，副教授，主要从事运筹学及图论研究．维普资讯http://www.cqvip.com36重庆工

6、学院学报成个几个独立集的一个划分(，，⋯，)．关于=JBl，2=JB2⋯⋯。=，⋯≤+l，则称A≤B，图的着色问题，我们可以运用文献[1]第151页i=1，2，⋯，P．TH所给的方法求图G的色数，也可以利用线由前所知，对任意连通的简单图G，其邻接矩．：．性整数规划中的最小覆盖问题来求解．如果需要阵为A，都存在最小着色问题，也即存在图G的顶一个图G的非图形表示时(例如使用计算机时)，点集V(G)的一个划分(，，⋯，)．如果我们通常利用图的邻接矩阵来描述它的结构．下面给按(G)的划分中顶点顺序给图G重新标定，则可出它的定义：得到邻接矩阵A’

7、，且存在置换矩阵P，使得A=定义1．3设图G的顶点集(G)=(V1，，PAP，因此可以得到下述定理：⋯，)，令定理2．1设简单的连通图G，顶点集为f1，若与邻接(G)，邻接矩阵为A，图G的色数为n，V，，，⋯，，若与不邻接，或：y是图G的一种最小着色，其中y为独立集，i=则称元素0(i，=1，2，⋯，P)构成的P阶矩阵为1，2，⋯n，则若按，，，⋯，中顶点顺序重新标图的邻接矩阵(adjacentmatrix)，记作A(G)或记定图G，对应的邻接矩阵A’的形状如下：为A．0那么在不同的标定下，图的邻接矩阵之间有0什么关系呢?邻接矩阵的行与

8、列按相同的顶点次0序排列，置换行和相应的列，即重新安排顶点的次0序．如在邻接A中交换两行(同时交换相应的列)，那么图G。同构于图G：的充要条件为存在一个置其中0．为II阶零矩阵，空白处为1或0，i=1，换矩