[原创]图论法证明四色猜测

雷明85639720

[watermark]
图论法证明四色猜测
雷   明
（二○○八年六月一日）
任何一个图G都有一个顶点数最少的完全同态θ，θ中的各个顶点都是由G中的互不想邻的顶点同化而来，它代表着G中的若干个顶点，这若干个顶点在对G着色时着同一颜色是完全符合要求的。由于θ中的各顶点均是相邻的，所以给θ着色一定要用θ种颜色，那么给G着色，θ种颜色也就够了。把这个完全同态按对G同化时的反方向连同已着的颜色展开成图G，G的着色就算完成了。G中的相邻顶点绝不会用同一颜色。G的色数γ就等于θ的顶点数α，即
     γ＝α                                        （1）
因为G的完全同态θ的顶点数α是决不会少于G的密度ω的，即
     α≥ω                                        （2）
所以γ也不会小于ω的，又有
        γ≥ω                                        （3）
（3）式只是G着色时色数的下界，其上界是多少，就得看G的最小完全同态θ的顶点数α有没有上界和其上界是多少，即其上界又与ω是什么样的关系。
既然G的最小完全同态θ的顶点数α决不会小于其密度，那么就可以在G中选一个最大团Kω，把G中的其它顶点向这个最大团中同化，看最终得到的最小完全同态的顶点数α最大可能与G的密度ω又是一个什么关系。
图G中的任何一个单独顶点或任何一个单独的团都是可以同化到最大团中去的，关键的是道路中的顶点是不是都能同化到最大团中去。
1、单独道路向最大团的同化

单独道路和最大团的相邻关系最复杂的情况是：道路Pn（Pn是指由顶点1到n之间的且不通过最大团的一条最短的道路）的所有顶点都与最大团中的同一个Kω－2团中的各顶点均相邻，且道路的两个端点顶点又同时分别与最大团中的其它两个顶点之一相邻，即两端点顶点分别连接着最大团中的ω－1个顶点。如图1和图2（为了清晰，图中只画了一部分顶点和边，图中其它的顶点和边均未画出）。这种情况下，如果在其中再增加任何一条边，则G的密度就会增大，或者在道路中间又增加了一个与最大团有ω－1条边相邻的顶点，把道路分成了与上述道路有相同特点的两条道路，使其中之一就成了研究的对象。所以把在这种情况下的道路叫饱和道路，用PN表示。现在，问题已简化成了这条道路PN向一个K2团的同化了。
    （1）在图1中，当N是奇数时，PN中总有一个顶点同化不到K2团中去，也就是同化不到最大团中去，且每一个顶点都可成为这样的顶点；当N为偶数时，则可全部同化进去。
（2）在图2中，而当N是偶数时，PN中也总有一个顶点同化不到K2团中去，也就是同化不到最大团中去，且每一个顶点也都可成为这样的顶点；当N为奇数时，则可全部同化进去。
2、多条道路向最大团的同化
多条饱和道路间相邻关系最复杂的情况是S条道路两两间均有联存在，即这S条道路间有联存在（即任何一条道路中的任何一个顶点都和其他道路中的所有顶点均相邻）。联也是一个图，它也必然要有其密度值，已经知道联的密度等于构成它的各分子图的密度之和，而每条道路的密度都是2，所以由S条道路构成的联的密度值就是S 个2的和，即2S，也即这个联中的最大团是K2S，其顶点数是2S。由于该联只是图G中的一个分子图，所以它的密度2S也决不会大于原图G的密度，即有
        2S≤ω  或  S≤ω/ 2                          （4）
（4）式说明两两间均有联存在的饱和道路的条数是不会大于G的密度之半的。一条饱和道路有一个顶点不能同化到最大团中去，那么不大于G的密度之半的多条饱和道路同化不到最大团中去的顶点数最多一定是不会超过ω/ 2个的，这时，G的最小完全同态的顶点数总是不会大于其密度的一倍半的。即
        α≤1.5ω                                     （5）
（5）式就是G的最小完全同态θ顶点数α的上界，也是G 着色时色数γ的上界，即
        γ≤1.5ω                                     （6）
由于饱和道路的条数只能是整数，且还要受α不大于1.5ω的限制，所以还只能向下取整，这时又有
α≤<1.5ω>                                   （7）
和
        γ≤<1.5ω>                                   （8）
3、图顶点着色色数的界
把前面的式（3）和式（8）合写在一起，就得到任意图顶点着色时色数的界，即
    ω≤γ≤<1.5ω>                                （9）
式（9）就是任意图顶点着色色数的界。
4、四色猜测的证明
现在对四色猜测证明如下：
（1）平面图四色猜测的证明
已知平面图的密度决不会大于4，把一个个密度值代入（8）式，当ω＝1、2和3时，其色数γ都不大于4；而只有当ω＝4时，色数γ可以是4，也可以是5或6。但当γ＝5或6时，说明图中至少是有一条饱和道路的，但当有一条饱和道路出现时，这时的图就不再是平面图，而是非平面图了。如图3。很明显图中产生了交叉边，这是非平面图的特点（图中最大团K4各顶点旁的数字既是顶点序数，又是颜色种类，而道路PN各顶点下面的数字是顶点序数，顶点上面的数字则是所着颜色的种类）。看来当ω＝4时，色数γ恒等于4，即γ4≡4。图3中的四个图都是各有一条饱和道路的非平面图，有的用五种颜色，有的却仍只用四种，这是因为，道路的两个端点顶点与最大团的相邻关系不同，以及道路中顶点数的奇偶性的不同的原因，参见图1和图2的着色。

从以上的分析看，任何平面图顶点着色时，其色数都是不会大于4的。这就证明了平面图的四色猜测是正确的。
从图3的四个图还可以看出，尽管平面图的密度都不大于4，但却不能说密度不大于4的图一定都是平面图；尽管已证明了任何平面图顶点着色的色数都不大于4，但顶点着色的色数不大于4的图却也不一定都是平面图。以上图3中的四个图的密度都是4，但却都是非一平面图；图3中的b、c两图顶点着色的色数都是4，但却是地地道道的非平面图。还有K3，3图的密度是2，色数也是2，却也是一个典型的非平面图。所以说虽然平面图的密度和色数都不大于4，但密度和色数不大于4的图，却不一定都是平面图。“平面图的密度和色数都不大于4”的命题是不可逆的。
（2）地图四色猜出测的证明
地图是一个特殊的3—正则的平面图，其对偶图也是平面图，给地图的区划（面）上的染色，实质上也就是对其对偶图这个平面图的顶点着色，任何平面图顶点着色四种颜色够用了，那么任何地图染色时四种颜色也就够用了。这就证明了地图四色猜测也是证确的。
由于地图是一个3—正则的平面图，其对偶则是一个所有面均是3—圈的极大平面图。地图的偶图中任一个顶点所连的边数就是该顶点所代表的区划在地图中所相邻的区划数。给这个对偶图的顶点着色，就等于给这个地图的区划也着色了。


雷  明
二○○八年六月一日于金堆城

wangyangke

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想

lusishun

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想
老w辛苦了，装疯卖傻推销 的实际是


鲁思顺，陕西雷明轻松证明哥德巴赫猜想，

wangyangke

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想