数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 2308|回复: 13

证明四色猜测时为什么要用最小构形

[复制链接]
发表于 2018-2-23 19:37 | 显示全部楼层 |阅读模式

证明四色猜测时为什么要用最小构形
雷  明
(二○一八年二月二十三日)

构形虽然也是一个图,但却不是一个具体的图,而是某一类有共同特征的图的代表。构形不只光是一个图,而是只有一个顶点(待着色顶点)未着色的图。把与这个待着色顶点相邻、且依次相邻的顶点叫围栏顶点。待着色顶点与围栏顶点则构成的是一个轮形图,所以根据围栏顶点的多少,分别叫做n—轮构形。
四色问题研究的对象是平面图,而任意平面图中至少一定含有一个顶点的度是小于等于5的,所以平面图中不可避免的构形就是:0—轮(孤立顶点K1团)构形,1—轮(单条边K2团)构形,2—轮(有平行边的2—重K3团)构形,3—轮(K4团)构形,4—轮构形,5—轮构形。由这6种轮构成的集合就是平面图的不可免构形集。这就把一个无穷的问题变成了一个有穷的问题了,只要研究这6种构形是可4—着色的(即可约的),就等于证明了四色猜测是正确的。
坎泊已证明了不可免集中的前五种轮构形都是可约的,且对于5—轮构形也只有一种情况(既含有相交叉有两条连通链,又不可同时移去两个同色)下,没有证明其是否可约。把坎泊已征明是可约的构形,我们统一叫做K—构形,而把坎泊还没有证明是否可约的构形,我们统一叫做H—构形。现在只要证明这种情况下的各种类型的H—构形都是可约的,也就弥补了坎泊证明中的漏洞。四色猜测也就得到证明是正确的。
构形待着色顶点以外的顶点都是着了色的,且最多只用了四种颜色。这四种颜色的顶点在构形中只能构成6种色链,根据各链间的各种相互关系,我们对坎泊未证明的那种H—构形进行了分类,共分为a,b,c,d四类(如图1)。

这些构形都是极大图,即各个面都是三角形面。在每一个面内都可以增加一个顶点,着上与其相邻的三个顶点颜色以外的第四种颜色;也可以在每条边上增加若干个顶点,并使该两顶点间保持有原来的色链;在不破坏原构形的基本特征(既含有相交叉有两条连通链,又不可同时移去两个同色)的情况下,都可得到若干个甚至无数个与原构形中有相同链间关系的一系列构形;其着色方法也都与原构形的着色方法是相同的(具体怎么进行交换,这里也就不再说了),也都是可约的。所以说图1中的各构形,除了“b 有一条C—D环形链”的一种外,其他几种都是最小的构形,即顶点数最少的构形。

证明时为什么要用最小构形呢,因为最小构形的顶点数、边数都较少,画图和看图都比较方便,它又能代表其他的与其有相同特征构形的图,所以在证明时,用最小构形。但着色却不是证明,着色时一定要把整个图都画出来,一个顶点一个顶点的去着色。
把图1中各图的顶点数减少到九点形构形时,就得到了图2。除了“b 有一条环形链”的构形外,其他各图尽管与图1中各图都有相同的链间关系,但他们都成了可以同时移去两个同色的K—构形了,所以九点形不是a,c,d三类H—构形的最小构形;而只有“b 有一条环形链”这一构形仍不可同时移去两个同色,仍是H—构形。所以图2中“b 有一条环形链”的构形才是b类H—构形的最小构形。


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

注:此文已于二○一八年二月二干四日在《中国博士网》上发表过,网址是:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2018-3-10 10:42 | 显示全部楼层
谢谢你啊,好帖子不顶不行












如果你受够了打工之苦,如果你的生意好难维持,如果你想创业赚大钱,这个项目最适合你!合法长久的大平台将会改变你的一切!你想知道互联网营销自动化盈利模式吗?太震撼了!
免费注册:lyhtx.net.cn/w466867/v2.html
 楼主| 发表于 2018-3-10 13:39 | 显示全部楼层
我不想挣大钱。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 15:01 , Processed in 0.072265 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表