“E族构形”的放大

zhangyd2007@soh

《四色猜想中染色困局构形的4-染色》之 参考文献【8】



“E族构形”的放大

"E- Family Configuration" Enlargement

     张彧典  张利翀



在《一种试探式的平面图四染色》【1】中，哈米什·卡尔和威廉·考凯讨论了CK图的嵌入放大问题，他们指出：

In "A Tentative Four Coloring of Planar Graphs" [1], hamish Karl and William Cocay discussed the embedding amplification of CK graphs. They pointed out that:

“导致算法2.1循环的G中的Kempe链的所有边仍然存在于G’中。因此，对于输入图G’，算法2.1循环，其周期为20的倍数。图6显示了一个例子。

"All edges of the Kempe chain in G that caused the algorithm 2.1 loop still exist in G'. Therefore, for the input graph G', the cycle of algorithm 2.1 is a multiple of 20. Figure 6 shows an example.

这些结构可以用来生成大量的平面图，以使得算法2.1循环。他们都是基于CK图中的Kempe链。我们还没有找到能够让算法2.1循环的其他平面图。

These structures can be used to generate a large number of plan views to make algorithm 2.1 loop. They are all based on the Kempe chain in the CK diagram. We have not found any other  plan view that can loop algorithm 2.1.

问题：是否还有任何不是基于CK图的平面图会使得算法2.1循环呢？”

Question: Is there any plan view that is not based on CK graph that will make algorithm 2.1 cycle? "

以上论述中，（ In the above discussion），

1、“算法2.1”就是米勒她们给出的导致构形周期循环的H染色程序；

1. "Algorithm 2.1" is the H staining program that Miller and his colleagues gave to cause the cycle of configuration cycle

2、CK图就是《四色猜想“染色困局构形”的可约证明》中的E1构形；

2. CK graph is the E1 configuration in the reducible proof of the four-color conjecture "dye dilemma configuration";

3、需要解决两个问题：

3. Two problems need to be solved:

一是能否找到“基于CK图中的Kempe链”而且“能使算法2.1循环的其他平面图”？

First, can we find "Kempe chain based on CK graph" and "other plan view that can make algorithm 2.1 cycle"?

这个问题，我们已经找到了与E1构形同胎的另外3个构形，它们也是都是“使算法2.1循环的” 平面图。

For this problem, we have found 3 other configurations identical to E1 configuration, which are also "the plan  view that makes algorithm 2.1 cycle".



二是“是否还有任何不是基于CK图的平面图会使得算法2.1循环呢？”

The second is "is there any plan that is not based on CK graph that will make algorithm 2.1 cycle?"

现在，就第二个问题讨论如下。

Now, let's discuss the second question as follows.

我们认为，这个问题的答案可以分四类解析。

We believe that the answer to this question can be divided into four types of analysis.



第一类，四色构件嵌入CK图中的任意三角形内部，如图1所示：



In the first category, the four-color component is embedded inside any triangle in the CK diagram, as shown in fig. 1:

514980639825724674

                                  图1



这个构形是在CK图的任意一个三角剖分（红色）中嵌入一个四色构件（蓝色），由于它没有破坏原来构形的十折对称主构件及其色图，已知的A-B环仍然存在，因此用Z染色程序可约。

In this configuration, a four-color component (blue) is embedded in any triangulation (red) of CK graph. Because it does not destroy the ten-fold symmetric main component and its color diagram of the original configuration, the known A-B ring still exists, so it can be reduced by Z coloring program.

                              

第二类：四色构件嵌入CK图中的任意四边形，如图2所示：

Type ii: four-color components are embedded into any quadrilateral in CK diagram, as shown in figure 2:



                         图2

图2中：红色、蓝色、粉红色所示的四色构件嵌入红色五边形黑色四边形所示E1构形的放大构形外部，这时，不管是蓝色的A-C链或者是红色色链联通的B-D-B链存在，都不会影响整个构形的周期循环，这是因为：

如图3，在施行H染色程序时，一定涉及A-D---B-D---B-C---A-C四条色链，依次用橙色-绿色-蓝色-红色区分，它们在十折对称结构中留下的痕迹，组成一个图样，只剩下12条边没有被覆盖，如虚线所示 。

As shown in fig. 3, when implementing the h dyeing procedure, four color chains, a-d-b-d-b-c-a-c, must be involved, which are distinguished by orange-green-blue-red in turn, and their traces in the 10-fold symmetrical structure form a pattern, leaving only 12 edges uncovered, as shown by dotted lines.

ab3ddbe906e092bf0ed9cab76140cde  be24404eb1414bd18519fbd42f2324c         

     图3 染色痕迹图样                 图 4十折对称模板

Fig. 3 dyeing trace pattern        Fig. 4   10-fold symmetrical template



然后，我们把图样放到图4所示的十折对称几何结构模板①处，用橙色显示出来；

Then, we put the pattern on the 10-fold symmetrical geometric structure template ① shown in fig. 4 and show it in orange.                                

我们再次把这种图样从橙色①处逆时针旋转144度，到达图4中的红色②处，这时，又有8条边被覆盖，如图4中标有2的红色边，这时还剩下4条边没有被覆盖了。

Once again, we rotated the pattern 144 degrees counterclockwise from orange ① to red ② in fig. 4. at this time, another 8 edges were covered, as shown in the red edge marked 2 in fig. 4, and then there were still 4 edges left uncovered.

我们继续把这种图样从红色②处逆时针旋转144度到达绿色③ 处，这时，又有3条边被覆盖，如图4中标有3的绿色边，最后剩下1条边还没有被覆盖。

We continue to rotate this pattern counterclockwise 144 degrees from red ② to green ③, at this time, three more edges are covered, as shown in the green edge marked 3 in fig. 4, and finally the remaining one edge is not covered.

我们继续把这种图样从绿色③处逆时针旋转144度到达④处，这时，最后1条边也被覆盖了，如图4中标有4的蓝色边，

We continue to rotate the pattern counterclockwise from green ③ to ④ by 144 degrees. At this time, the last edge is also covered, as shown in the blue edge marked 4 in Figure 2.

当我们运用上述覆盖理论对图5所示的（红色E1的放大图）进行覆盖时，不难发现，绿色的五边形五条边没有被覆盖，说明任何四色构件嵌入这样的五条边所在的四边形，都不会影响这种放大构形的周期循环。

When we apply the above covering theory to cover the (enlarged picture of red E1) shown in Figure 5, it is not difficult to find that the five sides of the green Pentagon are not covered, indicating that any four-color component embedded in the quadrilateral where the five sides are located will not affect the cycle of this enlarged configuration.





图5（与图1基本框架一样）

Fig. 5(same as basic frame of fig. 1)

为什么会出现这样的情形呢？考察一下图5：放大构形的五边形围栏与最小E1构形的五边形围栏以及它们所在的四边形四个顶点染色完全相同，各条边也相同，是E1构形中的边在向外拉长，所以在四次颠倒染色覆盖时不会涉及到它们，变成无用边。这表明，没有必要讨论四色构件嵌入E族构形的放大构形的情形，只需要讨论嵌入最小E族构形。



Why is this happening? Figure 5: The pentagonal fence with enlarged configuration and the pentagonal fence with minimum E1 configuration and the four vertices of the quadrilateral where they are located are dyed exactly the same, and each edge is the same, which is the outward extension of these edges in E1 configuration, so it will not participate in four times of reverse dyeing coverage and become useless edges. This shows that it is not necessary to discuss the case that the four-color components are embedded in the enlarged configuration of the E-family configuration, only the E-family configuration with the smallest embedding needs to be discussed.



现在讨论，E-族构形向内扩展时，它们的周期循环是否受嵌入五边形的任何四色构件的影响？

Now, when the E- family configurations expand inward, are their periodic cycles affected by any four-color components embedded in pentagons?

文献1中在证明了引理3.1成立之后，指出：

After proving that lemma 3.1 holds, document 1 points out:

“注意，CK的中心顶点在CK0, CK ,中都有相同的颜色，因为它不受任何Kempe组件的颜色交换所影响。”

"Note that the center vertex of CK has the same color in CK0, CK4, because it is not affected by the color exchange of any Kempe component."

究其原因，是因为：在A-C（或者A-D）链一侧颠倒B-D（或者B-C）链的染色时，都没有涉及到它（中心顶点），在生成的B-C(或者B-D)链一侧颠倒A-C(或者A-D) 链的染色时，都不会涉及到它。

The reason for this is that it is not involved in the dyeing of the B-D (or B-C) chain when the A-C (or A-D) chain side is reversed, and it is not involved in the dyeing of the A-C (or A-D) chain when the generated B-C (or B-D) chain side is reversed.

这个结论表明，E-族构形在周期循环中，一定少不了十折对称几何结构的中心顶点的存在。

This conclusion shows that the existence of the central vertex of a 10-fold symmetric geometric structure is indispensable for E- family configurations in periodic cycles.

由此，可以讨论，文献1中给出的图4、5、7（这里只给出4与7）所示向内扩展的不同情形。实际上这三种构形中的G与H的含义是一样的-----任何一个四色构件嵌入中心五边形中。

From this, we can discuss the different situations of inward expansion shown in figs. 4, 5 and 7 (only 4 and 7 are given here) given in document 1. In fact, G and H in the three configurations have the same meaning-any four-color component is embedded in the central pentagon.



                                图6  （文献1中的图4）



                              图7（也是文献1中的图7）



不管嵌入的四色构件G或者H，是否破坏了原图的十折对称性、色图。

See if the embedded four-color component G or H breaks the 10-fold symmetry and color map of the original image.

没有破坏原图的十折对称性、色图，那么新的构形仍然发生周期循环，可以用z染色程序可约。

If the 10-fold symmetry and color diagram of the original image are not destroyed, then the new configuration still has a periodic cycle, which can be reduced by z-dyeing program.



第三类： CK图中的任意一条二色边延伸

    The third category: any dichromatic edge extension in CK graph

如图6所示：（  shown in fig. 2: ）

838357214272564364

图26                             

   这类构形是二色嵌入同一种色链中，相当于任意拉长CK图中除去C2-D2链（因为这条色链的拉长会使得原图简化为A1-C1、A1-D1相离简单情形）的任意一条色链，事实上也是嵌入四边形情形。由于没有破坏原来CK图的十折对称基本框架，可以使得算法2.1循环。所以也可以用Z染色程序可约。

This kind of configuration is that two colors are embedded in the same color chain, which is equivalent to any color chain except C2-D2 chain in an arbitrarily elongated CK graph (because the elongation of this color chain will simplify the original graph into the simple case where A1-C1 and A1-D1 are separated from each other), which is actually an embedded quadrilateral case. Because the basic framework of the original CK graph is not broken, the algorithm 2.1 can be circulated. Therefore, z staining procedure can also be used for reduction.

      
    图文并茂，可见后面附件。


参考文献 【1】       万春如，《一种试探式的平面图四染色》
                           
这篇文章的修改稿可以到《四色猜想中染色困局构形的4-染色》之主要参考文献（修改）中完整评读，特此告知。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，