数学中国

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

无割边3—正则平面图可3—边着色的验证

[复制链接]
发表于 2017-4-15 09:22 | 显示全部楼层 |阅读模式
本帖最后由 雷明85639720 于 2017-4-19 01:13 编辑

无割边3—正则平面图可3—边着色的验证
雷  明
(二○一七年四月十五日)

设有n个面的无割边的3—正则平面图是可3—边着色的,那么当面数是n+1时,其是否也可以可3—边着色呢,验证如下:
要把一个面数为n的无割边的3—正则平面图的面数增加为n+1个时,把图中某一个面分成两个就可以达到目的。一个边数是m的面,在其中任两条边中各取一个点a和b,并把a和b用边相连,a和b就变成了两个新的“三界点”,图中就增加了一个面,也增加了三条边(如图1)。只要证明这个图还是一个无割边的3—正则图和仍是可3—边着色的就可以了。

    1、证明这个有n+1个面的图仍是3—正则图
从整个3—正则平面图来说,增加了两个顶点,三条边,图顶点数仍是偶数,边数仍是顶点数的1.5倍。但无割边的3—正则平面图还有一个特点不能忘记,即奇数边面的总个数一定是偶数,才能满足边数是整数的要求。已知原来的图中奇数边面的总个数是偶数,则:
1、1  若取点a和b的边的两个邻接面A和B原来都是偶数条边时,现在则都成了奇数边面,偶数+2仍是偶数,奇数边面的总个数仍是偶数:
1、2  若A和B原来都是奇数条边时,现在则都成了偶数边面,偶数一2仍是偶数,奇数边面的总个数仍是偶数:
1、3  若A和B两面原来的边数是一奇一偶时,则现在仍是一奇一偶,奇数边面的总个数没有发生变化,仍是偶数。
可见,A和B这两个面的边数的改变对3—正则平面图中的奇数边面的总个数并无影响。
现在再看一看被分开成两个面的那个面:
1、4  若被分开成两个面的面原来是奇数条边时,现在的边数仍是奇数条,只能分成一个奇数边面和一个偶数边面。这等于说图中减少了一个原来的奇数边面,除了增加了一个偶数边面外,又增加了一个奇数边面,相当于图中奇数边面的总个数并未发生变化,仍是偶数;
1、5  若这个被分开成两个面的面原来是偶数条边时,现在的边数仍是偶数条:
一种情况是分成两个偶数边面,图中奇数边面的总个数仍没有发生变化。
另一种情况是分成两个奇数边面,等于说图中减少了一个原来的偶数边面,但又增加了两个奇数边面,但偶数+2仍是偶数,奇数边面的总个数仍是偶数;
从这两个方面来分析,结果都是图中的奇数边面的总个数仍是偶数个。这就说明了原来图中的奇数边面的总个数是偶数,现在仍然是偶数,符合无割边3—正则平面图的要求。该图仍然是一个无割边的3—正则平面图,说明了有n+1个面的图仍是一个无割边的3—正则平面图。
2、证明这个有n+1个面的图仍是可3—边着色的图
现在再来看看a和b两点所在的边原来所着的颜色对该无割边的3—正则图的3—边着色有什么影响:

图中因为增加了一个面而增加的两个顶点,虽不能单独构成一个偶圈,但它却是原来图中两条边上的顶点(如图2和图3)。
2、1  两条边原来着色不同的情况:
如果a点所在的边原来着1色,那么这条边一定既是1—2—1边2—色圈上的一条边,又是1—3—1边2—色圈上的一条边;如果b点所在的边原来着2色,那么这条边也一定既是1—2—边2—色链圈上的一条边,又是2—3—2边2—色圈上的一条边;两条边共同都是1—2—1边2—色圈上的边;这条1—2—1边2—色圈上增加了两个顶点,同时也增加了两条边,仍是偶数,还是一条偶数的边2—色圈;所增加的这两条是位于原圈上的边,在1—2—1边2—色圈中,对位于a和b两点同一侧的所有边进行1、2二交换后,一定能给a和b两侧所连的边着上1或2两种颜色(这种对1、2二色的交换与原先着有颜色3的边并无任何关系,并不影响他们的颜色)。给所增加的、把原来的面分成两个面的a—b边着第三种颜色3就可以了(如图2)。


2、2  两条边原来着色相同的情况:
如果a和b两点原来所在的边都着2色,那么这两条边共同都是1—2—1和2—3—2两种边2—色圈上的两条边,这里我们只取一种2—3—2边2—色圈,虽增加了两个顶点,但也同时增加了两条边,该边2—色圈仍是一条有偶数边的边2—色圈。与以上图2中的处理办法相同,所增加的两条边,也一定能着上2或3两种颜色,所增加的把原来面分成两个面的a—b边,也可以着上第三种颜色1(如图3)。
以上两点实际上只是对a和b所在的两条边不仅是处在同一种边2—色圈上而言的,而是a和b所在的两条边又是处在同一个边2—色圈上而言的。我们知道同一种边2—色圈并不是只有一个,若a和b所在的两条边是处在不同的边2—色圈的情况下时,又将如何处理呢。我们来看下面的图4。
2、3        两条边原来不在同一个边2—色圈上的情况:

在图4,a中,a和b两点所在的边原来就不在同一条1—2—1边2—色圈上,这时我们可以把其中一个边2—色圈上的各边的颜色1和2进行互换,得到如图4,b的图,这样的交换对着色为3的边同样并无影响。我们发现,由于这一交换,图4,b的图中,虽然a和b两点所在的边仍处在不同的1—2—1边2—色圈上,但却又处在了同一条1—3—1(或2—3—2)的边2—色圈上了。这时,就与以上2、1和2、2中所谈的情况完全相同了,可以用同样的方法进行处理。最后得到可3—边着色的图(如图4,c)。
这也就证明了任何一个无割边的3—正则平面图都是可3—边着色的。
以上我们是对有n+1个面的无割边的3—正则平面图进行证明的,同样的也可以对有n-1个面的无割边的3—正则平面图进行证明是可3—边着色的。这只要从有n个面的图中去掉一条边即可办到。
现在已经证明了无割边的3—正则平面图都是可3—边着色的,这也就等于验证了任何无割边的3—正则平面图也都是可3—边着色的结论是正确的,也就验证了任何无割边的3—正则平面图都是可4—面着色的结论也是正确的。最终也就验证了地图四色猜测是正确的。


雷  明
二○一七年四月十五日凌晨于长安

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

本帖子中包含更多资源

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

x
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

GMT+8, 2025-7-31 01:49 , Processed in 0.098223 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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