数学建模社区-数学中国
标题:
解读heawood反例最好的文章
[打印本页]
作者:
张彧典
时间:
2012-8-20 09:48
标题:
解读heawood反例最好的文章
理应已知的赫伍德范例
( @3 O* x% m8 [5 v
; j \( ^9 v; ?8 q9 Y5 v9 w/ J8 t }
弗雷德·霍罗伊德和罗伯特·格兰丁·米勒
3 @7 [7 V G+ O) m6 L6 N/ e
7 D; V3 l, T8 d5 m
! l1 `9 s* U& t; O- S9 H5 S
(1990年10月23日收到)
4 }! |# W9 T7 ]0 D2 i, x
6 H J! T8 p! p
6 w; O9 e: O/ F: F
在任一平面图G中,用四色正确地对每一顶点x染色,使得G中任意相邻点V、W不同色.然后用Gw(V)[x(v),x(w)]表示肯普构形的容量__容纳G中极大连接[x(v),x(w)]的色链。
2 v2 X/ r) b# L2 D
, d$ |* q6 I- U! q! T
假定这时画好的G中,含有显示四色的5度不定平面x和另外所有3度平面,并对不定面顶点顺时针附加标记1—5,那么上述标记1和3具有相同色。
( y2 z( E* Z5 W
5 ?2 q: ]; K* }* y
肯普试图证明四色定理,论述如下:如果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)
' l4 Y& i. H2 [8 j, ^
, p8 m8 H/ E' s( D0 U. R
= G1(4)。(看图1,在肯普构形中G4(1)和G5(3)画粗线)。拥有这种染色特征的图称为赫伍德图形,这种染色叫作赫伍德染色。并分别按顺时针方向对G4(1),逆时针方向对G5(3)作赫伍德染色叫作顺时针.逆时针赫伍德颠倒。当对图1作逆时针赫伍德颠倒时,结果使图2中顶点逆时针倒转,表明不定面顶点的新染色数周期变化。这里G4(1)被表为黑体,G5(3)用阴影线表示。这个反例足以反驳肯普结论。但应注意,图2染色已不再是赫伍德染色。了解这一点,进而实行逆时针赫伍德颠倒,从而得到图3的染色。如果继而对黑体表示的Y—R构件实行肯普颠倒,事实上是沿不定面的染色系统去掉Y,只要开始时用顺时针赫伍德颠倒图1所示图,可得到同样结果。
9 m$ ~& r0 E8 w7 v4 k
( t/ f" w6 t7 E6 c
赫伍德反例因而处于开放的可能性。通过一个或一系列赫伍德颠倒,每个赫伍德染色可能转化到非赫伍德染色。于是提供了一个试图证明四色定理的想法,但是对图4所示图的染色排除了这种可能性。它比赫伍德例子序列更小,且具有十折对称性,构件G4(1)和G5(3)用黑体画出。应用赫伍德颠倒会使染色结果不变。为了验证这一点,只须运用逆时针赫伍德颠倒所遵循的程序,并经由这个赫伍德染色程序返回到原型染色。
2 t* j' X) l& p# k" {1 S& e2 L9 A0 F
% j! n$ y- m* y- G: `# w
我们对图4所示图运用四种连续的逆时针赫伍德颠倒,第一到最后的颠倒结果描述在独立的图5、6中,再次用黑体画出G4(1)和G5(3)。显而易见,这些染色的每一种情形确实都是赫伍德染色。同时能检验,从最后到第一的染色,通过图的对称旋转,结果随出。
2 ~8 g( u$ z4 K r: \* n% q! l6 |
1 R0 p0 `( V0 i+ {: S: S9 k; M
(有兴趣研读此文英文以及图示请搜索我的博客
zhangyd2007@sohu.com
)
. j, A: x) G' w5 A: D+ _
作者:
raymondno
时间:
2012-9-30 09:31
还是不太懂
作者:
raymondno
时间:
2012-9-30 09:56
还是不太懂
作者:
空木葬花
时间:
2014-3-14 21:06
非常感谢楼主的福利!
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5