论图的顶点色数，及闲聊NP问题

论图的顶点色数，及闲聊NP问题
江西省余江二中
摘要 本文找到了一种方法，可以确定简单无向图的顶点色数。

定义（对点） 设G(V,E)是简单无向连通图，G的顶点色数记为χ（G）=r，v1、v2是G的两个顶点，若
对G的任意一种顶点r着色方法，v1、v2着色都相同，则称v1、v2为对点。

定理1 设G(V,E)是简单无向连通图，则可以运用算法在G上添加若干条边，从而得到无向连通图
G'(V,E')，满足：
（1）G'的任意两个顶点的距离不大于2；
（2）G'与G的顶点色数的差不大于1。
证明：算法如下：
令G1（V,E1）=G（V,E）
For i≥1
若Gi（V,Ei）存在顶点va、vb距离为3
令Gi+1（V,Ei+1）=Gi（V,Ei∪{(va,vb)}）
若Gi（V,Ei）的任意两个顶点的距离不大于2，
令G'(V,E')=Gi（V,Ei）
设G的顶点色数为χ（G）=r，G'的顶点色数为χ（G'）=r'，显然r'≥r。
若算法添加的所有边的两个端点在G中都不是对点，则r'=r。若算法加的某些边的两个端点在G中是对点，
则G'中不存在对点，即r'=r+1。

定理2 设G(V,E)是简单无向连通图，G的任意两个顶点的距离不大于2，且G的每个顶点的度都大于3，
V1是G的一个极大独立点集，G去掉V1（及V1中所有顶点的所有边）得到图G',则有
（1）G'的任意两个顶点的距离不大于2；
（2）χ（G）=χ（G'）+1。
注：若G存在度为2的点，则应这样找极大独立点集：先选取度为2的极大独立点集，再任意选取其它的点。

由定理1和定理2，对任意简单无向连通图G,可以通过算法得到G',使得G'与G的顶点色数的差不大于1；且
可以取出G'的k（k≥0）个独立点集而得到G''，使得G''的每个顶点的度都不大于2，且有χ（G'）=χ（G''）+k；而G''的顶点色数不大于3，从而可以确定G'的顶点色数；最后验证G'比G多加的边中是否有边的端点在G中是对点（我估计这个验证过程是多项式算法、但没仔细研究），就可以确定G的准确的顶点色数了。

个人认为，NP问题取决于它的二级结构。什么是二级结构呢？我目前有这个想法，但还没有清楚的概念，
或许是谓词，或许是别的。

我没有时间！！！论图的顶点色数，及闲聊NP问题
江西省余江二中
摘要 本文找到了一种方法，可以确定简单无向图的顶点色数。

定义（对点） 设G(V,E)是简单无向连通图，G的顶点色数记为χ（G）=r，v1、v2是G的两个顶点，若
对G的任意一种顶点r着色方法，v1、v2着色都相同，则称v1、v2为对点。

定理1 设G(V,E)是简单无向连通图，则可以运用算法在G上添加若干条边，从而得到无向连通图
G'(V,E')，满足：
（1）G'的任意两个顶点的距离不大于2；
（2）G'与G的顶点色数的差不大于1。
证明：算法如下：
令G1（V,E1）=G（V,E）
For i≥1
若Gi（V,Ei）存在顶点va、vb距离为3
令Gi+1（V,Ei+1）=Gi（V,Ei∪{(va,vb)}）
若Gi（V,Ei）的任意两个顶点的距离不大于2，
令G'(V,E')=Gi（V,Ei）
设G的顶点色数为χ（G）=r，G'的顶点色数为χ（G'）=r'，显然r'≥r。
若算法添加的所有边的两个端点在G中都不是对点，则r'=r。若算法加的某些边的两个端点在G中是对点，
则G'中不存在对点，即r'=r+1。

定理2 设G(V,E)是简单无向连通图，G的任意两个顶点的距离不大于2，且G的每个顶点的度都大于3，
V1是G的一个极大独立点集，G去掉V1（及V1中所有顶点的所有边）得到图G',则有
（1）G'的任意两个顶点的距离不大于2；
（2）χ（G）=χ（G'）+1。
注：若G存在度为2的点，则应这样找极大独立点集：先选取度为2的极大独立点集，再任意选取其它的点。

由定理1和定理2，对任意简单无向连通图G,可以通过算法得到G',使得G'与G的顶点色数的差不大于1；且
可以取出G'的k（k≥0）个独立点集而得到G''，使得G''的每个顶点的度都不大于2，且有χ（G'）=χ（G''）+k；而G''的顶点色数不大于3，从而可以确定G'的顶点色数；最后验证G'比G多加的边中是否有边的端点在G中是对点（我估计这个验证过程是多项式算法、但没仔细研究），就可以确定G的准确的顶点色数了。

个人认为，NP问题取决于它的二级结构。什么是二级结构呢？我目前有这个想法，但还没有清楚的概念，
或许是谓词，或许是别的。

我没有时间！！！