与梁增勇朋友交换意见

zengyong

四色定理的双迹法证明

摘要：
关键词：色数；不可避免构形集；迹；双迹图；圈；

1  前言
（略）
2  双迹法
1）双迹法定义：在三角形结构连通平面图中把四种颜色的顶点分为两大双色集合 , 由a、b两色（或c、b两色）的顶点和它们之间的边所构成的子图称之为迹。这里，由a、b两色组成的迹称之为A-B迹，我们用符号jn1表示；符号jn2表示有n个顶点 的C-D迹（含c、d两色）。利用迹的优越性质对平面图进行正常4-着色的方法就叫做双迹法。
2）双迹图定义：由双迹和色顶点以及公共边组成的三角形结构连通平面图就叫做双迹图。由无奇圈的迹组成的双迹图也叫做标准双迹图。
3  双迹图性质:
3.1 双迹图的不可避免构形集
双迹图的不可避免构形集中的构形基本是路径、树、森林，它的特殊构形是单顶点和含偶圈的迹。


因为在不正确的着色过程中也可能出现奇圈，而造成迹不能正常2-着色。这是在标准双迹图中所不允许出现的，同时它也是可以消除避免的（见后面章节）。因此，我们不打算把奇圈作为双迹图的不可避免构形。
证 因为 双迹图是由两大色集的顶点组成。1）当一个色集的顶点只有一个顶点是迹的特殊情况。2）两个和多个顶点和它门之间的边构成的子图（如果没有分叉）是路径。3）多条路径的结合含有分叉的迹子图就是树结构。4）如果迹的顶点和边形成一个回路就是圈结构。含有圈结构的迹也是一特殊的构形。因为迹是一种线状结构，顶点的度不超过3，因此它仅能组成以上4种结构的形式。

3.2 标准双迹图迹的色数
定理1  标准双迹图的单迹色数为2。
证 因为标准双迹图的定义迹是不含奇圈的。1）单顶点的色数是1；2）当迹为路径，顶点的颜色以a-b-a-…形式相间排列，显然只用两种颜色；3）当迹为树的构形，不管有多少个分叉，后续的n级路径的顶点都可使用a、b两种颜色着色。因此，树结构的迹子图色数也是2。4）我们已经知道偶圈的色数是2，所以含偶圈的迹的子图的色数也还是2

zengyong

3.3 双迹图迹顶点颜色可调的灵活性

3.4 双迹图的正常着色标准

3.5  奇圈的消除
在平面连通图中,偶圈和奇圈 是可能同时存在的. 但在双迹图中, 在规划迹的分布过程中,不可避免的遇到奇圈的出现.为了能达到标准的双迹图. 就必须采取措施消除迹的奇圈。
实际操作见下图和图3 破圈的例子：
（注意：在后面的图例中，为了更简单明了的表现顶点颜色，我们使用黑、白、深灰和浅灰色对应代表a、b 、c和d四色。）

图3
图3显示了图G有一个A-B迹的奇圈出现，两个白色的顶点产生了颜色冲突。图G’将A-B迹的一个黑色顶点换成邻近C-D迹的浅灰色顶点，A-B迹的奇圈消失。在换顶点的过程中也可能会出现同颜色的迹的邻接问题，处理方法见3.3 。
(提示：注意:迹的奇圈和平面连通图的区别。)

zengyong

定理2  一个新顶点与一个标准双迹图Gk 的顶点邻接，总可以
完成一个新的标准双迹图Gk+1的正常4-着色。
证 一个新顶点与一个标准双迹图Gk 的顶点邻接，他将会遇到以下几种情况：
1）新顶点与旧迹的端点邻接。(可参见3.3)
2）新顶点与旧迹的中间顶点邻接。(可参见3.3)
3）新顶点与旧迹的偶圈顶点邻接。(可参见3.3)


图4
以上的迹的方向与顶点顺向。G和G’显示如何使用破圈法把新顶点V1用黑色后出现的A-B迹的奇圈（W3和W7）“破”去。即将本来是A-B迹的v2 顶点改为C-D迹的顶点。G’’和G’’’显示如何保持A-B迹的偶圈（W10）的另一种着色方案。
以下迹的方向与顶点横向（用一个雷明先生提供的原图说明）。

zengyong

定理3  任何一个复杂的三角形结构连通平面图G都可以变为双迹法结构的图
  证 即任何复杂的三角形结构连通平面
图都可以通过逐个添加顶点完成整个原图G的再现。
......
这样，就可以证明当n无穷大，即原图G无论怎样大，都可以实现标准双迹图Gn。

定理4  任何复杂的标准双迹图色数不大于4。
证  在前面我们已经证明，任何复杂的双迹图都是由A-B迹和C-D迹两大类子图构成，同时当出现迹含有奇圈，可以采取措施消除、避免奇圈的存在。在各个迹顶点之间也不会产生颜色冲突。换句话说，
整个标准双迹图的顶点颜色只有a、b、c和d四钟颜色，所以标准双迹图的色不会大于4。

4         四色定理的证明

定理5  任何三角形结构连通图色数≤4.
证 在定理3已经证明，任何一个复杂的三角形结构连通平面图G都可以变为双迹法结构的图G’ 实现正常4-着色,再 由定理4就可证
                             χ(G) =χ(G’) ≤4 。

定理6  任何连通平面图G可增加边导出三角形结构连通图G’ , 且
                               χ(G’) ≥χ(G)。
    证  很明显，
   命题（四色定理)  任何平面连通图的色数不大于4。
   证  任何连通平面图G可增加边导出三角形结构连通图G’ , 由定理5和定理6 可证明
                               χ(G)≤χ(G’)≤4 .
即任何平面连通图的色数不大于4。



5  双迹法的着色方法 （前面帖子已经谈的差不多, 通过了解双迹法的证明，
我们就能够理解双迹法的着色方法步骤。同时
通过了掌握双迹法的着色方法我们有能够更加体会双色法的证明可靠和双色法的着色的优越性）。
6  结论
（略）

雷明85639720

我会仔细看的。

雷明85639720

1、“2）双迹图定义：由双迹和色顶点以及公共边组成的三角形结构连通平面图就叫做双迹图。由无奇圈的迹组成的双迹图也叫做标准双迹图。”  难道还有含奇圈的双迹图吗?画一个看看。
2、“因为在不正确的着色过程中也可能出现奇圈，而造成迹不能正常2-着色。这是在标准双迹图中所不允许出现的，因此，我们不打算把奇圈作为双迹图的不可避免构形。”  多余的话。
3、“因为迹是一种线状结构，顶点的度不超过3，因此它仅能组成以上4种结构的形式。”  请问，你的图G和图G＇中，那个顶点的度不大于3呢？
4、"5）只有当含奇圈的迹的子图的色数会是3。因为奇圈的色数是3，大于2。但是标准的双迹图的定义迹是不含奇圈的。所以标准的双迹图的色数就不大于2。" 迹就是由两种颜色构成的，绝不会有色数是3的迹的。
5、"图3显示了图G有一个A-B迹的奇圈出现，两个白色的顶点产生了颜色冲突。图G’将A-B迹的一个黑色顶点换成邻近C-D迹的浅灰色顶点，A-B迹的奇圈消失。在换顶点的过程中也可能会出现同颜色的迹的邻接问题，处理方法见3.3 。(提示：注意:迹的奇圈和平面连通图的区别。)" 叫做颜色冲突就可以了，不要叫做奇圈迹。“图G’将A-B迹的一个黑色顶点换成邻近C-D迹的浅灰色顶点，A-B迹的奇圈消失。”   只是没有了所谓的奇圈，但仍有颜色冲突，两个白色顶点仍是相邻的。
6、“定理2  一个新顶点与一个标准双迹图Gk 的顶点邻接，总可以完成一个新的标准双迹图Gk+1的正常4-着色。
证 一个新顶点与一个标准双迹图Gk 的顶点邻接，他将会遇到以下几种情况：
1）新顶点与旧迹的端点邻接。(可参照3.3着色)
2）新顶点与旧迹的中间顶点邻接。(可参照3.3着色)
3）新顶点与旧迹的偶圈顶点邻接。”
这样的证明是否有点太简单了。连一个图也没有。
7、“以上的迹的方向与顶点顺向。”  这是什么意思？
8、“G和G’显示如何使用破圈法把新顶点V1用黑色后出现的A-B迹的奇圈（W3和W7）“破”去。”图4中没有W3和W7呀!
9、“即将本来是A-B迹的v2 顶点改为C-D迹的顶点。G’’和G’’’显示如何保持A-B迹的偶圈（W10）的另一种着色方案。”；图4中也没有W10呀i你的图中就
没有A,B,C,D字样出现，在这里谈什么A-B迹与C-D迹呢？
10、“以下迹的方向与顶点横向”又是什么意思呢？

雷明85639720

1、你的图画得有毛病。用黑，白，深灰和浅灰，文字再就不应再用A，B，C，D了。但你的图中的深灰和浅灰实在是分不开的，你可以看一看，不如直接就用字母代表颜色还要明了一些。
2、你的关键一步——图5，不把一步一步如何变化分开画图，而画了同一个图的不同画法，十在是没有意义。从你仅有的一个图G＇和G＇＇是看不出你是如何改动（破圈）的，也不可能看清你是如何最后得到G＇＇＇的。这样你的方法再好，看不明白，就等于对读者没有任何作用一样。
3、另外你的图5中的图G＇＇＇中，有两个D色顶点是相邻的，所以你对我这个图的着色是错误的。
4、“即任何复杂的三角形结构连通平面图都可以通过逐个添加顶点完成原图的再现。”这里的“原图”是指什么呢？三角形结构就是说所有面都是三角形面，为什么还要增加顶点呢，增加后的顶点都是只能与三个顶点相邻，有什么意义呢。
5、根据你的双迹法原理，我想是可以证明四色猜测是否正确的，但问题是你一定要把文章写得叫人们能看明白，这是最主要的。我认为你是关键的地方不去祥写，而把一些不是关键的地方写得那么祥细是没有用的。
6、你的想法是否能成立，关键盘在于你开始就认为任何平面图一定是双迹的，这个双迹，就是说任何平面图就是用四种颜色着色的。对于小于四种颜色的图，还可以认为有一种颜色的顶点都是独立顶点迹。但在还没有证明四色猜测是正确以前，你能保证任何平面图都一定是四色的吗。如果有第五种颜色出现，那不就是不能说任何平面图都不一定是双迹图吗。
7、这就是我以前的贴子上说你可能会出现循环论证的原因。现在看清楚了吧，你的出发点就是认为四色猜测是正确的，最后证明的结果仍是四色猜测是正确的。这等于没有证明。白下功夫。
8、你的“任何平面图都是一个双迹图”的命题，等同于四色猜测。所以你想证明四色猜测，就只要证明任何平面图都是双迹图就可以了。祝你成功。

zengyong

谢谢你的评议，我看后再详细回答和 修改。

雷明85639720

好的。我等你。

zengyong

答雷明朋友的评议：

1、“2）双迹图定义：由双迹和色顶点以及公共边组成的三角形结构连通平面图就叫做双迹图。由无奇圈的迹组成的双迹图也叫做标准双迹图。”  难道还有含奇圈的双迹图吗?画一个看看。“

答：我在图3中就介绍了如何解决由于规划j迹的分布不正确的过程中而出现的奇圈。（注意：是在过程中出现奇圈）见左图G,
有一个11顶点的A-B迹的奇圈，同时在打“×”处有两个白色的顶点邻接（颜色冲突）。经过消除奇圈的处理，把A-B迹奇圈上的一个顶点该为C-D迹的顶点，A-B迹奇圈就不再存在。见右图。另外，还可如G’’’处理。