[原创]我对Mycielski操作过程的再研究

雷明85639720

[watermark]

我对Mycielski操作过程的再研究
——兼论四色猜测的证明
雷  明
（二○一三年十二月二十二日）
(图请看上面的DOC文件）
1、杨博士教给我Mycielski—操作过程
数学家狄拉克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色图。”以上是厦门大学的杨卫华博士给我介绍Mycielski—操作时所发的一个图片里的话。这里所说的“不含三角形”的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称为M—操作。
这一操作过程是可以递推的，即可以多次进行的。杨博士说：“我发给你的那个图片——Mycielski—图的构造方法（我们称那个构造方法叫Mycielski操作），按着那个方法重复进行Mycielski操作，每操作一次色数都增加1，且团数不变（每一次都是保持无导出三角形，故团数不变），比如以5-圈出发，用一次Mycielski操作色数变为4，对得到的图再进行一次Mycielski操作色数就变成了5，以此类推会出现6色无三角形图，7色无三角形图，8色，9色，……，这也就是说图色数不可能被团数的线性式（团数常数倍+常数）界定上界”，杨博士这里所说的团数，我在的论文中都称为图的密度。他还说：“Mycielski构造的图说明：存在无三角形且色数任意大的图”，并说：“M—操作可以以任何图为基图，而不是仅仅以圈为基图，M—操作的结果就是使得所得图比基图色数增加1。”这实际上就是说，进行M—操作时的基图的密度可以是任意的，不一定都得是密度小于3的图。
2、我进一步对Mycielski—操作过程的理解
以上的M—操作过程中“将vi与ui所有邻点及v0相连，1≤i≤n”一句说得很不明确，没有办法操作。在杨博士给我介绍的bondy教材中译本中对于M—操作过程又是这样说的：“设Gk的顶点是v1，v1，……，vn，从Gk发出如下构作一个新图Gk＋1：添加n＋1个新顶点u1，u1，……， un，v,然后对适合1≤i≤n的i，把ui同vi的邻点以及v都连接起来。”这里的“把ui同vi的邻点以及v都连接起来”同样也不明确，也难以操作。同一个M—操作法，而在李建中译的《图论导引》一书中则是：“由简单图G产生包含G的一个简单图G＇。从顶点集合为｛v1，……，vn｝的图G开始，添加顶点U＝｛u1，……，un｝中的顶点和一个另外的顶点w，然后添加一些边使得ui与NG(vi)中的顶点都邻接，最后令NG(w)＝U。”M—操作主要说的是要构造一个“无三角形且色数任意大的图”，但这里说的“然后添加一些边使得ui与NG(vi)中的顶点都邻接”虽然很明确，但不确切，甚至是错的。因为无三角形的图中的最大团肯定是K2，添加顶点与边之后仍要保持图中的最大团是K2，如果“添加一些边使得ui与NG(vi)中的顶点都邻接”，这将会产生K3团，这是不合适的。所以我认为应是在继续“添加一些边之后，使u1，……，un与w生成一个n—星，并对适合1≤i≤n的i，使ui尽可能多的与基图Gk中的顶点相连，但不能使ui与Gk中的最大团Kω（ω≤k）构成更大的团，ui至少要与最大团Kω要有一个顶点不相邻。”这样，才能保证最后所生成的图既仍保持与原基图有相同的最大团（原基图最大团是K2时，就是无三角形的图），但其色数又是比原基图大1的k＋1的图 。


李建中所译的《图论导引》一书中有两例：从2—色图K2开始，运用一次M—操作，得到3—色的图C5（5—圈），如图1。然后再把M—操作运用到C5上，产生了4—色的Crotzsch图，如图2。
从以上两个图的实际中可以看出，我在上面对M—操作的的理解是对的。
3、进行一次M—操作过程图的色数就增加1
在进行了一次M—操作过程后，图的色数为什么会比原基图的色数大1呢。其原因就是：
其一、因为原基图中已着有颜色，现在在进行M—操作过程中所添加的n—星的n个星点又互不相邻，是可以同化为一个顶点，染成同一种颜色的，但把这n个顶同化成一个顶点后，该顶点又与原基图中的着有各种颜色的顶点都成为相邻了，所以只有着另外一种颜色。由于n—星的中心顶点w与原基图中的任何顶点都不相邻，给其着上原基图中已用过的一种任何颜色完全是可以的。
其二、若把原基图同化成最小完全同态Kk后，n—星的n个顶点中任何一个都与这个最小完全同态Kk至少有一个顶点不相邻，当然这k个顶点一定是可以同化到这个Kk完全同态中去的，即是可以同化到原基图中去的。但n—星的中心顶点w这时却又变成了与这个最小完全同态Kk的所有顶点相邻了，也只有着另外一种颜色了。
从这两点都可以看出图的色数一定是要比原基图大1的。
现在把M—操作用图来表示如图3。图中的5—圈用了红、黑、兰三种颜色。以上其一、其二中的两种着色如图4和图5所示。图4中把所有的u都着绿色（第四种颜色），把顶点w着基图中已用过的任何一种颜色（这里用的是黑色）；图5中是把所有的u都与在基图中相对应的v着以相同的颜色，而把顶点w着以第四种颜色绿色。



4、关于图的色数的界的问题
通过以上的分析可以看出，在一个图的密度不变的情况下，其色数是随着对其所进行的M—操作过程次数的增多而增多的。但是在这里我们要看到的是，只要进行了一次M—操作过程，图就不再是原来的基图了，尽管其密度没有发生变化，但也不是原来的图了，因为图中的顶点数比原来的基图多了一倍还要多1。
从总体上看，图的色数是没有上界的。因为图的基本参数——图的密度ω本身就是一个变数，可以是无穷大的。而图的色数与图的密度是有着关系的。
但从个体上看，对于一个具体的图，其密度则是一个具体的值，其中的不可同化道路的条数也是具体的。一个图是否是由某基图进行过几次M—操作，除了画图的人外，着色的人是不可能知道的。但图已经给出，是否进行过M—操作，进行了几次，总是有一个具体数的。密度，不可同化道路的条数，进行过M—操作的次数都是具体的。
所以说从同密度的一类图看，图的密度又是有界的。其界是：
ω≤γ＝ω＋S＋I≤ ＋I （0≤S≤ω/2，I为自然数）
式中γ、ω、S、 I、 分别是图的色数，图的密度，构成联的不可同化道路的条数、进行M—操作过程的次数和向下取整的符号。
5、平面图色数的界与四色猜测的证明
M—操作过程所添加的顶点与边中有一个n—星，星的密度本身就是2，所以M—操作过程最小是从密度是2 开始的。除了对K2图（密度是2）和p3道路（密度也是2）进行了一次M—操作过程后所得到的图仍是平面图（如图1和图6）外，其他对密度为2 的图进行一次或多次M—操作过程，以及对密度大于2的团或图进行M—操作过程，所得到的图都是非平面图。图2就是一个非平面图，对K3进行M—操作过后所得到的图，也是非平面图，如图7。


我们已经画出了在图2中4—色的Crotzsch图基础上，再进行一次M—操作过程后得到的密度是2但色数却是5的图；也画出了色数分别是4和6的密度是4的图在进行了一次M—操作过程后所得到的密度仍是4但色数却分别是5和7的图。它们都是非平面图。
由于以上的原因，所以可以说M—操作过程对于除了K2图和p3道路外的平面图都是不适用的。平面图的色数的界应该是：
ω≤γ＝ω＋S＝       （0≤S≤ω/2）
式中符号同前。由于平面图的密度只有1、2、3、4四种，代入0≤S≤ω/2中并向下取整得：0≤S1＝ ＝0，0≤S2＝ ＝1，0≤S3＝ ＝1,是乎0≤S4＝ ＝2，但可以证明实际上在密度为4 的平面图中根本就不可能存在不可同化道路的，其中只要有一条饱和道路，图就变成了密度为4的非平面图。即在平面图时有0≤S4＝0，所以平面图的色数的界还可以写成：
　　　　
有了这一点对证明四色猜测已经足以够用了。可以看出，任何密度下的平面图的色数都是没有大于4的。这就证明了四色猜测是正确的。
    6、M—操作过程的实质
然而进行了一次M—操作过程的图1和图6的色数为什么是3，比其基图的色数都大1呢，用我的不可同化理论是很容易解译的。因为对其进行M—操作的过程也就是对其最大团K2添加一条不可同化道路的过程，使图中都产生了5—圈，是奇圈，奇圈着色时一定得要用3种颜色。其色数的增加，既是因为对K2团进行了M—操作的原因，也是因为对K2团添加了一条不可同化道路的原因，当然也是因为5—圈是一个奇圈的原因。
除了对K2图和p3道路进行M—操作的过程，同时也是对其中的K2团添加了一条不可同化道路的过程外，对其他任何团或任何密度的图，也包括对密度为2的其他图进行的M—操作过程都是与不可同化道路没有关系的。不可同化道路是一条饱和道路，其上的任何顶点都至少要与最大团Kω中有ω－2个顶点相邻。在M—操作过程中所添加的n—星的任何两个星点与n—星的中心顶点w虽都构成了一条道路，但n—星的中心顶点w却与最大团中的任何顶点都不相邻，根本不可能成为饱和道路。这一点只有在对K2和p3进行M—操作过程时才能同时满足，所以对K2和p3进行M—操作过程同时也是对该团添加了一条不可同化道路。
无论对于密度是多大的图Gω进行M—操作过程，实际上都是在对其最小完全同态Kk（k＝ω＋ S，S意义同前）中的任何一个K2团添加不可同化道路的过程。因为两个星点ui与uj与顶点w都都与Kk团中的一个K2团构成了一个5—圈，可以把5—圈中的顶点ui与uj同化到K2团中去，也就是同化到Kk团中去，而把顶点w作为同化不到那个K2团中去的顶点的，这时由于w与Kk团中的所有顶点均相邻，所以也只能着原基图中已着的k种颜色以外的另一种颜色。这就是M—操作的实质，也是该操作与不可同化道路理论相联系的地方。
雷  明
二○一三年十二月二十二日于长安

任道远

图那？
   如果说别的证明题可以没有图，四色猜想的证明没有图，那就等于没有证明！

雷明85639720

看图请点击上面的DOC文件，我不是在文章的开头已经说了吗。雷明

任务重

打不开！
    最好随同论文一起画出来！

雷明85639720

以前我总是这样发图的，今天怎么又打不开了呢，好象昨天我还打开过。我试一试看能不能满足你的要求。雷明

雷明85639720

我没办法把图发上来。给你一个地址，你去我的博客中看吧。雷明的博客：
http://blog.sina.com.cn/leiming1946。雷明

雷明85639720

我实在是没有办法了。你只能去我的博客里看了。

雷明85639720

你是否可以给我教教给这里发图的方法。我的图是用附件里的“画图”来画的，如何把这样的图发到这里来呢。雷明

任在深

下面引用由雷明85639720在 2013/12/25 03:01pm 发表的内容：
你是否可以给我教教给这里发图的方法。我的图是用附件里的“画图”来画的，如何把这样的图发到这里来呢。雷明

俺也不会！
不必着急！
慢慢来吗。

雷明85639720

任朋友，现在可以打开了。雷明