超级军网由图着色问题论证NP=P
来源：百度文库 编辑：超级军网 时间：2024/04/27 16:29:15
由图着色问题论证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的着色方案也就确定了。
由图着色问题论证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的着色方案也就确定了。
这是我的原创论文，禁止转载。
看不懂，太高深
有错误，下面是终极修订版本。
由图着色问题论证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'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}。
证明：由色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——因为这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路——而对角线上值相同的元素色数相关，可用一种颜色；对角
线上值不相同的元素色数无关，必须用不同颜色。由于H'在对角
线上有α1个各异的正元素，有α2个各异的负元素，则G必要且
只要max{α1，α2}种颜色给顶点着色，就可使G中任意两个相邻
顶点着色不同，即G的顶点色数s（G）=max{α1，α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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。
----------
我会上传图片和视频到网上，图着色问题很简单，高中生也能做（如魔方）。
由图着色问题论证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'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}。
证明：由色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——因为这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路——而对角线上值相同的元素色数相关，可用一种颜色；对角
线上值不相同的元素色数无关，必须用不同颜色。由于H'在对角
线上有α1个各异的正元素，有α2个各异的负元素，则G必要且
只要max{α1，α2}种颜色给顶点着色，就可使G中任意两个相邻
顶点着色不同，即G的顶点色数s（G）=max{α1，α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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。
----------
我会上传图片和视频到网上，图着色问题很简单，高中生也能做（如魔方）。
更正：“G的顶点色数s（G）=α=max{α1，α2}”应为“G的顶点色数s（G）=α=max{α1，α2}+2”。
上面的好多要修改和补充。如下：
由图着色问题论证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进行初等行、列变换如下
循环部分
/ 如果矩阵中存在至少3行（列），满足每行（列）至少有两
个非0元素，设有aik≠0，ajk≠0，i≠k，i≠j
1≤i、j、k≤n，且aik＝λajk
则令rj-λri（第j行减去第i行的λ倍。
即对1≤k≤n，做减法运算“ajk-λaik”）
cj-λci（第j列减去第i列的λ倍。
即对1≤k≤n，做减法运算“akj-λaki”）
如果矩阵只存在2行（列），满足每行（列）至少有两
个非0元素——此时每行（列）只会有两个非0元素，
且每行有一个是对角线上的元素，设有aii≠0，ajj≠0，
aij≠0，i≠j，1≤i、j≤n，且aij＝λaii
则令rj-λri，
cj-λci
/
判断部分
/ 如果方阵中每行（列）最多只有一个非0元素，将所得方
阵记为H'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个值各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}+2。
证明：
由矩阵理论可知α1个各异的正元素，α2个各异的负元素是H的
不同的特征值，每个值对应一个特征向量。结合图的定义与性质，
色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——即这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路，要用不同的颜色。
而对角线上值相同的元素是矩阵H'的相同的特征值，即色数相
关，可用同一种颜色；对角线上值不相同的元素对应H'的不同的特
征值，它们色数无关，必须用不同颜色；而正负号不同的特征值表
明它们也是色数相关的。由于H'在对角线上有α1个各异的正元素，
有α2个各异的负元素，则G必要且只要max{α1，α2}+2种颜色
给顶点着色，就可使G中任意两个相邻顶点着色不同，即G的顶点
色数s（G）=max{α1，α2}+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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。
由图着色问题论证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进行初等行、列变换如下
循环部分
/ 如果矩阵中存在至少3行（列），满足每行（列）至少有两
个非0元素，设有aik≠0，ajk≠0，i≠k，i≠j
1≤i、j、k≤n，且aik＝λajk
则令rj-λri（第j行减去第i行的λ倍。
即对1≤k≤n，做减法运算“ajk-λaik”）
cj-λci（第j列减去第i列的λ倍。
即对1≤k≤n，做减法运算“akj-λaki”）
如果矩阵只存在2行（列），满足每行（列）至少有两
个非0元素——此时每行（列）只会有两个非0元素，
且每行有一个是对角线上的元素，设有aii≠0，ajj≠0，
aij≠0，i≠j，1≤i、j≤n，且aij＝λaii
则令rj-λri，
cj-λci
/
判断部分
/ 如果方阵中每行（列）最多只有一个非0元素，将所得方
阵记为H'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个值各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}+2。
证明：
由矩阵理论可知α1个各异的正元素，α2个各异的负元素是H的
不同的特征值，每个值对应一个特征向量。结合图的定义与性质，
色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——即这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路，要用不同的颜色。
而对角线上值相同的元素是矩阵H'的相同的特征值，即色数相
关，可用同一种颜色；对角线上值不相同的元素对应H'的不同的特
征值，它们色数无关，必须用不同颜色；而正负号不同的特征值表
明它们也是色数相关的。由于H'在对角线上有α1个各异的正元素，
有α2个各异的负元素，则G必要且只要max{α1，α2}+2种颜色
给顶点着色，就可使G中任意两个相邻顶点着色不同，即G的顶点
色数s（G）=max{α1，α2}+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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。
晕死，还有小错误。不再回复了，本帖到此为止。
------------------------------
最后一版本
由图着色问题论证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进行初等行、列变换如下
循环部分
/ 如果矩阵中存在至少3行（列），满足每行（列）至少有两
个非0元素，设有aik≠0，ajk≠0，i≠k，i≠j
1≤i、j、k≤n，且ajk＝λaik
则令rj-λri（第j行减去第i行的λ倍。
即对1≤k≤n，做减法运算“ajk-λaik”）
cj-λci（第j列减去第i列的λ倍。
即对1≤k≤n，做减法运算“akj-λaki”）
如果矩阵只存在2行（列），满足每行（列）至少有两
个非0元素——此时每行（列）只会有两个非0元素，
且每行有一个是对角线上的元素，设有aii≠0，ajj≠0，
aij≠0，i≠j，1≤i、j≤n，且aij＝λaii
则令rj-λri，
cj-λci
/
判断部分
/ 如果方阵中每行（列）最多只有一个非0元素，将所得方
阵记为H'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个值各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}+2。
证明：
由矩阵理论可知α1个各异的正元素，α2个各异的负元素是H的
不同的特征值，每个值对应一个特征向量。结合图的定义与性质，
色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——即这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路，要用不同的颜色。
而对角线上值相同的元素是矩阵H'的相同的特征值，即色数相
关，可用同一种颜色；对角线上值不相同的元素对应H'的不同的特
征值，它们色数无关，必须用不同颜色；而正负号不同的特征值表
明它们也是色数相关的。由于H'在对角线上有α1个各异的正元素，
有α2个各异的负元素，则G必要且只要max{α1，α2}+2种颜色
给顶点着色，就可使G中任意两个相邻顶点着色不同，即G的顶点
色数s（G）=max{α1，α2}+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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。
------------------------------
最后一版本
由图着色问题论证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进行初等行、列变换如下
循环部分
/ 如果矩阵中存在至少3行（列），满足每行（列）至少有两
个非0元素，设有aik≠0，ajk≠0，i≠k，i≠j
1≤i、j、k≤n，且ajk＝λaik
则令rj-λri（第j行减去第i行的λ倍。
即对1≤k≤n，做减法运算“ajk-λaik”）
cj-λci（第j列减去第i列的λ倍。
即对1≤k≤n，做减法运算“akj-λaki”）
如果矩阵只存在2行（列），满足每行（列）至少有两
个非0元素——此时每行（列）只会有两个非0元素，
且每行有一个是对角线上的元素，设有aii≠0，ajj≠0，
aij≠0，i≠j，1≤i、j≤n，且aij＝λaii
则令rj-λri，
cj-λci
/
判断部分
/ 如果方阵中每行（列）最多只有一个非0元素，将所得方
阵记为H'，称为G的对应方阵，结束；否则，返回循环部分
/
由矩阵理论知，经过有限步之后，H可以转换为H'。
显然H'也是对称方阵。易知H'在对角线（aii）之外有非0元
素。如果H'在对角线上有非0元素，且其中有α1个值各异的正元
素（即每个元素的值都是正数且互不相同），有α2个值各异的
负元素，则G的顶点色数s（G）=α=max{α1，α2}+2。
证明：
由矩阵理论可知α1个各异的正元素，α2个各异的负元素是H的
不同的特征值，每个值对应一个特征向量。结合图的定义与性质，
色数无关的概念、性质可知，H'元素aij≠0（i≠j）
对应的顶点vi、vj必须用2种颜色着色。而对角线上的每个非0元
素不能被对角线上0元素所在的行（列）线性表达——即这些
顶点与非对角线上的非0元素对应顶点的集合的导出子图有奇回
路，要用不同的颜色。
而对角线上值相同的元素是矩阵H'的相同的特征值，即色数相
关，可用同一种颜色；对角线上值不相同的元素对应H'的不同的特
征值，它们色数无关，必须用不同颜色；而正负号不同的特征值表
明它们也是色数相关的。由于H'在对角线上有α1个各异的正元素，
有α2个各异的负元素，则G必要且只要max{α1，α2}+2种颜色
给顶点着色，就可使G中任意两个相邻顶点着色不同，即G的顶点
色数s（G）=max{α1，α2}+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的顶点色数为α=max{α1，α2}。如
果G不是完全α分图，则我们可添加一条边得图G'，G'对应的方
阵H''可能有两种情形——
（1）由H''知G'的顶点色数为α，则该边可添加；
（2）由H''知G'的顶点色数为α，则该边不可添加。
由于G的阶数为n，则经过不超过[n（n-1）/2]次尝试加边之后，我
们就可以得到包含G的完全α分图，G的着色方案也就确定了。