文档介绍：维普资讯
第卷第期重庆工学院学报年月
. . .
【计算机与自动化】
求顶点着色问题的一种新方法
胡青龙,何军
.西昌学院工程技术系,四川西昌;.重庆师范大学经济与政治学院,重庆

.,
.,,,,;
.,,,
:,,
, ,⋯⋯..,
.
:;; ;;—
;
预备知识独立集,的独立集分划, ,⋯, ,最小
覆盖数,根据团的定义及独立集与团的关系,还能
对于图的顶点着色问题仅考虑连通的简单得到其补图的最小团覆盖数即色数和最大团
图,人们关心的往往是色数及最小着色问题等一数.
些相关问题,文献介绍了一种求色数及最小着定义. 用种颜色对图的顶点进行着
色的方法,但这种方法容易忽略一部分情况,实际色,且没有相异的邻接顶点着色相同,则称为的
上,我们可以对这种方法作一些改进,即若图的边—个一顶点着色—,简称一
按某种方式收缩,得到三角形或完全四边形着色.
,那么我们判断一下图中是否含有团或定义. 使图为一着色的最小数值称为
,若有,则最小色数为或即可停止计算. 的色数,
文献介绍了另外一种用线性整数规划的方法,则为一色的—.
,具有任何一种
用邻接矩阵置换行和相应的列即置换相似变换相同颜色的所有顶点集为图的独立集
来求图的色数及最小着色,同时还可以得到最大,因此图的一个一着色,也就是把分
· 收稿日期:..
作者简介:胡青龙一,男,四川仪陇人,副教授,主要从事运筹学及图论研究.
维普资讯
重庆工学院学报
成个几个独立集的一个划分, ,⋯, .关于,⋯⋯。,⋯≤,则称≤,
图的着色问题,我们可以运用文献第页,,⋯,.

. :. 所给的方法求图的色数,也可以利用线由前所知,对任意连通的简单图,其邻接矩
,都存在最小着色问题,也即存在图的顶
一个图的非图形表示时例如使用计算机时, 点集的一个划分, ,⋯, .如果我们
,则可
出它的定义: 得到邻接矩阵’,且存在置换矩阵,使得
定义. 设图的顶点集, , ,因此可以得到下述定理:
⋯
, ,令定理. 设简单的连通图,顶点集为
, 若与邻接,邻接矩阵为,图的色数为,,, ,⋯,
, 若与不邻接,或: 是图的一种最小着色,其中为独立集,
则称元素,,,⋯,构成的阶矩阵为,,⋯,则若按,, ,⋯, 中顶点顺序重新标
图的邻接矩阵,记作或记定图,对应的邻接矩阵’的形状如下:
为.
那么在不同的标定下,图的邻接矩阵之间有
什么关系呢邻接矩阵的行与列按相同的顶点次

序排列,置换行和相应的列,即重新安排顶点的次

,
那么图。同构于图:,空白处为或,,
换矩阵使:.事实上由于邻,⋯,,,元的上边和左边的元素均
接矩阵是由标定图做出的,若。和:是同一个图为,,⋯,.且存在置换矩阵,使得
的两种不同标定下的邻接矩阵,则必存