解读heawood反例最好的文章

张彧典

理应已知的赫伍德范例
2 \% b" e' ^: u3 Q/ A
+ _, F* O$ p  g" o9 X3 |( l( T弗雷德·霍罗伊德和罗伯特·格兰丁·米勒


(1990年10月23日收到)
* {0 t9 |/ |+ a
6 `0 n7 I( |3 `* y! ~
在任一平面图G中,用四色正确地对每一顶点x染色,使得G中任意相邻点V、W不同色.然后用Gw（V）[x(v),x(w)]表示肯普构形的容量__容纳G中极大连接[x(v),x(w)]的色链。

: ]& [+ B6 ]( ~& @8 H; |. A5 E; d   假定这时画好的G中，含有显示四色的5度不定平面x和另外所有3度平面，并对不定面顶点顺时针附加标记1—5，那么上述标记1和3具有相同色。
. j) _. s' y& x' @3 C+ Z' E
$ G8 R/ P9 _3 P" }# z   肯普试图证明四色定理，论述如下：如果G4（2）≠G2（4）（或G5（3）≠G3（5）），那么交换G4（2）（或G5（3）），使得染色数减少为3，结论成立。如果G4（1）≠G1（4），G5（3）≠G3（5），那么同时交换G1（4）和G5（3），使得染色数再次减少到3。赫伍德对这一本质结论作出反驳。他在显示图中实行颠倒染色G4（1），产生G3（5）= G5（3），或者实行颠倒染色G5（3），产生G4（1）
3 H" ~8 u) u/ K5 X+ Q2 E6 I2 _* r3 N1 O
9 J- t9 U& c, ~4 u/ c: A$ J& |) V= G1（4）。（看图1，在肯普构形中G4（1）和G5（3）画粗线）。拥有这种染色特征的图称为赫伍德图形，这种染色叫作赫伍德染色。并分别按顺时针方向对G4（1），逆时针方向对G5（3）作赫伍德染色叫作顺时针.逆时针赫伍德颠倒。当对图1作逆时针赫伍德颠倒时，结果使图2中顶点逆时针倒转，表明不定面顶点的新染色数周期变化。这里G4（1）被表为黑体，G5（3）用阴影线表示。这个反例足以反驳肯普结论。但应注意，图2染色已不再是赫伍德染色。了解这一点,进而实行逆时针赫伍德颠倒，从而得到图3的染色。如果继而对黑体表示的Y—R构件实行肯普颠倒，事实上是沿不定面的染色系统去掉Y,只要开始时用顺时针赫伍德颠倒图1所示图，可得到同样结果。
% F' Q' Z1 y4 G9 C$ U1 {8 l1 h2 ?4 k
    赫伍德反例因而处于开放的可能性。通过一个或一系列赫伍德颠倒，每个赫伍德染色可能转化到非赫伍德染色。于是提供了一个试图证明四色定理的想法，但是对图4所示图的染色排除了这种可能性。它比赫伍德例子序列更小，且具有十折对称性，构件G4（1）和G5（3）用黑体画出。应用赫伍德颠倒会使染色结果不变。为了验证这一点，只须运用逆时针赫伍德颠倒所遵循的程序，并经由这个赫伍德染色程序返回到原型染色。

我们对图4所示图运用四种连续的逆时针赫伍德颠倒，第一到最后的颠倒结果描述在独立的图5、6中，再次用黑体画出G4（1）和G5（3）。显而易见，这些染色的每一种情形确实都是赫伍德染色。同时能检验，从最后到第一的染色，通过图的对称旋转，结果随出。
6 x0 f2 {7 `" Z$ ^
（有兴趣研读此文英文以及图示请搜索我的博客zhangyd2007@sohu.com）
9 [2 N4 k; H1 z; j, I1 ?; y

raymondno

还是不太懂

raymondno

还是不太懂

空木葬花

非常感谢楼主的福利!