数学中国

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

不可免H—构形间的相互转化

[复制链接]
发表于 2017-4-22 06:51 | 显示全部楼层 |阅读模式

不可免H—构形间的相互转化
雷  明
(二○一七年四月二十一日)

二○一六年年底前我构造了一个H—构形的不可免集。如图1。

c类和d类构形的解决方法都是转型交换。
c类构形从顶点1逆时针交换B—D后,是一个可以同时移去两个同色D的DCD型的构形(如图2,a),先从顶点4交换D—A,后从顶点1交换D—B,即可空出D给V;但c类构形从顶点3顺时针交换B—C时,却得到一个有环形链A—B的类似b类的构形(如图2,b),可再按b类构形的解法,交换环形的A—B链内、外的任一条C—D链,使图变成K—构形而得解。当然了,图2,b进行一次逆时针交换C—B后也会得到c类构形,因为这一交换正好是前次顺时针交换B—C的逆过程。
d类构形从顶点3顺时针交换B—C后,是一个可以同时移去两个同色C的CDC型的构形(如图3,a),先从顶点5交换C—B,后从顶点3交换C—A,即可空出C给V;但d类构形从顶点1逆时针交换B—D时,却也得到一个有环形链A—B的类似b类的构形(如图3,b),可再按b类构形的解法,交换环形的A—B链内、外的任一条C—D链,使图变成K—构形而得解。同样的,图3,b进行一次顺时针交换后,也可得到d类构形。


a类构形的解法是交换环形的A—B链内、外的任一条C—D链,使图变成一个K—构形而得解。但无论是逆时针,还是顺时针,只要进行一次转型交换,图都变成有环形链A—B的类似b类的构形(如图4)。当然了,对图4的两图分别进行与前次交换相反方向的交换,图也就变成了原来的a类构形。
还有既可以归入a类构形,又可归入b类构形的敢峰—米勒图(如图5,a),正常的解法是从环形的A—B链内、外交换任一条C—D链(按a类构形看待时),或从环形的C—D链内、外交换任一条A—B链(按b类构形看待时),都可以使图变成K—构形而得解。但若对其进行一次转型交换时,图也就变成了有环形链A—B的类似b类的构形(如图6)。图6的图不但进行了前一次交换的逆交换后,可以得到敢峰—米勒图,而且继续进行同方向的转型交换,也可得到类似敢峰—米勒图的构形(如图7),其主要标志是图中除了具有H—构形的特点外,还具有环形的A—B链和环形的C—D链两条环形链(图中两个加粗了边的圈)。


b 类构形的解法是交换环形的C—D链内、外的任一条A—B链,使图变成一个K—构形而得解。当然也可以进行一次转型交换,使图变成一个可以同时移去两个同色的K—构形。这里的所画的b 类构形的图并不是最小的,而最小的应是“九点形”图(如图5,b),为了整齐,我把它们都画成了“十五点”形。


从上面可以看出,不但各构形间可以通过转型交换相互转化,而且都可以转化成b类构形,统一用解决b类构形的办法进行解决。另外,除了b类构形和敢峰—米勒图外,别的构形也都可以通过转型交换,转化成可以同时移去两个同色的K—构形。因为b类构形的图1,b和图5,b就是赫渥特图的简化和再简化,所以,从以上的研究中可以看出赫渥特图和敢峰—米勒图是两个非常重要的图,不能忽视。图1中的a、c、d三类构形已是最小的构形了,不能再简化了。如果把其再简化,则分别就变成了图8的“九点形”,都成了可以同时移去两个同色的K—构形。

图8中,对于B—D和B—C两链的交换来说,图8,a可以任意进行交换;而图8,b则必须先从1交换,后从3交换;图8,c则必须先从3交换,后从1交换;最后才都能达到同时移去两个同色B的目的,把B给V 着上。但若只交换一次时,图8,a变成了一个K—构形;而图8,b和图8,c却分另变成了DCD型或CDC型的如同图5,b一样的最小的b类H—构形。当然了,图5,b的最小的b类H—构形进行一次转型交换后,也可以得到图8,b和图8,c。说明了图8,b和图8,c的K—构形与图5,b的最小的b类H—构形也是可以相互转化的。

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


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

本帖子中包含更多资源

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

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

本版积分规则

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

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

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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