[原创]表说（证明）四色问题

雷明85639720

[watermark]

表说（证明）四色问题
——二十多年来研究四色问题的总结
雷  明
（二○一○年四月十八日）
1、四色猜测的发展历史（见表一）
四色猜测的发展历史（表一）
人 名时 间 采  用  方  法  使  用  工  具  及  其  结  果说明
法郎西斯1852，10，23，在给英国地图染色时首先提出地图四色问题。（又一说是在1840年由麦比乌斯提出的。）
莫根1852——1860从1852年10月23日到1860年4月14日一直在以各种不同的方式对四色猜测进行着传播。
凯莱1878，6，17，凯莱分别在伦敦的数学会上与次年的英国皇家地理学会所创办的第一卷会刊上两次提出四色问题，四色问题才引起了数学界的重视。
坎

泊1879，7，13，采用着色法验证了4—轮（即一国邻四国）以下的不可避免构形可以4—着色，对5—轮这个不可避免构形并没有验证就宣布他证明了猜测是正确的。这里存在着一个“漏洞”。坎泊在验证猜测的过程中创造了用两种颜色交替着色的方法和颜色交换技术。他首先证明了任何地图中至少存在着一个其相邻区划数小于等于5的区划；也首先证明了任何地图中都不存在5个区划两两均相邻的情况。并首先使用了不可避免构形的概念。
赫
渥
特1890也是用了着色的方法。他构造了一个只剩下一个5—轮中心顶点未着上已用过的四种颜色之一的Haewood—图，因他对该图不能4—着色（坎泊也不能对其进行4—着色）而否定了坎泊的证明。另外他还用坎泊所创造的颜色交换法“证明”了错误的与四色问题毫不相关的所谓的“五色定理”。赫渥特一生研究四色问题六十年，虽没有直接解决四色问题，但却给出了一个任何亏格下的多阶曲面上的地图着色公式，该公式本来对于亏格为0的平面图也是成立的，但由于他对他的Haewood—图没有进行4—着色，而对该公式附加了条件：亏格n≠0。
“国”数不断增加的国际接力比赛1939——1976仍然是用着色的方法。这一时期主要是对“假想地图”进行着色验证。不同国家的许多数学家不断的把“地图”中的“国家”数由22个增加到了52个（还有一说是从1920年到1976年，“地图”中的“国家”由25个增加到52个，还有人说是增加到了95个），虽然都是用了四种颜色，但由于其中的“国家”数仍的有限性，仍不能说明四色猜测就是正确的。
阿
贝
尔
等1976还是用着色的方法。阿贝尔等三人构造了近2000个构形，采用坎泊所创造的方法（着色法）和交换技术，用高速运转的电子计算机花去了2000多个机器小时进行验证，都是只用了四种颜色，宣布了他们用电子计算机“证明”了四色猜测。虽然如此，但其并没有证明猜测是正确还是错误，只是用这2000个有限的图进行了验证是正确的。另外，他们所列的构形中正好就不包括坎泊没有验证，赫渥特也不能验证的5—轮构形。这种“证明”只是白白的浪费了资源。
本文
作者
雷明1989——1994本人用图论的方法，不对任何图进行着色，首先得到了任意图顶点着色的色数与图的密度的关系，然后把平面图的密度不大于4的特点代入，即得到任何平面图着色时色数总不大于4的结论。同时也能解释只含奇轮（密度是3）和奇圈密度是2）的图的色数分别是4和3而比其密度大的原因。这种让明还可以得到诸如线色数、全色数和平面图的面色数等图值函数的色数的界。本文作者还用着色的方法证明了5—轮构形是可以4—着色的，对坎泊证明的“漏洞”进行了弥补，并且对Haewood—图进行了4—着色，说明其是可4—着色的。还可以从曲面上的欧拉公式出发，最后推导出赫渥特的多阶曲面上的地图着色公式，使平面图的四色猜测又得到证明是正确的，因为该公式当曲面的亏格数为0时，其计算结果是色数小于等于4。看来四色猜测就应该变成为“四色定理”了。
2、图的顶点着色、顶独立集划分、顶点同化三者之间的关系（见表二）
图的顶点着色、顶独立集划分、顶点同化三者的关系（表二）
图的基本运算顶 点 着 色顶独立集划分顶 点 同 化说     明
运算的基本操作不相邻的顶点
可着同一颜色不相邻的顶点
可划分到一个
顶独立集内不相邻的顶点可同化成一个顶点
各运算所要达
到的基本要求相邻的顶点不
用同一颜色相邻的顶点
不在同一个
顶独立集内相邻的顶点不
同化在一起
各运算的中
间结果各称色 类 数 Γ顶独立集数Β完全同态的
顶点数A
中间结果指标ω≤Γ≤vω≤Β≤vω≤A≤vω是图的密度即最大团的顶点数
图的顶点数
V与中间结
果的关系  v＝
v＝
v＝
vi分别是着某种颜色的顶点数、某个顶独立集内的顶点数、最小完全同态中某个顶点所代表的顶点数
各运算的最
终结果各称色  数 γ最小顶独
立集数β最小完全同
态的顶点数a
最终结果与中
间结果的关系γ＝minΓβ＝minΒa＝minA
最终结果的宽界ω≤γ≤vω≤β≤vω≤a≤v
图的顶点数
V与最终结
果的关系v＝
v＝
v＝
vi分别是着某种颜色的顶点数、某个顶独立集内的顶点数、最小完全同态中某个顶点所代表的顶点数
经过证明是正确的最终结果乍界ω≤γ≤
ω≤β≤
ω≤a≤
表示其中的数字向下取整
总      结求图顶点着色的色数必须求出图的最小完全同态，其顶点数就是图的色数。
3、图中的单个顶点、团和道路向最大团的同化（见表三）
图中的单个顶点、团和道路向最大团的同化（表三）
图中可向最大团同化的各种分子图单   个
顶   点单  个  团单 条 道 路多 条 道 路说    明
可同化分
子图的表
示方法vKm
（1≤m≤ω）Pn（n≥0）P1,P2,……,PS（1≤S≤ ）
相 邻 度 dd≤ω－1d是各顶点与最大团Kω所相邻的顶点数
相 邻 团KdKdK1 ,K2 ,……,KmK1 ,K2 ,……,KnKd是各顶点与Kω中所相邻的d个顶点所构成的团
相邻团的顶点数dd≤ω－1d≤ω－md≤ω－2
d≤ω－1d≤ω－2
d≤ω－1道路两端点顶点的Kd可达d＝ω－1
单个顶点：
Kω可供同化的顶点数cc≥1单个顶点一定可以同化到Kω中去
单个团时：
Kω可供Km各顶点同化的顶点数cc≥m任何一个团都可以同化到Kω中去
道路情况：
道路各顶点Kd的交KD的顶点数DD≤ω－2D≤ω－2
1、单条道路的第一种情况（非饱和道路）K1∩K2∩，……，∩Km＝KD，D＜ω－2或d1，dn＜ω－1Kω中还有两个以上顶点可供道路中的顶点同化，图的最小完全同态的顶点数a＝ω这种道路叫非饱和道路用Pn表示

2、单条道路的第二种情况（饱和道路）K1∩K2∩，……，∩Km＝KD，
D＝ω－2且d1，dn＝ω－1Kω中只有两个顶点可供中的Pn顶点同化，可能有的顶点有可能同化不到Kω中去这种道路叫饱和道路，
用PN表示
其中：
第一种情况K1∩Kn＝K21、n是偶数Pn中全部顶点都可同化到Kω中去，图的最小完全同态的顶点数a＝ω这是一条可同化道路
2、n是奇数Pn有一个顶点同化不到Kω中去，图的最小完全同态的顶点数a＝ω＋1这是一条不可同化道路
其中：
第二种情况K1∩Kn＝K21、n是奇数Pn中全部顶点都可同化到Kω中去，图的最小完全同态的顶点数a＝ω这是一条可同化道路
2、n是偶数Pn有一个顶点同化不到Kω中去，图的最小完全同态的顶点数a＝ω＋1这是一条不可同化道路
3、有多条不可同化道路的第一种情况（无联）各条道路间
均无联存在S条PN同化不到Kω中去的那S个顶点均不相邻，仍可同化成一个顶点，其结果与只有一条不可同化道路PN的情况相同，也只有一个顶点同化不到Kω中去，图的最小完全同态的顶点数也是a＝ω＋1
4、有多条不可同化道路的第二种情况（有联）各条道路间
均有联存在S条PN同化不到Kω中去的那要S个顶点均相邻，不可再同化成一个顶点，就有S个顶点同化不到Kω中去，这时，图的最小完全同态的顶点数将是a＝ω＋S
5、有联存在的不可同化道路的条数S条不可同化道路均有联存在时，所构成的分子图的密度最大只可能是2S，它一定是小于等于图的密度的，即2S≤ω，有S≤ω/ 2，因S必须是整数，所以还得向下取整，就有S≤
6、有联存在时图的最小完全同态的顶点数aS条不可同化道路均有联存在时，其同化后，图的最小完全同态的顶点数是a＝ω＋S＝ω＋ ＝
7、图的最小完全同态顶点数a的界从以上可以看出，a的最小值是ω，最大值是 ，所以图同化时最小完全同态的顶点数的界是ω≤a≤
总     结PN道路如果是简单回路（即圈）时，同样也有相同的结果。有了任意图最小完全同态顶点数的界，就可以进一步得到任意图顶点着色色数的界。
4、任意图顶点着色色数的界（见表四）
任意图顶点着色色数的界（表四）
图顶点着色
色数的界下     界上     界全     界说     明
界值γ＝aγ＝a≥ωγ＝a≤
ω≤γ＝a≤
总    结图的色数只与图的密度有关，可以把平面图密度不大于4的特点代入其中，证明四色猜测是否正确。
5、四色猜测的证明（见表五）
四色猜测的证明（表五）
项     目密度ω＝1密度ω＝2密度ω＝3密度ω＝4说     明
色     数123344 56
不可同化道路PN的条数S00101012
图的特征孤立顶点无奇圈有奇圈无奇轮有奇轮K3团是奇轮
是否是平面图是是是是非非
结     论任何平面图着色时四种颜色就够用了，这就证明了平面图的四色猜测是正确的。又由于地图本身就是平面图，而平面图的对偶图仍是平面图，所以给地图的面上的着色实际上就是给其对偶图（平面图）的顶点着色。平面图着色四种颜色够用了，当然地图着色四种颜色也就够用了。这也就证明了地图的四色猜测也是正确的。
6、具体平面图的色数（见表六）
具体平面图的色数（表六）
项    目密度ω＝1密度ω＝2密度ω＝3密度ω＝4说     明
有无奇圈无有
有无奇轮无有有
PN的条数S001010
顶点着色色数123344
7、地球地图的实际色数（见表七）
地球地图的实际色数（表七）
地图中的区划及类形地      图       中       的       区       划       数
2
“国中之国”3
“两国夹国”4
“三国环国”5         国         以         上
无邻国数为奇数的区划有邻国数为奇数的区划
无海洋区划有海洋区划无海洋区划有海洋区划
无有无有
色  数2343445
说  明地图边匡以外画地图的纸也有一种颜色（白），有时还单独用一种颜色把南极洲，克什米尔地区，格陵兰岛这些特殊的地区区别开来，所以实际地图的色数有时要比4大。但这并不影响地图四色猜测的正确性，因为这多于4种的颜色是在已进行了4—着色的地图上人为的改着的。
月 图
色 数月球上没有海洋，所以无论怎么在月球上划分区划，月图的色数都一定是≤4。
8、图值函数色数的界（见表八）
图值函数色数的界（表八）
图 值 函 数原图的
最大度图值函数
的密度图值函数
色数的下界图值函数
色数的上界图 值 函 数
色 数 的 全 界
线图，线着色ΔΔΔ
Δ≤γ线≤
全图，全着色ΔΔ＋1Δ＋1
Δ＋1≤γ全≤
平面图
面着色对偶图仍
为平面图≤4≤4≤4γ面≤4
图值
函数的着色Δ，……


≤γ图值≤
说  明图值函数的密度与原图的各参数有关，所以图值函数的密度用 表示。

9、从曲面上的欧拉公式到赫渥特的多阶曲面上的地图着色公式（见表九）
从曲面上的欧拉公式到赫渥特的多阶曲面上的地图着色公式（表九）
推 导
步 骤推  导  方  法  及  所  依  据  的  原  理说   明
第一步从曲面上的欧拉公式v＋f＝e＋2－2n（其中v、f、e、n分别是图的顶点数、面数、边数和曲面或图的亏格）推导出任意图的亏格n≥ （v≥3， 表示其中的数字向下取整）。依据是图的边数与面数有3f≤2e的关系，把f≤2e / 3代入到曲面上的欧拉公式即可得到。
第二步从任意图的亏格n≥ 推导出完全图的亏格n＝ （v≥3）。依据是相同顶点数的图的边数与顶点数的关系e≤v（v－1）/ 2，把e≤v（v－1）/ 2代入到上面的任意图的亏格中即可得到。
第三步从完全图的亏格n＝ （v≥3）再推导出赫渥特多阶曲面上的地国着色公式γn≤ 。推导过程是把完全图的亏格在取整之前进行变形得到0＝v2－7v＋12×（1－n）一元二次方程，然后再解这个关于v的一元二次方程，得其有用根是v＝（7＋ ）/ 2，由于完全图的色数γn就等于其顶点数v，所以有γn＝（7＋ ）/ 2，又由于完全图的色数是与其相同顶点数的所有图中的最大者，又有γn≤（7＋ ）/ 2，色数必须是整数，再向下取整即是γn≤ 。
第四步把亏格n＝0代入赫渥特的多阶曲面上的地图着色公式γn≤ 中，得到γn≤4。
结  论用赫渥特的多阶曲面上的地图着色公式也可以证明四色猜测是正确的（纯数学推导方法）。
10、结论
四色猜测是正确的。任何地图或平面图着色时，四种颜色足矣！

雷  明
二○一○年四月十八日于长安
注：此文已于二○一○年四月二十二日在《数学中国》网上发表。