加载中…
正文 字体大小:

四色猜测证明的三篇文章

(2013-10-09 14:42:34)

 

四色猜测证明的三篇文章

 

(二○一三年十月九日)

 

    以下三篇论文是香港《新科技》杂志总第十六期(二○一三年九月刊)准备一次刊登的我的三篇关于四色猜测证明的论文。并且为此而写了编者按。我感到他们的版面费用太高,所以也就不准备刊登了。我现在把这三篇论文的校对搞重新发表在这里。

香港《新科技》杂志的编者按:科学领域研究发展是永无止境!四色猜想是世界近代著名的三大数学难题之一,仅次于 Goldbach 猜想。作者的《用哈德维格尔的思想对四色猜测进行证明》、《4CC的证明——从欧拉公式到着色定理》和《用“断链”的思想证明四色猜测》三篇论文,既有继承,又有创新,将“四色猜测”世界难题的研究又向前推进了一大步,希望中外数学界给予重视。

 

1)、用哈德维格尔的思想

对四色猜测进行证明

 

(二○一三年八月五日)

 

1、四色问题

四色问题是一个由对地图中区域(面)染色的地理问题演变而来的对平面图的顶点着色的数学问题。由于地图本身就是平面图,且平面图的对偶图仍是平面图,所以对地图中面的染色就相当于对其对偶图中顶点的着色。

四色问题说的是对任何一个地图中区域(面)的染色,或者对任何一个平面图中顶点的着色,当两相邻的面或两相邻的顶点都不用同一颜色时,最多四种颜色就够用了,也就是说它们的色数都不大于4

哈德维格尔(Hadwiger)在1943年的提出了一个猜想:即“若图Gn色的,则G可‘收缩’为一个完全图Kn”。如果该猜想是正确的,则四色问题就相当于任何平面图也可收缩为一个顶点数小于等于4的完全图Kn。那么证明四色猜测只要证明任何平面图最后收缩成的完全图Kn的顶点数n不大于4就可以了。

2、哈德维格尔猜想的证明

既然图G的色数是n,那么着有相同颜色的顶点所构成一个集合就是图的一个顶独立集,该图有n种颜色,也就一定可以构成n个顶独立集。每一个顶独立集内的顶点在图中都是不相邻的顶点。把每一个顶独立集均看成一个顶点时,由于处在不同顶独立集中的某些顶点在原图中存在着这样那样的相邻关系,也就使得这代表n个独立集的n个顶点均成为两两顶点均相邻的完全图Kn,其中的顶点数n就是原图的色数。这个完全图Kn就是原图的最小完全同态。

3、任何图的最小完全同态的顶点数都是不会小于其密度的

图可以说是由顶点数不同的各种团构成的,其中必有一种团的顶点数是最多的,该团就是图的最大团,最大团用Kω表示。图中最大团的顶点数ω就是图的密度(有的文献中把“密度”叫做“团数”)。密度是区别图的最基本的特征参数。由于任何团都是一个完全图,所以任何图的最小完全同态Kn的顶点数都是不会小于该图的最大团Kω的顶点数ω的,即有n≥ω的关系。

由于平面图中的最大团Kω的顶点数ω都不大于4,所以我们就有可能对不同的4 种密度的平面图逐个的进行分析,看其最小完全同态Kn的顶点数n是否大于4(见后面的6)。若都不大于4,四色猜测就是正确的,否则就是错误的。

4、不可同化道路

可以肯定,图中最大团以外的任何一个顶点单独一定都是可以同化(“同化”就是哈德维格尔猜想中的“收缩”)到最大图中去的,因为其至少与最大团中有一个顶点是不相邻的,最大团外的那个顶点当然就可以同化到最大团中的这个顶点之上。但最大团外的多个顶点在相互之间还相邻的情况下,这多个顶点是否都可以同化到某个最大团中去呢。

这里首先引入“不可同化道路”的概念。就是该道路中总是存在一个顶点不能同化到最大团中去的,所以叫不可同化道路。如果一个最大团外的一条道路的每个顶点都与最大团中的ω-2个顶点相邻,而道路的两个端点顶点又分别是与最大团中的另外两个顶点之一相邻,这条道路中的顶点总存在一个顶点是同化不到最大团中去的。如图1

四色猜测证明的三篇文章

1a是一个奇圈,图1b是一个奇轮,顶点3n是一条道路,该道路中的每个顶点都与奇圈中的一个K2团的ω-2220个顶点相邻,也都与奇轮中的一个K3团的ω-2321个顶点相邻,并且该道路的两个端点顶点3n又分别与K2团和K3团中的顶点12相邻。当n为奇数时,无论你怎么同化,道路中总是有一个顶点同化不到最大团中去的,而且道路中的每一个顶点都可成为这样的顶点,其机会是相同的。这就使得奇圈同化的最小完全同态是一个完全图K3,顶点数是3;奇轮同化的最小完全同态是一个完全图K4,顶点数是4;分别都比其原来图中最大团的顶点数大1,其色数也就比其密度大1。奇圈的密度是2,而色数却是3;奇轮的密度是3,而色数却是4

当图1中的n均为偶数时,即图是偶圈或偶轮时,道路中的所有顶点则是可以全部同化到最大团K2K3中去的,所以偶圈与偶轮的色数分别仍是23,与其密度相同。这种圈和轮中的道路与以上奇圈和奇轮中道路有相同的特点,但道路中的所有顶点却都是可以全部同化到最大团中去的。同样都是具有相同特点的道路,有的所有顶点都能同化到最大团中去,有的则不能。我们把具有这种特点的两种道路统一叫做饱和道路,因为再在道路与最大团间增加边时,图的密度大小和道路的长短都会发生变化,就不成原来的图了。

5、两个图的联

一条不可同化道路就一定有一个顶点同化不到最大团中去,那么某个最大团外有多条不可同化道路情况时是什么样子呢。首先还要引入两个图的联的概念。两个图的联就是把甲图中的每一个顶点都与乙图中的每一个顶点相邻,同时也把乙图中的每一个顶点与甲图中的每一个顶点也相邻后所得到的图。两个图的联既然是图,就一定也有图的基本特征参数——密度值。可以证明两个图的联的密度等与构成它的两个图的密度之和。

道路中的最大团是K2,密度是2,两条道路的联中的最大团则是K4,其密度就是4。这是因为把甲道路中两相邻顶点分别与乙道路中的两相邻顶点都用边连接起来后,图中就出现了K4团,所以两条道路的联的密度就是4

如果最大团外的两条不可同化道路构成了联,那么两条不可同化道路中同化不到最大团中去的那两个顶点则因其本身就是相邻的,而不可能再同化成一个顶点,所以有两条构成了联的不可同化道路就有两个顶点同化不到最大团中去,图的最小完全同态的顶点数就会比其密度大2。若两条不可同化道路间未构成联时,即两条道路中总存在着至少有两个不相邻的顶点,那么我们在同化时总可以把这两个不相邻的顶点作为不可同化的顶点,然后再把他们同化成一个顶点,仍相当与只有一条不可同化道路时的情况。

6、平面图的最小完全同态的顶点数是不会大于4

现在就对平面图的密度一个个的进行分析,看其中是否存在不可同化道路,且其间是否可以构成联:

当ω=1时,最大团是K1,图中只有孤立顶点,不可能有任何道路,所以图同化的结果仍是完全图K1,其顶点数是n14,色数也是1,也不大于4

当ω=2时,最大团是K2,图中若有奇圈时,一定有一条不可同化道路,图同化的结果一定是K3,否则则是K2,其顶点数n分别是32,均不大于4,色数也分别是32,也不大于4

当ω=3时,最大团是K3,图中若有奇轮时,也一定有一条不可同化道路,图同化的结果一定是K4,否则则是K3,其顶点数n分别是43,也均不大于4,色数也分别是43,也不大于4

由于两条道路的联的密度是4,已是平面图的最大密度了,所以在ω=2和ω=3时的平面图中是不可能存在两条可构成联的不可同化道路的。

当ω=4时,最大团是K4,本身就是一个轮。我们在 K4外构造一条不可同化道路时,图就成了非平面图,因为图中出现了交叉边。如图2

2中的四个图均是在K4外构造了一条饱和道路,其中两个图中的是不可同化道路,两个图中的是可同化道路。但四个图中均有一条边e是交叉边,使图变成了非平面图,不在四色问题研究之列。所以说在密度为ω=4的平面图中是不会存在不可同化道路的。

到此,我们就已经证明了任何平面图的最小完全同态的顶点数是不会大于4 的。

7、图2中四个图不是平面图的理论证明

 

2中这四个图均不是平面图还可以这样来从理论上进行证明:设这条饱和道路Pn的顶点数为n,则:① 这条道路共有n1条边;② 其与最大团K4相邻的边数是(42n22n2条(其中每个顶点各与K4团的两个顶点(ω-2422)相邻,两个端点顶点又各与K4团中的另一个顶点相邻);③ K4团的边数是4×(41/ 26;④ 共计该系统的总边数是(n1)+(2n2)+63n7条;⑤ 4n个顶点构成的图如果是平面图时,其边数最大只能是e3v63×(4n)-63n6条,⑥ 而现在该图实际的边数却有3n7条,大于3n6条。⑦ 所以密度为ω=4的图中,如果在某一个K4团外,只要有一条道路是饱和道路时,则不管这条饱和道路是否是不可同化道路,这个图就都不再是平面图了,而是一个非平面图。⑧ 所以说任何密度是4的平面图同化时的最小完全同态的顶点数或其顶点着色的色数都恒等于4

四色猜测证明的三篇文章
    8、四色猜测是正确的

通过以上分析,可以看出任何平面图同化时的最小完全同态的顶点数都是不可能大于4 的,当然其顶点着色的色数也就不会大于4了。这就证明了平面图的四色猜测是正确的。因为平面图(也包括地图)的面染色就是对其对偶图的顶点着色,平面图顶点着色的色数不大于4,那么平面图面染色的色数也就不大于4。这也就证明了地图四色猜测是正确的。所以可以得出结论:四色猜测是正确的,四色足矣!

 

二○一三年八月五日于长安

 

注:该文已发给杨卫华老师进行交换。

 

 

 

24C C 的 证 明

——从欧拉公式到着色定理

 

(二○一三年五月二十三日)

 

 】从适合于任何亏格的多阶曲面上图的欧拉公式直接推导出了多阶曲面上图的着色公式,不但证明了亏格为0的球面(平面)上的四色猜测是正确的,而且还得到了更加绚丽多彩的多阶曲面上图的着色定理。

关键词】图  任意图  任意图的色数  顶独立集  任意图的最小顶独立集数  完全同态  任意图的最小完全同态的顶点数  多阶曲面  亏格  嵌入  欧拉公式

 

1、任意图的色数与其最小顶独立集数和最小完全同态的顶点数是相等的

把图中的两个不相邻的顶点凝结到一起的过程叫“同化”。一个图经过一次同化后所得到的图叫原图的一个“同态”,在这个同态的基础上再进行一次同化后所得的图,仍是原图的一个同态,只是后一次的同态比前一次的同态的顶点数少了1。一个图经过若干次同化后,一定可以得到一个不可能再进行同化的、各顶点均互相相邻的完全图式的同态,这个同态就是原图的完全同态[1]

由于同化的步骤不同,一个图可以得到顶点数不同的多个完全同态,但其中必有一个完全同态的顶点数是最少的,这就是原图的最小完全同态。最小完全同态中的每一个顶点都是由若干个不相邻的顶点凝结而来,所以它的每一个顶点都是代表着若干个不相邻的顶点的,这些不相邻的顶点就够成了原图的一个顶独立集,所以最小完全同态的顶点数就是原图的最小顶独立集数。

在图的最小完全同态中,由于各个顶点均相邻,其在着色时有几个顶点就得用几种颜色。若再按同化时的相反方向连同所着的颜色返回到原图时,这个图的着色就已经完成。图中所用的颜色数就等于其最小完全同态的顶点数。同一个顶独立集内的顶点,由于其在原图中均不相邻,所以完全是可以着同一种颜色的,有几个顶独立集,着色时就得用几种颜色。所以任意图的着色数与图的最小顶独立集数也是相同的。因此可以得出结论:任意图的色数与其最小顶独立集数和最小完全同态的顶点数都是相同的。

用γ表示图的色数,用β表示图的最小顶独立集数,用α表示图的最小完全同态的顶点数,则有γ=β=α的关系。可嵌入某亏格曲面上的图的最小完全同态也一定是能够嵌入到与该图同亏格的曲面上的。由此可以看出任意图的着色问题就可以转化为求多阶曲面上可嵌入的最大完全图(或最大团)的顶点数的问题。

2、多阶曲面上可嵌入的最大完全图的顶点数

若一个能够嵌入到亏格为n的曲面上的、有v个顶点和e条边的图把曲面分成了f个区域,一定能满足已经经过证明是完全正确的多阶曲面上图的欧拉公式[2],即有vfe22n,其中v1f1e0n0。设f个区域分别是f1f2,……,ff,用ei1if)表示区域fi的边数,由于单纯连通图中每个面的边数都是大于等于3的,因此有ei3,又因为每一条边均是属于两个区域所共有,所以有3f≤ ≤2e,故有3f2e,即有f2e / 3。把f2e / 3代入多阶曲面上图的欧拉公式vfe22n得:

v2e / 3e22n

ve / 322n

3ve66n

再把完全图的边与顶点的关系式evv1/ 2代入上式得:

3vvv1/ 266n

6vv2v121n

v27v121n)≤0

解这个关于图的顶点数v的一元二次不等式得:

v1= =

v2= =

由于图的顶点数必须是v1,而根v2在亏格数n1v2= 是小于等于0的,不符合题意要求,舍去不要。所以该一元二次不等式只有一个根v1= ,又由于图的顶点数必须是整数,所以v1= 还得向下取整,即有:

v1

这就是亏格为n的曲面上所能嵌入的最大完全图(或最大团)KV的顶点数。这个完全图着色时的色数就等于其顶点数。这也就是赫渥特1890年给出的多阶曲面上的地图着色公式。

3、更加绚丽多彩的着色定理

前面已经说了,任意图的着色问题可以转化为求多阶曲面上可嵌入的最大完全图(或最大团)的顶点数的问题。再由于可嵌入某亏格曲面上的图的最小完全同态也一定是能够嵌入到与该图同亏格的曲面上的,所以可嵌入某亏格曲面上的图的色数也一定是不会大于该亏格曲面上的最大完全图的色数(即该图的顶点数)的。所以又有:

        γn=β=α≤v1

这是一个多么光彩绚丽的着色定理呀!当n0时,有γ≤4,这就证明了四色猜测是正确的;当n1时,还有γ≤7,这就是环面(轮胎面)上的七色定理;当n2时,也还有γ≤8的八色定理;等等等等。现在用亏格n对色数γ作如下表得:

 

亏 格 n =

0

1

2

3

4

5

6

7

8

9

10

色 数 γ ≤

4

7

8

9

10

11

12

12

13

13

14

顶独立集数 β ≤

4

7

8

9

10

11

12

12

13

13

14

完全同态顶点α≤

4

7

8

9

10

11

12

12

13

13

14

 

这不比单纯只有一个四色定理更绚丽多彩吗。当我们要求出某个色数定理所对应的曲面的最小亏格时,可以把γ≤ 进行变形得:

γ≤

2γ≤7

2γ-7

2γ-72148n

48n≥(2γ-721

n

曲面的亏格是整数,把上式再向上取整得:

n

这就是某个色数定理所对应的曲面的最小亏格。

 

4、结论

不但球面(平面)上的四色猜测是可以证明的,而且还有比四色定理更加绚丽多彩的多阶曲面上图的着色定理γn≤ 。

                         

             二○一三年五月二十三日于长安

 

[参考文献]

1 《图论的例和反例》,[美]M·卡波边柯,J·莫鲁卓合著,聂祖安译,湖南科学技术出版社出版发行,湖南省新华印刷二厂印刷,19884月第1版第1次印刷。同化一词见该书第1718页和第211页。“同化”有的文献上又叫“收缩”,我认为叫同化合适一些,因为它是把两个不相邻的顶点凝结到一起的过程,而收缩则是要沿着某一路线进行的过程,这一路线就是某条边,所以我认为只有把两个有边相邻的顶点凝结到一起的过程叫收缩也才是合适的。“收缩”一词也请参见该书第214页的“初等收缩”(Elementary contraction)一词的注释。同态(Homomorphism),完全同态(Complete homomorphism),见该书第1718页和第211页及第217页。

2 《图论导引》(《lntroduction  to  Graph  Theory》),[美]Gary  ChartrandPing  Zhang 合著,范益政、汪毅、龚世才、朱明等翻译,人民邮电出版社出版发行,北京隆昌伟业印刷有限公司印刷,20079月第1版,20079月第1次印刷。多阶曲面上图的欧拉公式的证明见该书的第218219页。

 

注:此文已于二○一三年五月二十三日在《数学中国》网上发表过,网址是:

http://www.mathchina.com/cgi-bin/topic.cgi?forum=12&topic=3289&show=0

 

 

 

3)、用“断链”的思想证明四猜测

 

(二○一三年八月十九日)

 

着色法证明四色猜测时,一定要用到坎泊的颜色交换技术——K—交换。K—交换的实质就是对一条用两种颜色交替着色的道路(图论中把这种已着色的道路叫做链)中的两种颜色互相调换,以达到改变道路中任何一个顶点的颜色的目的。

由于平面图中至少有一个顶点的度小于等于5,所以在证明猜测时一般都是采用一个5—轮构形,5—轮中心顶点V以外的所有顶点都已4—着色,且5—轮的轮沿顶点已点用完了四种颜色,问这时V能否着上图中已用过的四种颜色之一。如图1

四色猜测证明的三篇文章

 

5—轮的5个轮沿顶点用四种颜色的情况只可能有这一种。要给V着上已用过的四种颜色之一,只有从轮沿顶点所用的颜色中移去一种给V着上,当然首先最好是考虑移去只用了一次的颜色,而改着上其他两种只用过一次的颜色。要达到这一目的,一定得要使用坎泊1879年所创造的颜色交换技术。

选取一组对角顶点24,如果这两顶点间没有连通的bg链,从那一个顶点交换都是可以移去bg二色之一给V着上,而这个轮沿顶点则改着成了bg链中与其原有颜色不同的另一种颜色(如图2)。否则,交换bg链也是空不出颜色给V的;再看另一组对角顶点25,如果这两顶点间没有连通的by链,从那一个顶点交换都是可以移去by二色之一给V着上,而这个轮沿顶点则也改着成了by链中与其原有颜色不同的另一种颜色。否则,交换by链是空不出颜色给V的;当在bg链、by链都连通的情况下(如图3),根据约当曲线定理,肯定从顶点1 到顶4没有连通的rg链,也肯定从顶点3到顶点5也没有连通的ry链,这时可以选择移去两个同色r的交换方法:分别从顶点13开始交换rg链和ry链,空出rV着上(如图4)。

四色猜测证明的三篇文章

 

3和图4中有两条连通链,但在链的非端点顶点处,两链再没有交叉顶点。象这种存在两条连通链的情况还有如图5和图6的两种情况,是两条连通链在其非端点顶点处存在交叉顶点的情况。同样,图5 中一定没有连通的by链和bg链,从顶点245三顶点之一开始,交换上述的bybg中的任一条不连通链,都可空出非r色的一种颜色给V着上。

6在一般情况下,是可以分别从顶点13开始,交换两次关于r的链后空出rV的,两次交换的次序是不分先后的。但也有交换了两次关于r的链后,仍得到的是有两条连通且相交链的类似图6的图。如图7 先从顶点1进行rg链的交换,后从顶点3进行ry链的交换后,所得到的图8就是这样的图。虽然如此,但图8却与图7 是不大相同的,图7有环形的gy链,把br链分成了环外环内互不相邻的环内和环外两部分,而图8则没有这一情况,br链和gy链均只有一条,且都是直链。图7就是由赫渥特图变化成来的“九点形”图,这种图我们叫它“H—构形”。(若对图7先从顶点3进行ry链的交换,后从顶点1进行rg链的交换所得到的图则是形如图9所示的图。图9和图8正好是左右对称的。)

四色猜测证明的三篇文章

 

为什么会产生图8的这一情况呢,这是因为图7从顶点1 进行了rg链的交换后,原本不连通的从顶点35ry链却变成了连通的,第二次从顶点3开始交换的实际上是一条连通链,当然是空不出颜色来的。交换的结果是顶点3r变成了g色,而顶点5却由g色变成了r色,所以说该图就不可能同时移去两个同色r。该怎么办呢?

我们发现,由图7变化而来的图8 和图9,与图7 是不同的。对于图8,有选择性的先从5—轮左上角的顶点4开始进行bg链的交换,再从5—轮右上角的顶点1开始进行yg链的交换,是可以空出g色给V着上的。这是因为这种图从顶点4交换了bg链后不会形成顶点35的连通链yg,所以从顶点3 是可以进行yg链的交换的。对于图9,则是先要从5—轮右上角的顶点3进行ry链的交换,再从5—轮左上角的顶点1进行rg链的交换,也才能空出r色给V的。以上两图两次交换的次序均是不能改动的,否则,交换的次序错了,仍是不能空出两个同色给V的。不但不能空出两个同色,而且图又会变成象图7H—构形。

四色猜测证明的三篇文章

 

还有一种图,图中虽然也有相交且连通的bgby链,但图中有一条环形的br链,把gy链分成了环内环外不连通的两部分,如图10。这种图是可以不分先后次序的进行两次关于r的链的交换的,空出rV着上。我们把这种图叫做非H—构形。由于图8 和图9着色的特殊方式,既可以同时移去两个同色,又不可以同时移却两个同色,所以我们把它叫做半H—构形。

从以上的分折中我们还可以看出,H—构形与半H—构形是可以相互转化的,所以在着色时一定要注意,不要陷入其相互转化的陷阱中去了。

对于H—构形的图,除了把其转化为半H—构形再空出颜色外,还可以通过K—交换对连通链进行破坏,我把这种方法称为“断链法”。对图7分别从两连通链的交叉顶点28进行br链的交换,都可使bgby链变得不连通,这一交换过程就是在进行“断链”的过程。再随便从顶点245那一点开始交换bgby链就可空出bgy三色之一给V着上。

四色猜测证明的三篇文章

 

H—构形更复杂一点的还有米勒构形,(如图11,也就是张彧典书中的图5.4),这个图中除了有H—构形的特点以外,其中的AB链和CD链各都有两条,且都各有一条是环形链,一条是直链。从内向外分别是:AB直链,CD环链,AB环链和CD直链。这就造成了该图既不能同时移去两个同色B,也不能从两条连通的交叉链的交叉顶点进行交换。这又如何办呢?有办法,采用的仍是“断链”的方法。

11的构形中,两交叉链ACAD的非端点顶点的那个交叉顶点如图11中心部的顶点A),与两链的非交叉顶点的那两个端点顶点(如图11中最下部的C1点和D1点)不是直接相邻的,不象H—构形中的直接相邻,即就是把图7H—构形中顶点45gy链交换了,并不能破坏两条连通链bgby的连通性。但如果把米勒图中最外面的C1D1链进行交换,却则也可达到破坏A1C1链和A1D1链连通的目的。连通的链已经“断”了,使图变成一个非H—构形的图(如图12a,这也就是张彧典书中的图7·391)中的中间一图)。这样就可以空出两个同色BV了。当然对另一条环形的CD环进行交换,也可以使连通且相交的AC链和AD链“断开”,成为一个非H图。

四色猜测证明的三篇文章

 

同时我们还可以看到如果对米勒图企图同时移去两个同色B时,当进行了一次B1D1链的交换(张彧典的书中叫逆时针赫渥特颠倒)后,得到的图却有另外的特点(如图13,这也就是张彧典书中的图5.5)。图13中,除了相交叉的连通链C1A1C1B1AB 环链与直链直接连接上了,CD链则变成了两条直链,无环形链。这就使得我们可以采用对H—构形着色时的“断链”方法给米勒图着色了。这时我们对两条CD链(其中都有两交叉链的交叉顶点)中的任一条进行交换,都可使图变成一个如上图5式的有两条连通的CA链和CB链的非H—构形(如图14,这也就是张彧典书中的图7·392)中的中间一图),再进行一次交换即可空出ABD三色之一给V着上。

四色猜测证明的三篇文章

 

 

四色猜测证明的三篇文章

如果对图13 再进行一次逆时针赫渥特颠倒(张彧典的书中由图5.5到图5.6进行的就是这一步交换)后,得到一个与上面图11 基本相同的米勒构形,如图15(这也就是张彧典书中的图5.6)。图15也与图11一样,从内向外分别是:AB直链,CD环链,AB环链和CD直链。这个图可以交换AB环内外的任一条CD链,使图变成非H—构形,可同时移去两个同色A,与图11的着色方法相同。可见图11和图13 的构形是可以相互转化的,任一个图只要进行一次逆时针赫渥特颠倒后,都可以变成另一个图。

四色猜测证明的三篇文章

 

还有没有比赫渥特图、米勒图更难着色的图呢,现在还没有看到,说不定过些时候就会被构造出来。这样不断的出现新的难着色的图,不断的研究其着色方法,猜测什么时候才能被证明是对还是错呢。因此我一直不主张用着色的方法对猜测进行证明,而主张用不着色的方法进行证明。

补充几点:

1、以上对米勒图进行着色时,只是交换了环形的AB链外的C1D1直链,使连通的ACAD链“断链”,其实还可以交换环形的AB链内CD环链,也可以使连通的ACAD链“断链”,也可同时移去两个同色A

2、以上谈到图11与图15相互转化时只是说进行逆时针赫渥特颠倒,实际上无论是进行那种方向的赫渥特颠倒都可以,以至一逆时针一顺时针都是可以的。

3、对于米勒图着色,无论是直的还是环形的AB链都是不能进行交换的,因为他交换的结果仍是一个米勒图,都有由内向外的AB直链、CD环链、AB环链和CD直链的结构。

4、关于构形、具体的图与着色模式的区别。构形是只有一个顶点未着色的非具体的图,如5—轮构形等,5—构形中除了5—轮以外可以说还有无数的顶点,各顶点之间的相邻关系都不是具体的;具体的图的顶点以及顶点之间的相邻关系都是固定不变的,所以是具体的,如赫渥特图和米勒图等;着色模式是一个图(具体的或不具体的)着色的形式,因为同一个图是可以存在着不同的着色形式的。我们对赫渥特图就已有十多种着色模式,张彧典先生书中的图5.4到图5.8实际上都是同一个具体的米勒图,图5.4到图5.8以及图7·39中的各图分别是米勒图的不同着色模式,其中有的图是着色完成后的模式,有的则是还没有完成的着色模式。

 

二○一三年八月二十一日于长安

 

 

二○一三年十月九日于长安

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有