图论法证明四色猜测的思想方法(原件)

雷明85639720

雷明85639720

                        图论法证明四色猜测的思想方法
                                  雷  明
    1、图顶点着色是把相邻的顶点用不同的颜色区分开来，而不相邻的顶点则是可以着以相同颜色的。而图中不相邻的顶点是可以通过图的一种运算——不相邻顶点间的同化（或叫凝缩），同化为一个顶点。这就把顶点着色与同化联系起来了；
    2、每个图都有一个最大的团，在团中的各顶点均是两两相邻的，这个最大团的顶点数就是图的密度。不同的图的最根本区别就是其密度的不同；
    3、任一个图顶点同化的最终结果将是一个再不能进行同化的完全图，因为完全图的顶点均是两两相邻的。这个完全图叫做该图的完全同态。由于同化时的路线、方法的不同，同化后得到的结果也可能不同，即可得到顶点数不同的多个完全同态。把顶点数最少的那个完全同态叫做该图的最小完全同态；
    4、由于图都有自已的最大团，所以图的最小完全同态的顶点数决不会少于其最大团的顶点数。对这个最小完全同态各顶点着色，其数色一定是不会小于图的密度的，这是图顶点着色色数的下界。把这个已着色的完全同态的各顶点，连同各顶点的已着的颜色一起返回到原图时，一个图的顶点着色就完成了，所用的颜色总数一定是最少的，且保证了相邻的顶点不用同一种颜色；
    5、图的最小完全同态的每一个顶点，都代表着原图中某些互不相邻的顶点，它着某种颜色就说明了它所代表的那些互不相邻的顶点都可着这种颜色。完全同态用了几种颜色，这个图的色数就是几；
    6、有下界就也必有上界，图顶点着色色数的上界是多少，这要对图的同化研究后才能确定。通过研究可以得到图顶点同化的最小完全同态顶点数的上界（也即图顶点着色色数的上界）是不大于图密度的1.5倍（这个研究到必要的时候我是会发表的）；
    7、通过研究，得到任意图顶点着色色数的界是：其色数是大于等于图的密度，而小于等于图的密度的1.5倍。
    8、平面图的密度不大于4，把平面图的四种密度一个一个的代入到任意图顶点着色色数的界中，就能得到任何平面图顶点着色的色数是不会大于4的。这里要强调指出的是，按照图顶点着色色数的界，密度为4的图的色数会出现5和6（因为5和6都不大于4的1.5倍），但在这种情况下，图的密度虽然是4，但图已不再是平面图了，而成为非平面图，因为其中出现了交叉边；
    9、地图是一种特殊的平面图，它的对偶图也是平面图，任何平面图顶点着色的色数不大于4，那么任何地图染色时的色数也就不会大于4。
    10、具体平面图的色数
    密度是1的图（孤立顶点）的色数一定是1；密度是2的图的色数是2（图中不含奇圈）或3（图中含有奇圈）；图密度是3的图的色数是3（图中不含奇轮）或4（图中含有奇轮）。以上三种密度小于4的图全都是平面图。密度是4的图有两种情况，当图是平面图时的色数一定是4；而只有当图是非平面图时的色数才可能是大于4。
    到此，就证明了平面图的四色猜测是正确的，地图四色猜测也是正确的。

                                  （雷明2008年4月9日于金堆城）

wangyangke

论坛没有靠得住的哥猜证明，确有一些靠得住的二百五，，，鲁思顺是二百五中的突出代表，，，