米歇尔斯基操作的实质

雷明85639720

米歇尔斯基操作的实质
雷  明
（二○一五年十月十五日）

1、什么是米歇尔斯基操作
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是u1，u2，……，un,，添加点v1，v2,……，vn和点v0。将vi与ui所有邻点及v0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。这里所说的不含三角形的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称M—操作。且这一操作过程是可以递推的，即可以多次进行的。每进行一次M—操作，图的密度并不发生变化，但其色数却增加1。所以厦门大学的杨卫华博士说：“Mycielski构造的图说明：存在无三角形且色数任意大的图”。实际上，进行M—操作时的基图的密度可以是任意的，不一定都得是密度小于3的图。的确，我们也画出了以K2为基图（密度为2）经过一次M—操过程后得到的密度仍是2 但色数却是3的5—圈，并在5—圈的基础上，再经过一次M—操作过程后得到的密度仍为2但色数却是4的Crotzsch图，在此基础上再经这一次M—操作过程又得到了密度仍为2的，但必须用5种颜色（色数是5）来着色的图；同时也画出了以在K4团外有两条已构成联的不可同化道路的图（其密度是4，色数是6）为基图而只进行了一次M—操作过程后所得到的密度仍为4，但其必须用7种颜色（色数是7）来着色的图等。
2、米歇尔斯基操作的实质
上面所说的“由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法”很不明白，难以操作。我们通过对米歇尔斯基操作的研究认为，其实质是在一个密度是ω、色数是γ、顶点数为v的连通图（基图）外增加一个星形图（密度是2），其点数u比基图的顶点数多1，即u＝v＋1。然后把星形图中各星点顶点ui与基图中相应顶点vi的所有邻点相连接，但ui与vi不相连，使每一个星点顶点ui最多只能与基图中含有vi顶点的最大团Kω中的ω－1顶点相邻，以保证图的密度不变。但操作过程中星形图的中心顶点u0与基图中的顶点始终是不相邻的。这样做的结果，所得图的密度并未发生变化，但其色数却比原基图的色数增大了1。也就是说在施行了M—操作后所得的图的密度未变，但色数比原基图的色数却大了1。M—操作后所得图的色数只所以比原基图的色数增大1，可以通过以下两个方面来理解。
第一，由于增加的星形图的各个星点顶点均不相邻，所以这些星点顶点是可以同化成一个顶点的，同化后所得到的一个新顶点就与基图中着有各种颜色的顶点都相邻了，这个新顶点只有着上原基图所用颜色以外的另一种颜色，使得色数比原基图的色数增大了1（因星形图的中心顶点与基图中各顶点均不相邻，所以给其着上基图中已用过的任一种颜色就可以了）。
第二，由于M—操作时，是不允许对应的ui与vi相连的，所以可以把增加的星形图的星点顶点ui与原基图中对应的vi顶点着以相同的颜色，这时星点顶点也就点用完了原基图中所使用的颜色种类，所以也只能给增加的星形图的中心顶点u0着上另外一种颜色，从而比原基图增加了一种颜色图。
3、M—操作是不会影响四色猜测和证明的
厦门大学的杨卫华博士认为“Mycielski构造的图说明：存在无三角形且色数任意大的图”，以此来企图否定我们爱好者对四色猜测的证明，或者说他就是在否定四色猜测。但他没有看到平面图在施行了M—操作后，除了个别图外，绝大部分所得到的图均是非平面图，他们根本就不是四色问题研究的对象。
通过作图，并对其进行M—操作，可以看出，所有的树图，以及只含有一个3—圈而不有其他圈的图在施行了一次M—操作后仍是平面图外，其他的平面图施行了一次M—操作后匀是非平面图，都不是四色问题所研究的对象了。而以上两种图在施行了第二次M—操作后，所得图也变成了非平面图，也不是四色问题研究的对象了。
树的密度是2，色数也是2，施行一次M—操作后，仍是密度是2的平面图，但色数变成了3，是不大于4的；含有一个3—圈，但不含有别的圈的图的密度是3，色数也是3，施行一次M—操作后，仍是密度是3的平面图，但色数变成了4，也是不大于4的；这两种图再施行第二次M—操作后，则都成了非平面图，也就不是四色问题研究的对象了。
从此，可以看出，米歇尔斯基操作是不会影响对四色猜测测的证明的。


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

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

雷明85639720

，，，，，，，，