[原创]我在网上发表的第一编论文

雷明85639720

[watermark]

我在网上发表的第一篇
有关证明四色猜测的论文
雷  明
（二○一○年三月二十日）
这里我把我于1999年在《业余数学天地》网的《百家争鸣》栏目上发表的有关用图论方证明四色猜测的论文《用图论与集论的方法对四色猜测的证明》全文抄录如下：
用图论与集论的方法
对四色猜测的证明
雷  明
（ 一九九九年四月 ）
摘  要：用图论与集论方法证明了四色猜测是证确的，不需用对任何图进行着色。
关键词：四色猜测、图、平面图、地图、着色、色数、同化、同态、完全同态、最小完全同态、团、       最大团、图的密度、图值函数
本人是一个业余数学爱好者，从一九八五年起就开始对四色问题进行研究至今，取得了一定的进展。望数学“大师”们不要看不起“小人物”，抽出一定时间一阅，或许是有所获益的。
在对四色猜测进行证明之前，先要求出任意图顶点着色色数的界。
1  任意图顶点着色色数的界
1．1  图顶点着色与同化的关系
图着色时不相邻的顶点可着同一颜色，而图同化时不相邻的顶点也可同化为成一个顶点。把一个图一步步同化可得到一系列的同态，最后可得到一个完全同态。由于不同的人同化的方法及途径不同，在所得到的完全同态中总有一个顶点数是最少的，这就是被同化的图的最小完全同态。
1．2   任意图顶点着色色数的界
1．2．1   图顶点着色色数的下界
任何一个图中一定存在着一个最大团，其顶点数就是图的密度。由于最大团就是图中一个再不能同化（压缩）的最小集团，所以任何一个图在同化时的最小完全同态的顶点数决不会少于其最大团的顶点数。若用ω代表最大团Kω的顶点数，用a代表最小完全同态的顶点数，则有
a ≮ ω或a ≥ ω                                        （1）
给这个最小完全同态着色，必须要用a种颜色，然后再按着色时的相反方向把已着色的图展开成原来的图，则原图就着色成功，全图只用了a种颜色。若把任意图顶点着色的色数用γ来代表，则有
              γ＝a ≥ ω                                               （2）
（2）式就是任意图顶点着色色数的下界。
1．2．2   最大团外的顶点向最大团的同化
从（1）式中可以看出，图顶点着色时一定存在着色数大于密度的情况，现在就先来看一下在什么情况下会有这种情况发生。先选定一个最大团，把该最大团外的其他顶点都向这个最大团中进行同化。
1．2．2．1   最大团外一个顶点向最大团的同化
若用d代表任何一个顶点与最大团中相邻接顶点的数目，则d一定小于图的密度ω，即
d ＜ ω                                                  （3）
否则图的密度就不再是ω而是ω＋1了。可见，最大团外的任何一个单个顶点都是可以同化到最大团中去的，因为最大团中至少还有一个顶点可以让这个顶点同化进来。
1．2．2．2  最大团外一个团Km向最大团的同化
用Km（ｍ＜ω）表示最大团外的一个团，由于d1∩d2∩……∩dm的顶点数一定是小于等于ω－m的（否则图的密度也就会大于ω），即
d1∩d2∩……∩dm≤ω－m                                （4）
这个交集内的顶点构成的团与最大团的关系是：
Kd1∩Kd2∩……∩Kdm≤ Kω－m∈Kω                         （5）
加上有（3）式d＜ω的这个条件，最大团外的这个团Km中的m个顶点都是可以同化到最大团中去的，那么这个团Km也就同化到了最大团中去了。
1．2．2．3   最大团外的道路Pn向最大团的同化
图中有各种各样的道路，这里我们把两个端点顶点与最大团中相邻接顶点的数目都等于ω－1之间的道路作为研究的对象，即该道路的d1＝ω－1，dn＝ω－1。由于道路是由首尾相结的若干个K2团构成的，每个K2团最多只可能与最大团中的ω－2个顶点相邻接，所以这里分开d1∩d2∩……∩dn小于ω－2和d1∩d2∩……∩dn等于ω－2两面种情况来进行研究。
1．2．2．3．1     d1∩d2∩……∩dn＜ω－2，即Kd1∩Kd2∩……∩Kdn＜Kω－2∈Kω
这种情况下的任何道路中的所有顶点都是可以同化到最大团中去的，即这种道路是可以同化到最大团中去的。因为任何K2团向Kω中同化时，Kω中至少要有两个顶点不同时与K2团中的两个顶点相邻接，而现在是要多于两个顶点的，所以Pn中的所有顶点是一定可以同化到Kω中去的。
1．2．2．3．2     d1∩d2∩……∩dn＝ω－2，即Kd1∩kd2∩……∩Kdn＝Kω－2∈Kω
这种情况，问题的实质就变成Pn中各顶点向Kω中的那个K2（Kω－（ω－2）＝K2∈Kω）团同化的问题，因为Kω中其他顶点都与Pn中所有的顶点都相邻，不可能再进行同化了。在这里又有两种情况：即d1∩dn＝n－2和d1∩dn＝n－1的两种情况。
1．2．2．3．2．1     d1∩dn＝n－2，即Kd1∩Kdn＝Kω－2∈Kω的情况
这里又有两种情况：即道路Pn中n为奇数和偶数两种情况。
1．2．2．3．2．1．1     n为奇数
这种情况下，Pn中总有一个顶点同化不到Kω中去，且任何一个顶点都可能成为这样一个同化不到Kω中去的顶点，其机会是相等的（如图1）。图中只画出了和属于Kω中的那个K2，顶点的相邻关系除画了Pn中的顶点1和顶点n与属于Kω中的那个K2团的两个顶点的相邻关系外，其他的顶点和相邻关系均未画出。
1．2．2．3．2．1．2     n为偶数
这种情况Pn中的顶点全是可以同化到Kω中去的。
1．2．2．3．2．2     d1∩dn＝n－1，即Kd1∩dn＝Kω－1∈Kω的情况
这里也有两种情况：同样是n为奇数和偶数的问题。
1．2．2．3．2．2．1     n为偶数
这一情况下，Pn中也总有一个顶点同化不到Kω中去，同样其中任何一个顶点都可能成为这一同化不到Kω中去的顶点，其机会也是相等的（如图2）。

1．2．2．3．2．2．2     n为奇数
这一情况下Pn中的顶点也是全部可以同化到Kω中去的。
1．2．2．3．3  最大图外的圈（回路）向最大团的同化
当1．2．2．3中的Pn道路是回路（即圈）时，同样也有上述同化的结果。
1．2．3   图顶点着色色数的上界
从上面的计论中可以看出，只有在d1∩d2∩……∩dn＝ω－2，d1∩dn＝n－2，且n为奇数和d1∩d2∩……∩dn＝ω－2，d1∩dn＝n－1，且n为偶数时的两种特殊的道路中只存在有一个顶点同化不到最大团中去，可见着色时图中若有这样的特殊道路时，其着色色数至少要比图的密度ω大1，现在要问，最大能比密度大多少呢，也即是最多可能有多少个顶点不能同化到最大团中去呢。
1．2．3．1     
图中可能存在多条这种特殊道路，但如果这些特殊道路间不存在“联”（即“和”），那么总可以把各条道路中互不相邻的顶点作为道路中不能同化到最大团中去的顶点（前面已经证明了道路中的每个顶点都可作为这种同化不到最大团中去的顶点），这些顶点由于其本来就互不相邻，所以又完全可以再同化成为一个顶点。道路再多，仍与只有一条那种特殊道路的情况相同，最终只是有一个顶点同化不到最大团中去，图的色数也就会比其密度大1，即γ＝ω＋1。
1．2．3．2   
若在多条特殊道路中有s条两两间都有“联”存在，那么各道路中同化不到最大团中去的那s个顶点因其本来就相邻，也就不可能再同化成为一个顶点，图的色数也就比其密度大s，即γ＝ω＋s。那么s与ω有什么关系呢？
s条两两间都有“联”存在的特殊道路，所构成的团的顶点数最多只可能是2s，但它决不会大于图的密度ω，这时便有
2s ≯ ω或2s ≤ ω                                    （6）
也即
s ≤ ω/ 2                                                 （7）
但道路的条数只可能是整数，所以对（7）式的值要向下取整，则有
s ≤ <（ω/ 2）> 或 s ≤ INT（ω/ 2）                      （8）
可见一个密度为ω的图中最多可能有<（ω/ 2）> 个（或INT（ω/ 2）个）顶点同化不到最大团中去。
1．2．3．3   图的最小完全同态顶点数的上界
由1．2．3．2的论述可知，图同化后的最终结果——最小完全同态的顶点数最大只可能是
a ≯ ω＋<（ω/ 2）> ≯ ω＋ < 1.5ω >
或         a ≤ ω＋<（ω/ 2）> ≤ ω＋<1.5ω >                     （9）
1．2．3．4   图顶点着色色数的上界
由1．2．3．3可知，图顶点着色色数的上界就是
γ＝a ≯ < 1.5ω >或γ＝a  < 1.5ω >                     （10）
1．2．4   任意图顶点着色色数的界
把（2）式与（10）式结合起来，就得到任意图顶点着色色数的界是
ω ≤ γ ≤ < 1.5ω >                                   （11）
这（11）式就是任意图顶点着色色数的界。可见图顶点着色色数的界是图的密度的函数，即有
γ ＝ f（ω）                                       （12）
2   四色猜测的证明
有了前面关于任意图顶点着色色数的界以后，四色猜测的证明就简单得多了。
2．1   平面图四色猜测的证明
已知任何平面图的密度都不会大于4，现将平面图的密度代入（11）式即可。
2．1．1   当＜4时，把1、2、3分别代入（11）式，其值均不大于4，即密度小4的任何平面图的色数都不大4，即有
γ平 ＜ 4（ω＝1，2，3）                             （13）
2．1．2   
当ω＝4，代入（11）式时，会得到γ＝4，5，6的三种情况，但在当γ＝5，6的两种情况下，这个密度为4的图就不是平面图了，而是一个非平面图，如图3。图中K4团各顶点上的数字既代表顶点的顺序，又代表一种颜色，而Pn道路各顶点上面的数字只代表顶点的顺序，下面的数字则代表颜色。图3中的四个图每个图中都出现了顶点以外相互交叉的边e，这是非平面图的一个显著特点，仅管（2）、（4）两图的色数不大于4。（1）、（2）两图γ＝5，图就不再是平面图了，可见当γ＝6时就更不会是平面图了。由 此可知，ω＝4的平面图的色数一定恒等于4，则有
γ平 ≡4（ω＝4）                                   （14）

2．1．3   平面图的色数
综上所述，把（13）式与（14）式结合在一起即得到任意平面图的色数
γ平 ≯ 4或γ平 ≤ 4（ω≤4）                          （15）
到此，平面图的四色猜测就得到了证明是正确的。
另外由图3还可以看出，密度为4的图，既有可能是平面图，也有可能是非平面图，其色数有可能是4，也有可能是5或6。
2．2  地图四色猜测的证明
地图本身就是一个平面图，且是3正则图（每个顶点都连有3条边），它的对偶图仍是一个平面图，这样就把一个给图的面上着色的地理问题变成了一个给图的顶点着色的数学问题了。由（15）式知道任意平面图顶点着色的色数不会大于4，那么地图着色的色数也就不会大于4。即
γ地 ≯ 4或γ地 ≤ 4                                  （16）
至此，1852年由法郎西斯提出（又一说是1840年麦比乌斯提出）的地图四色猜测就得到了彻底地证明，任何地图着色时，四色足矣！
3   具体图的色数的确定
3．1   具体平面图色数的确定
3．1．1   当ω＝1时，图只是一些孤立的顶点互不相邻，一种颜色就够用了，把ω＝1代入（11）γ仍是1，即有
γ平≡1（ω＝1）                                  （17）
3．1．2   当ω＝2时，图中若含有奇圈，其色数一定是γ＝ω＋1＝3，因为奇圈中的每一个K2团以外的其他顶点对于该K2团构成了一条特殊道路，其上总是有一个顶点同化不到这个K2团中来，如图4（图中顶点旁的数字，K2团中的既是顶点顺序，又是颜色，Pn中的外面是顶点顺序，内面的是颜色）。可见ω＝2的平图，只要其中含有奇圈，其色数一定是ω＋1＝3，即有
γ平＝ω＋1＝2＋1＝3（ω＝2）                         （18）
除此以外的任何ω＝2的平面图的色数一律是ω＝2，即有
γ平＝ω＝2（ω＝2）                                   （19）

3．1．3   当ω＝3时，图中若含有奇轮，其色数一定是γ＝ω＋1＝4，因为奇轮中的每一个K3团以外的其他顶点对于该K3团也构成了一条特殊道路，其上也总是有一个顶点同化不到这个K3团中来，如图5（图中顶点旁的数字意义同图4）。可见ω＝3的平图，只要其中含有奇轮，其色数一定是ω＋1＝4，即有
γ平＝ω＋1＝3＋1＝4（ω＝3）                         （20）
除此以外的任何ω＝3的平面图的色数一律是ω＝3，即有
γ平＝ω＝3（ω＝3）                                  （21）
3．1．4  当ω＝4时，由（14）式可知，ω＝4的平面图色数是恒等于ω＝4的，即
γ平≡ω＝4（ω＝4）                                 （22）
3．2   具体地图色数的确定
3．2．1   地球地图的色数
以上说的地图是一个广义的地图概念，不管各区划的属性，而具体的地球地图中还有海洋，这就使得地球地图中的区划有两种属性，即海洋区划与陆地区划，海洋区划只有一个且不是一个行政区划，属与其相邻的行政区划所共有，因此，往往在给地球地图着色时单独地把海洋要改用单独一种颜色，这就使得地球地图的色数成为
γ地 ≯ 5或γ地 ≤ 5                                    （23）
由于具体地图的幅度不同，也就使得其着色时所用的颜色多少的不同。
3．2．1．1   “国中之国”的地图，如位于南非境内的莱索托，大洋中的单岛国，着色时两种颜色就够了，即
γ平＝ 2（国中之国的地图）                            （24）
      3．2．1．2   “两国夹国”的地图，如中国与俄罗斯之间所夹的蒙古国，着色时必须三种颜色才能够用，即
γ地＝ 3（两国夹国的地图）                           （25）
3．2．1．3   “一国环两国”的两国地图，如一个海岛中有两个国家，这种地图着色时也得要用三种颜色，也有
γ地＝ 3（一国环两国的两国地图）                     （26）
3．2．1．4   “一国环三国”的两国地图，如一个海岛中有三个国家，这种地图着色时必须得用4种颜色才可够用，即有
γ地 ＝ 4（一国环三国的三国地图）                      （27）
3．2．1．5    不含海洋的多国（区划）地图，若其中含有周围有奇数个邻国（区划）的国家（区划），着色时必须用四种颜色，有
γ地 ＝ 4（不含海洋的多国（区划）地图，含有奇数邻国（区划））                                                    （28）
否则，着色时只须三种颜色就够了，又有
γ地 ＝ 3（不含海洋的多国（区划）地图，不含有奇数邻国（区划））                                                   （29）
3．2．1．6    含有海洋的多国（区划）地图，包括海洋在内，若其中含有周围有奇数个邻国（区划）的国家（区划），着色时必须用五种颜色，即有
γ地 ＝ 5（含有海洋的多国（区划）地图，含有奇数邻国（区划））                                                    （30）
否则，着色时只须四种颜色就够了，又有
γ 地＝ 4（不含海洋的多国（区划）地图，不含有奇数邻国（区划））                                                   （31）
3．2．1．7    大洲和全地球的地图，由于陆地上的国家（区划）中一定会有一个国家（区划）的邻国（区划）数是奇数，所以着色时的色数一定是5，即
γ地 ＝ 5（大洲和全地球的地图）                        （32）
地球地图着色时最多可以用到五种颜色，但这与四色猜测的正确性并不予盾，因为海洋所用的一种是改着的，若把海洋与其他陆地区划同样看待时，四种颜色就够用了。
3．2．2  月球地图的色数
由于月球上只有陆地，而没有象地球上的海洋，所以月球上无论怎样划分区划，着色时四种颜色一定是可以够用的，即
γ月 ≯ 4或γ月 ≤ 4                                （33）
月球地图实质上就是一个广义的地图。
4   任意图顶点着色色数的界的作用
任意图顶点着色色数的界除了上述对四色猜测进行证明外，还可求出在不同着色要求下各种着色色数的界。
4．1   求线色数的界
线色数即只给图的边进行着色时的色数，其线图的密度为ω线＝Δ（Δ是图中顶点的最大度，即所有顶点中连边最多的顶点所连的边数），代入（11）式便得到
γ线 ≯ < 1.5Δ> 或 γ线 ≤ < 1.5 >                     （34）
4．2   求全色数的界
全色数即既给图的顶着色又给图的边进行着色时的色数，其全图的密度为ω线＝Δ＋1，同样代入（11）式便可得到
γ全 ≯ < 1.5（Δ＋1）> 或 γ全 ≤ < 1.5（Δ＋1）>         （35）
4．3求平面图面色数的界
面色数即只给平面图的面进行着色，其对偶图仍是平面图，其密度ω平偶一定不会大于4，其色数也一定不会大于4，也就是说任意平面图的面色数也决不会大于4，即有
γ面 ≯ 4 或 γ面 ≤ 4　　　                        （36）
4．4    图值函数的色数的界
线图、全图、平面图的对偶图都是原图的图值函数，还有多种别的图值函数，按照着色要求只要求出其图值函数的密度ω图值，其色数就可以确定了，即
γ图值≯ < 1.5ω图值 > 或 γ图值　≤ < 1.5ω图值 >               （37）
由于图值函数的密度与图的最大度Δ，δ最小度，面的最小周长c等一些图的参数有关，所以可以把图值函数的密度表示成
ω图值＝f（Δ，δ，c……）                              （38）
代入（11）式得图值函数的界为
f（Δ，δ，c……）≤γ图值　≤1.5 f（Δ，δ，c……）        （39）
5   结论
5．1    对于四色猜测的证明，只有在图论、集论有了一定发展的现阶段才有可能，证明过称不需对任何图进行着色；
5．2    用无休止的着色的办法是无法对猜测进行证明的，无休止的着色才是人“一辈子时间也证不完”（钱学森语）的；
5．3    所谓用电子计算机“证明”了猜测的说法是错误的，它只能算作是对猜测的验证，而不能看作是证明，因为“图”这个集合是一个无穷集合，图有无穷多个，而阿倍尔等人验证所用的图的个数不但是有限的，而且都是特殊的（实际上也是无法验证完的）；
5．4   1890年由赫屋特（Heawood）构造的Heawood—图是可4着色的，作者早于1989年就将该图在赫屋特已着色的基础上，将其着色所剩的一个顶点着上了他已使用过的四种颜色之一，并于1992年3月8日在陕西省数学会第七次代表大会（西安空军工程大学）上作过学术报告，进行了着色表演；
5．5    有了任意图顶点着色色数的界，平面图四色问题、地图四色问题、线色数的界、全色数的界、平面图面色数的界、图值函数的色数等，一切有关着色的问题就都可以解决了；
5．6    本论文曾于1994年9月27日在陕西省数学会一九九四年的学术年会上作过学术报告；
5．7    任意平面图着色、地图着色，四色足矣！

雷  明
一九九九年四月于金堆城矿

（注：当时在《业余数学天地》网上的《百家争鸣》栏目发表时图没有发上去，这次发表对文章个别地方作了修改。）

雷  明
二○一○年三月二十日于长安

尚九天

任主任快该上这儿放屁来了，先生不信，就等一会儿！