数学中国

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

施行断链交换的必要条件(修改稿)

[复制链接]
发表于 2019-11-12 10:32 | 显示全部楼层 |阅读模式
施行断链交换的必要条件(修改稿)
雷  明
(二○一九年十一月十日)

解决有环形链的5—轮构形染色困局时用的是断链交换法。施行这种交换时,要求的条件是环形链必须是经过了构形围栏顶点的环,且5—轮构形染色困局的关链顶点又必须分别处在相对应环的两侧。

1、什么是5—轮构形染色困局的关键顶点呢?即5—轮构形染色困局中的顶点2A(即双环交叉链的共同起始顶点),顶点8A(即双环交叉链的交叉顶点),这就是一对关键顶点;另一对关键顶点是5—轮构形染色困局中的顶点5C和顶点4D(即分别是两条双环交叉链的尾端顶点)和顶点7C和8D(即分别是两条双环交叉链中部相邻的顶点),这也是一对关键的顶点(如图1)。当然待着色顶点(图中未画出)和围栏顶点也可以叫做关键顶点,这样一个染色困局构形中就有9个关键顶点。但关键顶点8A和6C—7D边(链)可以有多个。
2、图2中有经过了构形围栏顶点1B—2A—3B的A—B环形链,可以在A—B环形链两侧交换C—D链,施行断链交换,使染色困局构形变成非染色困局构形;但图中的环形的C—D链却不经过构形的围栏顶点,就不能在其两侧施行断链交换,交换了也不能使构形成为非染色困局构形。图2就是埃雷拉图,只能在A—B环两侧施行断链交换解决问题。

3、图3和图4中都有两种经过了构形围栏顶点的环形链A—B和C—D。但图3有一对关键顶点2A和8A是分布在环形链C—D的同一侧,交换了环形的C—D链两侧的任一条A—B链,图都不会变成非染色困局构形的。这种图的解决只能是在环形的A—B链两侧任意交换一条C—D链解决问题。而图4中的顶点2A和8A却是分布在环形链C—D的两侧,但交换了C—D环两侧的任一条A—B链后,却也不会使染色困局得到解决,反而交换了A—B环两侧的任一条C—D链后,却会使困局得到解决。这又是什么原因呢?后面我们再分进行析。
4、目前我们还没有发现两种环形链同时存在,但关链顶点6C—7D边(链)和5C—4D边(链)同时处在A—B环形链同一侧的例子,而且可以证明根本就不会存在这样的构形。因为6C—7D边(链)总是紧紧伴随着顶点2A或8A(可能有多个交叉顶点出8A)而存在的,顶点1B和3B又直接分别与5C和4D相邻,任何一条经过1B—2A—3B的A—B环形链,都必须经过图1中5C和4D内侧(如图5),这样就至少有与2A紧相邻的一对6C—7D边(链)是分布在A—B环形链内侧的,与5C—4D边(链)是分别处在A—B环形链的两侧。从图2的构形中就可一明显的看出这一问题。所以关键顶点6C—7D边(链)和5C—4D边(链)同时处在A—B环形链同一侧的的情况的构形,是不会存在的。

5、但为什么会存在两种环形链同时存在,但关键顶点2A和8A同时处在C—D环形链同一侧的构形呢?如果有环形的A—B链通过并包含了8A,有可能伴随着8A的C—D边(链)就与5C—4D构成了环形链,这时的关键顶点2A和8A就处在C—D环形链的同一侧(如图6)。图中虽有环形C—D链,但不能交换其内、外的任一条A—B链解决问题,而只能交换A—B环形链内、个的任一条C—D链才能解决问题,就是因为关键顶点2A和8A是处在C—D环形链的同一侧的原因。
6、当两种环形链同时存在的图3和图4,图3的2A和8A是同时处在C—D环形链的同一侧,图4的2A和8A是分别处在C—D环形链的两侧,为什么解决的办法却都是交换A—B环内、外的任一条C—D链呢?这不是相互矛盾的吗?
首先看两个图,图3中的双环交叉链只有一个交叉顶点(如图7),与双环交叉链的起始顶点2A分布在C—D环形链的同一侧(如图3);所以图3只能交换A—B环形链两侧的任一条C—D链解决问题。而图4中的双环交叉链却有三个交叉顶点(如图8),这三个顶点本身就是分布在C—D链的两侧的(如图4),这时双环交换链的起始顶点2A总是和至少一个交叉顶点是分布在C—D链的同一侧的。这就与必要条件“关链顶点必须分别处在相对应环的两侧”产生了矛盾。既然有了矛盾,当然就不能在C—D环形链内、外交换A—B链了,而只能在A—B环形链内、外交换C—D链了。

图3和图4的解法看起来似乎是有矛盾的,但对于各图来说,与解决这类构形的原则却是不矛盾的,交换的链都是关链顶点分别处在相对应环的两侧的链。这是因为有A—B环形链的构形中6C—7D边(链)和5C—4D边(链)总不可能同时处在A—B环形链同一侧的原因。
7、图2中的埃雷拉图的解决办法虽然与图3的解决办法相同,但图2却是一个只有一条环形链的构形,它的解法应看作是只有一条环形链的构形的断链交换法。而不就看作是有两条环形链的解决办法。

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


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

本帖子中包含更多资源

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

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

本版积分规则

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

GMT+8, 2024-3-28 17:17 , Processed in 0.073242 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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