由图着色问题论证NP=P
江西省余江二中 胡
设G=（V,E）是简单无向图，假设至少需要r种差别的颜色给G的顶点着色，就能使得G中
肆意两个不相邻的顶点着色差别，则称G的顶点色数s（G）=r。
确定肆意一个简单无向图的顶点色数的问题，我们称为图着色问题。
若简单无向图G的顶点色数为r，则能够在G上添加若干条边（即毗连G中不相邻的顶点），
使得有限次后得到完全r分图G'。
但是，给定一个简单无向图，添加某些边之后所得图的顶点色数稳定；而有一些边，添加
肆意一条城市改动图的顶点色数——顶点色数增加1。
定义（对点） 设G是简单无向图，s（G）=r，va、vb是G中两个不相邻的顶点，若关于
G的肆意一种r着色计划，va、vb的着色都不不异，则称va是vb的对点（vb是va的对点），va、
vb互为对点。
例 长度为4的道路（v1v2v3v4v5），顶点色数为2。v3、v5都是v1的对点，添加边
（v1，v3）或（v1，v5）之后所得图有奇回路，顶点色数为3。
在矩阵理论中，有个概念喊“线性无关”，是说一个向量不克不及由另一组向量线性表达。
连系图论，我立马领略了：图的邻接矩阵蕴含了一个重要的性量：色数无关。
对G的某个子图G1=（V1，E1），设s（G1）=r'，G1往掉顶点vx（及其所有联系关系边）之后
得到图G2=（V2，E2），若s（G2）=r'-1，则称vx与顶点集V2色数无关——即对G1的肆意一种
r'着色计划，若V2中的顶点用了（r'-1）种颜色，则vx必需用第r'种颜色才气使G1的肆意两个
相邻顶点上色差别。
定理1 设G=（V,E）是n阶简单无向连通图，H=(aij)（1≤i、j≤n）是G的邻接矩阵。
显然H是n阶实对称方阵。
对H停止初等行、列变更如下
轮回部门
/ 假设aik≠0，ajk≠0，1≤i、j≤n，i≠j，且aik＝λajk
则令rj-λri（第j行减往第i行的λ倍。即对1≤k≤n，做减法运算“ajk-λaik”）
cj-λci（第j列减往第i列的λ倍。即对1≤k≤n，做减法运算“akj-λaki”）
/ 假设方阵中每行（列）最多只要一个非0元素，将所得方阵记为H'，完毕；不然，
返回轮回部门
由矩阵理论知，颠末有限步之后，H能够转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元素。设H'在对角线上有α个正元
素（即大于0的元素），则G的顶点色数s（G）=（α+2）。
证明：由色数无关的概念、性量可知，H'元素aij≠0（i≠j）顶点vi、vj必需用2种颜色着
色。而对角线上的每个非0元素不克不及被其它行（列）线性表达，认为着那些顶点与非对角线上的
非0元素对应顶点的聚集的导出子图有奇回路——但是对角线上的负元素与其它顶点色数相关，
固然会增加一些奇回路但不会增加顶点色数，而对角线上的正元素与其它顶点色数无关，必需
别的用一种颜色。因为H'在对角线上有α个正元素，则G需要且只要（α+2）种颜色给顶点着
色，就可使G中肆意两个相邻顶点着色差别，即G的顶点色数s（G）=（α+2）。证毕。
定理2 设G=（V,E）是n阶简单无向图，则确定G能否连通图的计算冗杂度不超
过O（n^3）——应该在O（n^2）以下。对G的每个连通分收图，按上面的办法确定顶点色数，
计算冗杂度不超越O（n^5）。因而，图着色问题是多项式时间问题。又图着色问题是NP完全
问题，所以NP=P。
用上述办法，我们很随便对n阶简单无向连通图G=（V,E）着色：由G的对应方阵H'晓得G
的顶点色数为（α+2）。假设G不是完全（α+2）分图，则我们可添加一条边得图G'，G'对应
的方阵H''可能有两种情况——
（1）由H''知G'的顶点色数为（α+2），则该边可添加；
（2）由H''知G'的顶点色数为（α+3），则该边不成添加。
因为G的阶数为n，则颠末不超越[n（n-1）/2]次测验考试加边之后，我们就能够得到包罗G
的完全（α+2）分图，G的着色计划也就确定了。