[原创]我研究四色问题的四篇论文

雷明85639720

[watermark]


我研究四色问题的四篇论文
雷  明
1、我解决四色问题的主导思想
2、任意图顶点着色色数的界
3、赫渥特地图着色公式的由来
4、5—轮构形是可约的
二○一二年八月十二日•长安修改
一、我解决四色问题的主导思想
雷  明
（二○一二年五月六日，八月十二日修改）
关键词：总体  共性  个体  个性  
摘  要：阐明了笔者不用着色的方法证明四色猜测的思路。
由于图的多样性，无限性，不可能把所有的图都画完，也不可能对所有的图都进行着色，所以就不可能用着色的方法对四色猜测进行证明。而只能走不画图，不着色的道路。本人解决四色问题的主导思想是：从图论入手，专门研究图的结构参数，找出图的着色数与图的某些结构参数之间的关系，从而对猜测进行了证明。
1、先从图的总体出发：
1、1  总体及图的共性
1、1、1  总体——任意图：包括平面图与非平面图。
1、1、2  图的共性——图的密度：图中至少都有一个最大的团，该团的顶点数就是图的密度。
1、2  图的几种运算：
1、2、1  顶点着色——给图中各顶点着以不同的颜色，使得相邻的顶点不用同一种颜色，但不相邻的顶点却不一定非得要用相同颜色。
1、2、2  顶独立集划分——把图中各顶点分配到不同的集合内，使得相邻的顶点不在同一个集合里，但不相邻的顶点却不一定非得分配到同一个集合里去。
1、2、3  图的完全同态——把不相邻的顶点凝结成一个顶点，使图最后变成一个完全图，这就是图的完全同态。看来相邻顶点是不能凝结在一起的，但不相邻的顶点却不一定非得要凝结到一起。把不相邻的顶点凝结在一起的过程叫做“同化”运算。
1、3  与运算对应的几种参数：
1、3、1  色数——图顶点顶点着色时所用的最少颜色数。
1、3、2  最小顶独立集数——对图在进行顶独立集划分时所得到的最少的顶独立集的个数。
1、3、3  最小完全同态的顶点数——在对图进行顶点同化时最终所得到的顶点数最少的那个完全同态的顶点数。
1、4  几种参数的关系：
从以上几种运算的定义看，上面的几种参数应该是相等的，即有
色数＝最小顶独立集数＝最小完全同态的顶点数
    最小完全同态中的每一个顶点均代表着图中若干个不相邻的顶点，而不相邻的顶点在一起所构成的集合就是图的顶独立集。同一顶独立集内的顶点均是不相邻的，所以着同一颜色是符合要求的，那么最小完全同态有多少个顶点，该图的最小顶独立集数就是多少，一个顶独立集用一种颜色，有多少个顶独立集，该图着色时就得用多少种颜色，这就是图的色数。
1、5  求几种参数的方法：
1、5、1  求色数——着色，但图的种类多种多样，一至无穷，无法把所有图都着色完。
1、5、2  求最小顶独立集数——抽屉法，即把每个顶点向不同的抽屉里放置，使相邻的顶点不在同一个抽屉之内，同样也无法把所有图都分配完。
1、5、3  求最小完全同态的顶点数——用“同化”的方法。所谓同化，就是把不相邻的顶点凝结在一起的过程，使其变成一个顶点。可以不用具体的图，只用一个能代表总体形象的、具有一般意义的图。理论上，任何图通过同化运算，最后都可以得到一个顶点数最少的完全同态，这就是图的最小完全同态。任意图的最小完全同态的顶点数与图的密度的关系是：大于等于图的密度而小于等于图的密度的一倍半向下取整的值（这里的密度是指图中最大团的顶点数）。
由于图的色数＝最小顶独立集数＝最小完全同态的顶点数，所以图的最小顶独立集数与色数也都是大于等于图的密度而小于等于图的密度的一倍半向下取整的值。这就是任意图的色数的界。
由于图的密度可以是无穷大的，所以对于任意的图来说，这是一个无穷的问题。
2、 再到对个体图的检验：
2、1  个体——平面图，即亏格为0的图。这种图是能够嵌入到球面（或平面，其亏格也是0）上的图。
2、2  共性中的个性：由于平面图的密度都不大于4，所以这就把一个对密度来说的无穷问题变成了一个有穷的问题了。
2、3  把平面图的四种密度，一个个的代入到任意图的色数的界中去，就得到了任何平面图顶点着色时的色数总不大于4的结论。这也就证明了四色猜测是正确的。
雷  明
二○一二年七月二十三日于长安
    注：该文已于二○一二年五月九日在《数学中国》网上发表。

二、任意图顶点着色色数的界
——四色猜测证明方法之一
雷  明
（二○一二年六月十七日，八月十二日修改）
关键词：图  着色  顶独立集  完全同态  同化  四色猜测
摘  要：不对任何图进行着色，可以证明四色猜测是正确的。
1、几个概念
1、1  图是由顶点与某些顶点间的连线（边）所构成的集合。有边相连的两顶点叫相邻顶点。
1、2  图顶点的着色：给图的顶点着以不同的颜色，使得相邻的顶点不着同一颜色。这里的关键是相邻顶点不能着同一颜色。图中所用的最少颜色数叫做该图顶点着色的色数，用γ表示。
1、3  顶独立集划分：把图中的顶点划分到不同的集合内，使得相邻的顶点不被划分到同一个顶独立集内。这里的关键也是相邻顶点不能划分在同一个独立集内。一个图所能划分出的最少的顶独立集的个数，叫做该图的最小顶独立集数，用β表示。注意，这里的“顶独立集数”是顶独立集的个数，不同于图论中用某顶独立集内的顶点数所定义的“顶独立数”。
1、4  图的同化运算：把图中不相邻的顶点，凝结为一个顶点的过程叫图顶点的同化。这里的关键也是相邻顶点不能同化到一起去。每同化一次所得到的图，叫做图的一个同态，一个图经若干次同化后，最终得到的结果一定是一个完全图，这叫做图的完全同态。其中顶点数最少的那一个完全同态就叫某图的最小完全同态。最小完全同态的顶点数用α表示。
1、5  从以上的几个概念可以看出：
图顶点着色的色数γ
＝图的最小顶独立集数β
＝图的最小完全同态Kα的顶点数α
最小完全同态中的每一个顶点均代表着图中若干个不相邻的顶点，而不相邻的顶点在一起所构成的集合就是图的顶独立集。同一顶独立集内的顶点均是不相邻的，所以着同一颜色是符合要求的，那么最小完全同态有多少个顶点，该图的最小顶独立集数就是多少，一个顶独立集用一种颜色，有多少个顶独立集，该图着色时就得用多少种颜色，这就是图的色数。
由于图中的最大团Kω中的各个顶点均是两两相邻的，不可能再进行同化，所以最小完全同态的顶点数α一定不会小于图的密度ω（图的密度就是图中最大团Kω的顶点数），所以又有
γ＝β＝α≥ω                          （1）
这就是任意图顶点着色色数的下界。
2、任意图顶点着色色数的界
请看下面两个图的同化过程。这两个图都不是具体的图。图中最大团Kω外的一条道路Pn的每一个顶点都与最大团Kω中未画出的那ω－2个顶点相邻（相邻的边在图中也未画出），道路的两个端点顶点又与最大团中剩余的那个K2团的两个顶点相邻。若在这条道路与最大团间再任增加一条边，将会导致图的密度发生变化（或者道路就会变成两条具有上述性质的道路，道路的长度就会变短），所以把这样的道路就叫做“饱和道路”。

图1中，在饱和道路Pn中，当n为奇数时，Pn中总有一个顶点同化不到最大团Kω中去，且Pn中的每一个顶点都可成为这样的不可同化顶点；否则当n为偶数时，Pn中的所有顶点都可全部同化到最大团Kω中去。图2 中，则是在饱和道路Pn中，当n为偶数时，Pn中也总有一个顶点同化不到最大团Kω中去，同样的，Pn中的每一个顶点都可成为这样的不可同化顶点；否则当n为奇数时，Pn中的所有顶点也都可以全部同化到最大团Kω中去。
由此可以从道路与最大团的相邻关系方面对道路进行分类如下：
1、非饱和道路，可以证明该道路中的所有顶点都一定可以同化到最大团中去；
    2、饱和道路，在道路与某一最大团间增加任一条边时，图的密度就会增大，或者路道就会变成两条较短的饱和道路。以上图1和图2 中的道路就是饱和道路。该类道路又可分为两类：
1、可同化道路，这种道路中的各个顶点都是可以同化到最大团中去的；
2、不可同化道路，这种道路上总有一个顶点同化不到最大团中去。
还可以证明，当不可同化道路是回路（圈）时，同样也有与以上两图的两种情况完全相同的结论。同样也可以证明当图1和图2中的Pn不是不可同化道路或饱和道路时，Pn中的所有顶点也都是一定能够同化到最大团中去的。
如果有S条不可同化道路，且这S条道路构成了联时,就有S个顶点同化不到最大团中去，这S个顶点因其本来在联中就是相邻的，不可再同化在一起，所以就有图的最小完全同态Kα的顶点数α＝ω＋S。
由于联的密度是构成联的各个分子图密度的和，又因为道路的密度是2,所以该联的密度是就2S。这个联又只是图的一个分子图，其密度一定不会大于图的密度，所以又有2S≤ω,即S≤ω/2。又因为不可同化道路的条数S必须是整数，所以对S还要向下取整，即又有
       S≤                 （2）
因此就有图的最小完全同态的顶点数的界是：
ω≤α≤ω＋S＝              （3）
因此又有
ω≤γ＝β＝α≤              （4）
γ＝β＝α≤ 就是任意图顶点着色色数的上界。因此又有任意图顶点着色色数的界是
ω≤γ≤                     （5）
3、四色猜测的证明
3、1  平面图四色猜测的证明
由于平面图的密度都不大于4，所以这就使得公式（5）ω≤γ≤ 对于图的密度ω来说的无穷问题就变成了一个有穷的问题了。
把平面图的密度从1到4一个个的代入到以上的任意图顶点着色色数的界中，就可得到任何平面图的色数都不会大于4，即有
γ平面图≤4                  （6）
当图的度是4时，从公式（5）中可以看出，其色数有可能是4，5，6三种可能，而当色数大于4时，尽管图的密度还是是4，但这种图就已经不再是平面图了（证明略）。
奇圈中的每一个K2团外都有一条不可同化道路，所以圈的密度虽是2，但奇圈的色数却是3，等于ω＋1；同样的，奇轮中的每一个K3团外也都有一条不可同化道路，所以轮的密度虽是3，但奇轮的色数却是4，也等于ω＋1。
由此可以得出：含有奇轮的平面图的色数一定是4，密度为4的含有K4团（3—轮，是奇轮）的图也是属于含奇轮的图；不含奇轮但只含有偶轮的图的色数则是3。不含轮而含有奇圈的平面图的数色一定是3，密度为3的含有K3团（3—圈，是奇圈）的图也是属于含奇圈的图；不含奇圈但只含有偶圈和树的图的色数则是2。不含圈和树的图全是孤立顶点，1种颜色就够用了。
这就证明了平面图的四色猜测是正确的。
3、2  地图四色猜测的证明
地图也是一种平面图（是特殊的3—正则平面图，各顶点的度均是3），给其面上的染色就相当于给其对偶图（也是一种特殊的极大平面图,各面均是3—边形面）的顶点着色。由于平面图的对偶图仍是平面图，又因为平面图的顶点着色四种颜色够用了，所以地图染色时四种颜色也就够用了。
这也就证明了地图染色的四色猜测也是正确的。
4、图值函数顶点着色色数的界
有了任意图顶点着色色数的界，研究图的线色数、全色数以及图的任何图值函数的色数就方便得多了。
比如线图的密度等于原图中的最大度Δ，所以图的线色数就是其线图顶点着色的色数，其界是
Δ≤γ线≤                 （7）
这就是1964年V•G•Vizing给出的线色数的界，但公式（7）比其更加完善。当时V•G•Vizing给出的线色数的界是Δ≤γ线≤Δ＋1,且只有在Δ等于2和3 时才是正确的。
又比如全图的密度等于原图中的最大度Δ加1,所以图的全色数就是其全图顶点着色的色数，其界是
Δ＋1≤γ全≤               （8）
这也就是1965年Behzad提出的全色数的猜想，同样公式（8）也比其更加完善。当时Behzad提出的全色数的猜想是Δ＋1≤γ全≤Δ＋2，也只是在Δ等于2 和3时才是正确的。
若给一个图G,其图值函数为f（G），f（G）的密度ωf（G）是与图G的有关参数有关的函数（如ω线＝Δ原图等），则图值函数f（G）的顶点着色色数的界是
   ωf（G）≤γf（G）≤    （9）
以上的线图和全图都是原图的图值函数，其色数（也就是原图的线色数和全色数）就是这样得来的。
由于平面图的对偶图也是原图的图值函数，给平面图的面上的着色就相当于对其对偶图的顶点着色，因其对偶图仍是一个平面图，所以平面图（原图）的面色数也是
γ平面图面色数≤4           （10）
地图着色也是给平面图（地图本身就是一个3—正则的平面图）的面的着色，所以这也就证明了地图的四色猜测也是正确的。
5、结论：四色猜测是正确的
本文没有对任何一个具体的图着色，只从图的色数等于图的最小完全同态的顶点数着手，得出了最小完全同态的顶点数与图的密度间的关系，进而得到任意图顶点着色色数的界，把平面图的密度不大于4的特点代入其中，就得到了任何平面图着色的色数都不大于4的结论，从而也就证明了四色猜测是正确的。
雷  明
二○一二年七月二十三日于长安
注：该文已于二○一二年六月十九日在《数学中国》网上发表过。

三、赫渥特地图着色公式的由来
——四色猜测证明方法之二
雷  明
（二○一二年六月二十日，八月十二日修改）
关键词：赫渥特  着色  四色猜测
摘  要：从适合于亏格为0的多阶曲面上的欧拉公式直接推导出了赫渥特的地图着色公式，该公式在曲面的亏格为0 时的值是小于等于4的，这也就证明了四色猜测是正确的。
1、赫渥特一生研究四色问题共六十年，虽发表过许多优秀的论文，但却没有最终解决这一问题。虽然如此，但他却得出了一个比四色问题更高级的、更丰富多彩的适合于任意亏格的多阶曲面上的地图着色公式γn≤ ，也正是因为他认为自已没有解决亏格为n＝0时的平面（或球面）上的四色问题，所以他给他的公式后面附加了条件n＞0。
2、在现有所能看到的文献资料中，在提到该公式时，也都只是引用了一下，并没有说明这个公式是如何得来的。也正是因为公式后有了附加条件n＞0，所以就成了一些人认为的“尽管公式中当n＝0时公式的值γ≤4,也不能说明四色猜测是正确的”的理由。这个公式当时赫渥特是如何得来的，我们不得而知，但我坚信总是有其由来的，只是我们一般的人看不到而已。要把该公式的由来弄明白那就是研究数学史的专家们的事了。
3、我们虽然不知道赫渥特地图着色公式的由来，但我们可以通过适合于任意曲面的多阶曲面上的欧拉公式推导出这一公式。
多阶曲面上的欧拉公式是v＋f－e＝2（1－n），其中的n是图的亏格，也是图所能嵌入的最小曲面的亏格，而v、f、e分别是曲面上图的顶点数、面数和边数。当亏格n＝0时，公式就成为v＋f－e＝2，这就是我们经常见到的平面图的欧拉公式。我们知道完全图Kv的边数是e＝ ，且完全图中的任何两两顶点都是相邻的，所以e和f也有3f＝2e的关系，即f＝ 。
先把f＝ 代入多阶曲面上的欧拉公式v＋f－e＝2（1－n）中，并整理后得到
3v＝e＋6－6n
再把e＝ 代入到上式3v＝e＋6－6n中，整理后得到
        v2－7v＋12（1－n）＝0
这是一个关于完全图的顶点数v的一元二次方程。解这个一元二次方程得
    v1＝
   v2＝
  由于在v2＝ 中，当n≥1时，v2＝ ≤0，而任何图的顶点数都是不会小于1的，v≤0显然是不符合题意的，所以舍去不要。则该一元二次方程也只有一个根v1＝ 。因为图的顶点数必须是整数，所以该根还得向下取整，得
   v＝
由于任何完全图的色数γ就等于其顶点数v，所以把v＝ 中的顶点数v换成某亏格下的色数γn，就得到
    γn＝
这只是完全图的色数γn与其亏格n之间的关系。由于在同亏格条件下，同顶点数的图中完全图的边数是最多的，顶点间的相邻关系也是最复杂的，当然其色数也一定是最多的，而同顶点数的任一非完全图的色数都是要小于完全图的色数的，所以还要把上式中的等号改换成不等号，则变成
    γn≤
这就是任意图顶点着色的色数与其亏格的关系，也就是我们在文章最开头所说的赫渥特在1890年得出的多阶曲面上的地图着色公式。
显然这个公式中，当亏格n＝0时，γn≤4，这就是平面（球面）上的四色猜测。同样，当亏格n＝1时，γn≤7，这是轮胎面（环面）上的色数；当亏格n＝2时，γn≤8，这是眼镜匡面（双环面）上的色数，等等等等。这显然比一个四色猜测要更显得丰富多彩。
4、为什么有些人死报着赫渥特原来公式中的附加条件n＞0不放，而硬说该公式对于亏格为n＝0的平面（球面）不适用呢，可能是因为他们还不认为赫渥特的图是4—可着色的，也可能是他们没有看到过赫渥特地图着色公式最开始时的由来，还有可能是因为他们不会从多阶曲面上的欧拉公式直接推导出赫渥特的地图着色公式的原因吧。
雷  明
二○一二年七月二十三日于长安
    注：此文已于二○一二年六月二十日在《数学中国》网上发表过。

四、5—轮构形是可约的
——四色猜测证明方法之三
雷  明
（二○一二年六月二十日，八月十二日修改）
关键词：图  四色猜测  构形  不可避免  可约的
摘  要：仍然使用坎泊的颜色交换技术，证明了5—轮构形是可约的，从而再次证明了四色猜测是正确的。
由于任何平面图中至少有一个顶点的度是小于等于5的，所以平面图的不可避免集中只可能有6种元素，即0—轮（即K1图），1—轮（即K2图）,2—轮（即2—重K3图），3—轮（即K4图）,4—轮和5—轮六种构形。
这六种构形中，0—轮构形的色数是1, 1—轮构形的色数是2, 2—轮构形的色数是3, 3—轮构形的色数是4，都是小于等于4的，这几种构形都是可约的；4—轮构形坎泊早已证明是可约的；而5—轮构形，坎泊在未把各种情况都考虑周全的情况下，就根据前面证明的4—轮构形是可约的而认为5—轮构形也是可约的。在这种情况下他就认为并宣布了他证明了四色猜测是正确的。
可是在十一年后，赫渥特构造了一个图，其中就有一个5—轮的中心顶点未着上其他顶点已用过的四种颜色之一，认为该图是不可约的。当时坎泊也不能将其中未着色的顶点着上赫渥特已用过的四种颜色之一。直到现在已有一百五十多年了，整个数学界还认为5—轮构形仍是不可约的。赫渥特的图真是不能4—着色吗，5—轮构形真是不可约的吗，不是的。现在就证明如下。
1、按赫渥特着色中所用的颜色交换方法继续交换下去，再进行别的链的交换后，仍是可以对赫渥特构造的图进行4—着色的，国内已有不少的人已进行过这一工作，也的确说明了赫渥特的图是可以4—着色的。目前在数学界，可能再也没有人认为赫渥特的图是不可4—着色的了。
2、把赫渥特图中的关键顶点留下，而把其它的顶点去掉，就得到一个9点形，这就是一个5—轮构形，如图1。
由于图1中的b—g链和b—y链是在顶点2 和顶点8相交了两次的连通链，交换两次关于r的链r—g和r—y是不可能同时移去两个r的，即v也是不能着上图中已用过的r色的。如何办，只能想办法首先把连通的链变成不连通或者把交叉的链变成不交叉的。然后想办法移去5—轮周围只用过一次的一种颜色给v着上。

3、可以看出，对图1从b—g链和b—y链的交叉点顶点8（或顶点2）进行b—r链的交换后，既可做到使两链变得不连通，又可使两链变得不相交（如图2）,然后再任意进行一次关于非r链（或非b链）的交换，即可空出图中已用过的四种颜色之一给v着上。5—轮构形是可约的。
4、对于赫渥特的图，按照上面2、3两步的方法去做，立即可使赫渥特图中的未着色顶点着上赫渥特已用过的四种颜色之一。赫渥特图也是4—可着色的。
5、现在已经证明了平面图的6种不可避免构形都是可约的，那么平面图的四色猜测也就得到了明是正确的。
6、地图是一种3—正则（各顶点的度均是3）的平面图，面上的着色就是给其对偶图的顶点着色，因其对偶图也是一种极大（各个面均是3—边形面）的平面图，所以任何地图的色数也一定是小于等于4的。这也就证明了地图四色猜测是正确的。
7、平面图的不可避免构型只有六种，这是人所共知的，因为任何平面图中不可避免的都会至少存在一个顶点的度小于等于5。1976年阿贝尔的验证，却避开了5—轮构形，用了一个什么叫双5—轮的所谓的“构形”来替代，这分明还是没有证明5—轮道底是否是可约的嘛。所谓的又5—轮构形实际上就是图1中的那种构形，张彧典在他的文章《与〈阿贝尔—哈根证明四色定理〉商榷》一文中也指出了这一点。当给双5—轮中的一个未着色顶点着上颜色后，这不还是一个5—轮构形嘛。既然阿贝尔验证了双5—轮是可约的，那不也等于说5—轮构形也是可约的了吗，难道你不是一个顶点一个顶点的着色吗。本来已经证明了5—轮是可约的，但就是不敢承认那就是对5—轮的着色，这不是怪事吗。阿贝尔用了两千个构形，再多一些又有什么用呢，难道能因为你着色的图越多就能说明你证明了四猜是正确的吗。这是一种穷举的笨办法。是对计算机资源的极大浪费。5—轮构形没有证明是否可约，就想办法证明它就行了，却硬是要避开它，绕开矛盾走，无穷的在穷举，这是不科学的态度。为什么不再多举一些呢，你能举完吗。本来是一个有穷的问题，却人为的硬要把它变成一个无穷的问题了。
雷  明
二○一二年七月二十三日于长安
注：此文已于二○一二年六月二十日在《数学中国》网上发表过。