3着色问题的多项式时间算法

3着色问题的多项式时间算法
江西省余江二中   胡
摘要   对任意n阶简单无向图G=（V，E），本文找到了一个算法，
可以在n的多项式时间内判定G的顶点是否可3着色，即表明了3着
色问题是多项式时间问题。又3着色问题是NP完全问题，则NP=P。

    定义（可约图）  设G=（V,E）是简单无向图，va是G的一个
顶点。若G中有顶点vb满足：vb到va的距离为2，且va的邻点集是
vb的邻点集的子集，则称G是可约图；否则称G是不可约图。

    定义（可缩并图） 设G=（V,E）是简单无向图，G不存在K4子
图（G的任意4阶子图都不是完全图）。若G存在4阶子图，该子图的
边数为5，则称G是可缩并图；否则称G是不可缩并图。
     设G=（V,E）是n阶可缩并图，V1={va,vb,vc,vd}是V的子集，
V1在G中的导出子图的边数为5，且该子图不包含边（va，vb）（即
va、vb在G中不相邻）。将G中的va、vb用一个顶点vx代替得到
图G'——即在G上去掉顶点va、vb及其所有关联边，添加一个新的顶
点vx，vx的所有关联边是且只是G中va、vb的关联边，称G'为G的缩
并图。

我们可以发现，以下性质是显然的。
    性质1 设G=（V,E）是n阶简单无向图，n≥4，则有：
            （1）判断G是否存在K4子图（4阶完全图的子图）只需
                   n的多项式时间；
            （2）判断G是否可约图只需多项式时间；
            （3）判断G是否可缩并图只需多项式时间；
            （4）判断G是否连通只需多项式时间。
以上四项是分类进行的，复杂度不超过它们中的最高级的。

　　定理1 设G=（V,E）是n阶简单无向连通图，G不存在K4子图，
但存在奇回路；G是不可约图、是不可缩并图，且G去掉任意边之后仍
然连通。则存在算法，对G的邻接矩阵H进行初等变换之后得到n阶对
称方阵H'（称之为G的色数矩阵），满足：
（1）H'的每行、每列最多只有一个非0元素；
（2）G的色数为3的充要条件是H'的对角线上最多只有一个不同的
正元素（即元素的值为正数），最多只有一个不同的负元素。
算法如下
    初始化：输入G的邻接矩阵H
    步骤一、如果矩阵的每行、每列最多只有一个非0元素，则将
            所得矩阵纪为H'，称为G的色数矩阵，输出，结束；
            否则，转步骤二。
    步骤二、1.  如果矩阵存在第i行ri，满足ri上只有一个非0元素
            aij，i≠j；且第j列cj上至少有两个非0元素，则对
            akj≠0，k≠i,且akj=λaij,做运算
                    rk-λri（第k行减去第i行的λ倍。
                    即对1≤t≤n，做减法运算“akt-λait”）
                    ck-λci（第k列减去第i列的λ倍。
                    即对1≤t≤n，做减法运算“ajt-λajt”）
            返回步骤一
            2.  如果对1≤i≤n，矩阵第i行ri只有一个非0元素
                 aij的同时，矩阵的第j列也只有一个非0元素aji，
                 则矩阵存在至少两行（列），满足每行（列）至
                 少有两个非0元素。
            2.1  如果矩阵存在第i行ri至少有两个非0元素，且
                 aii≠0,
                 设有aij=aji≠0，akj≠0，k≠i，且akj=λaij，
                 (1)若k=j，做运算
                     rk-0.5λri
                     ck-0.5λci
                 (2)若k≠j,做运算
                     rk-λri
                     ck-λci
                  返回步骤一
            2.2.1   如果对1≤i≤n，矩阵第i行ri至少有两个非0元素，
                  有aii≠0。且存在aii≠0，ajj≠0，aij≠0，满足
                  Λ=4（aij^2-aii*ajj）≥0，做运算
                      rj-λri
                      cj-λci{其中λ=[2aij+(Λ)^0.5]/2aii}
                   返回步骤一
             2.2.2  如果对1≤i≤n，矩阵第i行ri至少有两个非0元素，
                  有aii≠0。且对任意1≤i、j≤n，如果aii≠0，
                  ajj≠0，aij≠0，都有Λ=4（aij^2-aii*ajj）＜0，
                   做运算
                      rj-λri
                      cj-λci{其中λ=aij/aii}
                   返回步骤一
下面证明：由H'可知G的色数。
　　由矩阵理论知，经过有限步之后，H可以转换为H'。
　　显然H'也是实对称方阵。易知H'在对角线（aii）之外有非0元
素。
　　定义（对点） 设G是简单无向图，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的任意两个相邻顶点上色不同。
    由矩阵理论及色数无关的概念、性质可知，H'元素aij≠0
（i≠j）对应的顶点vi、vj必须用2种颜色着色。而对角线上的
每个非0元素不能被对角线上0元素所在的行（列）线性表达——
因为这些顶点与非对角线上的非0元素对应顶点的集合的导出子图
有奇回路——而对角线上值相同的元素色数相关，可用一种颜色；
对角线上值不相同的元素色数无关，必须用不同颜色。若G的色数
为3，则H'的对角线上最多只有一个不同的正元素（即元素的值为
正数），最多只有一个不同的负元素；反之亦然。证毕。
　　定理2 设G=（V,E）是n阶简单无向图，则确定G是否存在
K4子图、是否可约及是否连通图的计算复杂度不超过O（n^3）
——应该在O（n^2）以下。
对G的每个连通分支图，检验去掉任意边是否仍然连通的计算复杂度
也不超过O（n^3），再按上面的方法确定顶点色数，计算复杂度
不超过O（n^5）。因此，3着色问题是多项式时间问题。又3着色
问题是NP完全问题，所以NP=P。
3着色问题的多项式时间算法
江西省余江二中   胡
摘要   对任意n阶简单无向图G=（V，E），本文找到了一个算法，
可以在n的多项式时间内判定G的顶点是否可3着色，即表明了3着
色问题是多项式时间问题。又3着色问题是NP完全问题，则NP=P。

    定义（可约图）  设G=（V,E）是简单无向图，va是G的一个
顶点。若G中有顶点vb满足：vb到va的距离为2，且va的邻点集是
vb的邻点集的子集，则称G是可约图；否则称G是不可约图。

    定义（可缩并图） 设G=（V,E）是简单无向图，G不存在K4子
图（G的任意4阶子图都不是完全图）。若G存在4阶子图，该子图的
边数为5，则称G是可缩并图；否则称G是不可缩并图。
     设G=（V,E）是n阶可缩并图，V1={va,vb,vc,vd}是V的子集，
V1在G中的导出子图的边数为5，且该子图不包含边（va，vb）（即
va、vb在G中不相邻）。将G中的va、vb用一个顶点vx代替得到
图G'——即在G上去掉顶点va、vb及其所有关联边，添加一个新的顶
点vx，vx的所有关联边是且只是G中va、vb的关联边，称G'为G的缩
并图。

我们可以发现，以下性质是显然的。
    性质1 设G=（V,E）是n阶简单无向图，n≥4，则有：
            （1）判断G是否存在K4子图（4阶完全图的子图）只需
                   n的多项式时间；
            （2）判断G是否可约图只需多项式时间；
            （3）判断G是否可缩并图只需多项式时间；
            （4）判断G是否连通只需多项式时间。
以上四项是分类进行的，复杂度不超过它们中的最高级的。

　　定理1 设G=（V,E）是n阶简单无向连通图，G不存在K4子图，
但存在奇回路；G是不可约图、是不可缩并图，且G去掉任意边之后仍
然连通。则存在算法，对G的邻接矩阵H进行初等变换之后得到n阶对
称方阵H'（称之为G的色数矩阵），满足：
（1）H'的每行、每列最多只有一个非0元素；
（2）G的色数为3的充要条件是H'的对角线上最多只有一个不同的
正元素（即元素的值为正数），最多只有一个不同的负元素。
算法如下
    初始化：输入G的邻接矩阵H
    步骤一、如果矩阵的每行、每列最多只有一个非0元素，则将
            所得矩阵纪为H'，称为G的色数矩阵，输出，结束；
            否则，转步骤二。
    步骤二、1.  如果矩阵存在第i行ri，满足ri上只有一个非0元素
            aij，i≠j；且第j列cj上至少有两个非0元素，则对
            akj≠0，k≠i,且akj=λaij,做运算
                    rk-λri（第k行减去第i行的λ倍。
                    即对1≤t≤n，做减法运算“akt-λait”）
                    ck-λci（第k列减去第i列的λ倍。
                    即对1≤t≤n，做减法运算“ajt-λajt”）
            返回步骤一
            2.  如果对1≤i≤n，矩阵第i行ri只有一个非0元素
                 aij的同时，矩阵的第j列也只有一个非0元素aji，
                 则矩阵存在至少两行（列），满足每行（列）至
                 少有两个非0元素。
            2.1  如果矩阵存在第i行ri至少有两个非0元素，且
                 aii≠0,
                 设有aij=aji≠0，akj≠0，k≠i，且akj=λaij，
                 (1)若k=j，做运算
                     rk-0.5λri
                     ck-0.5λci
                 (2)若k≠j,做运算
                     rk-λri
                     ck-λci
                  返回步骤一
            2.2.1   如果对1≤i≤n，矩阵第i行ri至少有两个非0元素，
                  有aii≠0。且存在aii≠0，ajj≠0，aij≠0，满足
                  Λ=4（aij^2-aii*ajj）≥0，做运算
                      rj-λri
                      cj-λci{其中λ=[2aij+(Λ)^0.5]/2aii}
                   返回步骤一
             2.2.2  如果对1≤i≤n，矩阵第i行ri至少有两个非0元素，
                  有aii≠0。且对任意1≤i、j≤n，如果aii≠0，
                  ajj≠0，aij≠0，都有Λ=4（aij^2-aii*ajj）＜0，
                   做运算
                      rj-λri
                      cj-λci{其中λ=aij/aii}
                   返回步骤一
下面证明：由H'可知G的色数。
　　由矩阵理论知，经过有限步之后，H可以转换为H'。
　　显然H'也是实对称方阵。易知H'在对角线（aii）之外有非0元
素。
　　定义（对点） 设G是简单无向图，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的任意两个相邻顶点上色不同。
    由矩阵理论及色数无关的概念、性质可知，H'元素aij≠0
（i≠j）对应的顶点vi、vj必须用2种颜色着色。而对角线上的
每个非0元素不能被对角线上0元素所在的行（列）线性表达——
因为这些顶点与非对角线上的非0元素对应顶点的集合的导出子图
有奇回路——而对角线上值相同的元素色数相关，可用一种颜色；
对角线上值不相同的元素色数无关，必须用不同颜色。若G的色数
为3，则H'的对角线上最多只有一个不同的正元素（即元素的值为
正数），最多只有一个不同的负元素；反之亦然。证毕。
　　定理2 设G=（V,E）是n阶简单无向图，则确定G是否存在
K4子图、是否可约及是否连通图的计算复杂度不超过O（n^3）
——应该在O（n^2）以下。
对G的每个连通分支图，检验去掉任意边是否仍然连通的计算复杂度
也不超过O（n^3），再按上面的方法确定顶点色数，计算复杂度
不超过O（n^5）。因此，3着色问题是多项式时间问题。又3着色
问题是NP完全问题，所以NP=P。