[原创]对Mycieiski—操作过程研究之三

雷明85639720

[watermark]

对Mycieiski—操作过程研究之三
雷  明
（二○一三年十二月二十九日）
1、Mycieiski—操作的实质
大家都知道对任何图进行一次Mycieiski—操作（简称M—操作）过程之后，得到的图仍保持原基图的密度ω，但其色数γ却比原基图增大1。设原基图G有n个顶点，色数是γ（γ＝ω＋S，S是图中可构成联的不可同化道路的条数，S≤＜ω/2＞,＜＞表示其中的数字向下取整），在G外给出一个n—星（中心顶点用w表示），把星点ui（1≤i≤n）尽可能多的与基图中的顶点vi（1≤i≤n）用边相连，但不能使图中不能出现大于基图的最大团Kω的情况，以保证图的密度不发生变化。这就是对G进行了一次M—操作的过程。这时图的密度ω虽没有变化，但其色数却变成了γ＋1。M—操作过程实际上就是在对G的最小完全同态Kγ（γ＝ω＋S，S意义同前）中的任何一个K2团添加不可同化道路的过程。因为任两个星点ui、uj以及n—星的中心顶点w都与Kγ团中的一个K2团构成了一个5—圈。5—圈中对于任一个K2团都有一条不可同化道路，我们可以把5—圈中的两个端点顶点ui与uj同化到K2团中去（当然ui与uj也就是同化到了Kγ团中去了），而把顶点w作为同化不到那个K2团中去的顶点的。这时由于w与Kγ团中的所有顶点均变成相邻的了，所以也只能着原基图中已着的γ种颜色以外的另一种颜色，这时的图的色数就成了γ＋1。这就是M—操作的实质，也是该操作与不可同化道路理论相联系的地方（任何图中只要有几条不可同化道路构成了联，就有几个顶点同化不到最大团中去，图的色数就一定比其密度大几）。
    2、任意图着色色数的界
从上面1中可以看出，在一个图的密度不变的情况下，其色数是随着对其所进行的M—操作过程次数的增多而增多的。但是在这里我们要看到的是，只要进行了一次M—操作过程，图就不再是原来的基图了，尽管其密度没有发生变化，但也不是原来的图了，因为图中的顶点数比原来的基图多了一倍还要多1。从总体上看，图的色数是没有上界的。因为图的基本参数——图的密度ω本身就是一个变数，可以是无穷大的。而图的色数与图的密度却是有着关系的。从个体上看，对于已给出的一个具体的图，其密度则是一个具体的值；其中的可构成联的不可同化道路的条数也是一定的；是否是由某基图进行过几次M—操作，都是已经确定的；但是否所有的人都能看出来这些参数的值具体是多少，这就要看各个人的水平了。但只要图已经给出，以上这几个参数就已经是确定的了。又因为图中不可同化道路的条数是与图的密度有关的，单从同一密度的一类图来看，图的色数又是有界的。其界是：
ω≤γ＝ω＋S＋I≤＜1.5ω＞＋I（0≤S≤＜ω/2＞，I≥0）（1）
式中I是进行M—操作的次数，其它各符号同前。
3、平面图着色色数的界
M—操作过程中是在原基图G外添加了n—星，星的密度是2,所以M—操作只能是对于密度是大于等于2的图才可进行的。n—星的星点最多可与基图最大团Kω中的ω－1个顶点相邻，而中心顶点w却与基图最大团中的任何顶点都不相邻，所以由两个星点ui、uj与其中心顶点w构成的道路，对于密度为大于等于3的图来说，就不可能成为不可同化道路，图的色数的增加完全是由于进行M—操作所引起的，而且进行了M—操作后的图都是非平面图；但对于密度为2 的图来说，该道路却是一条不可同化道路，图的色数的增加同时也是不可同化道路所引起的（由不同的原因引起了同一结果，所以以上的公式（1）中的S和I两项只能取其一，这里我们取S）；而对于密度等于2 的图，除了K2的p3进行了M—操作后的图是平面图外，其它的图进行了M—操作后的图也都是非平面图。
任何图都有两个最基本的参数，即亏格和密度，M—操作虽然图的密度没有发生变化，但图的亏格有可能发生变化。从这个意义上可以说，要保证平面图在进行了M—操作后所得到的图的密度与亏格都不发生变化，除了K2图和p3道路外，任何平面图都是不可能达到的。但非平面图已不是四色猜测所研究的对象。也可以说，要保持图既是平面图，密度又不发生变化，除了K2图和p3道路外，对任何平面图都是不能进行M—操作的。因此，当亏格为0的平面图在不进行任何M—操作时，即上式中的I＝0时，公式就变成
ω≤γ＝ω＋S＝＜1.5ω＞（0≤S≤＜ω/2＞）    （2）
这就是平面图的色数的界。也是我们从同化理论中得出的图的色数的界的公式。
虽然K2图和p3道路是可以进行M—操作，但在进行了一次M—操作后的图仍是平面图，其色数只是3，是不大于4的，这对于证明四色猜测是没有影响的。
4、四色猜测的证明
要证明四色猜测，现在就只要证明任何密度下的平面图中的可构成联的不可同化道路的条数S不大于1就可以了。
当ω＝1时，图没有边，0≤S≤＜ω/2＞＝＜1/2＞＝0；
当ω＝2时，0≤S≤＜ω/2＞＝＜2/2＞＝1
当ω＝3时，0≤S≤＜ω/2＞＝＜3/2＞＝1
当ω＝4时，是乎0≤S≤＜ω/2＞＝＜4/2＞＝2，但可以证明（略），当ω＝4时，图中只要有一条不不可同化道路，图就不是平面图了，而成为非平面图。所以在ω＝4的平面图中，仍有0≤S≤0；
把以上各密度下的平面图的不可同化的条数S代入（2）式中去，都可得到色数ω≤4的结果。这就证明了四色猜测是正确的。
雷  明
二○一三年十二月二十九日于长安