与梁增勇朋友交换意见

雷明85639720

好的，好的。

zengyong

雷明朋友：
      我写了证明论文大纲如下，请你给我提点意见，参考参考。如何？



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

    图3
    因为在不正确的着色过程中也可能出现奇圈，而造成迹不能正常2-着色。这是在标准双迹图中所不允许出现的，因此，我们不打算把奇圈作为双迹     图 的不可避免构形。

    证

2）双迹图迹的色数：
    定理1  双迹图的单迹色数为2。
    证
3）双迹图迹顶点颜色可调的灵活性
4）双迹图的正常着色标准：
     a)迹
     b)顶点颜色
3  四色定理的证明
    定理2  任何一个复杂的三角形结构连通图都可以变为双迹法结构的图
    证
    定理3  任何三角形结构连通图色数≤4
    证  由任何双迹图色数≤4  →  三角形结构连通图色数≤4 。

   四色定理  任一平面连通图的色数不大于4。

   注：有以上的双迹图基本性质证明，再证明四色定理已经不是难事，基本思路是：任何连通平面图G可增加边导出三角形结构连通图G’ , G’色数不大于  平面图G色数. 。所以由任何双迹图色数≤4  →  三角形结构连通图色数≤4 → 任何平面图G色数 ≤4。
（ 具体陈述文字导师再组织。）

5、双迹法的着色方法 （已经谈的差不多）
5.1 双迹法的着色步骤：
   1）根据标准双迹图的要求规划双迹的布局。
   2）落实每条迹上顶点的颜色。

图3最右的子图是奇圈，J10.（临时加上的。）

雷明85639720

1、你这里讲的有一个图3，但没有看到图。
2、你说：“ 因为在不正确的着色过程中也可能出现奇圈，而造成迹不能正常2-着色。这是在标准双迹图中所不允许出现的，因此，我们不打算把奇圈作为双迹     图 的不可避免构形。”这里说的“不可避免构形”的定义是什么，一定要说清楚。另外，“不打算把奇圈作为”中的“奇圈”是指什么“奇圈”呢，奇2色迹的色圈在双迹图中是不可能存在的，但“奇圈”在图中可是不可避免的呀。
3、“由任何双迹图色数≤4  →  三角形结构连通图色数≤4 → 任何平面图G色数 ≤4。”这是不是有点循环论证了。

zengyong

1、忘了，补上。

2、就按你的，有奇圈，再谈如何处理（避免它在标准双迹图中出现）；

3、仔细看我的目录，

基本思路是：任何连通平面图G可增加边导出三角形结构连通图G’ , G’色数不大于  平面图G色数. 。所以先1）由定理1 证明 任何双迹图色数≤4
2) 再由 三角形结构连通图都可变成标准双迹图，那么它的色数也≤4
3） 再由 三角形结构连通图的色数≤4 推出→ 任何平面图G色数 ≤4。（因为任何连通平面图G可增加边导出三角形结构连通图G’ , G’色数不大于  平面图G色数.）
       逻辑上是没有问题的。

雷明85639720

图中有奇圈，但双迹中不应有奇圈。
那就看你的证明吧，反正我感到有点循环论证。你先试式看。

zengyong

“图中有奇圈，但双迹中不应有奇圈。”

对，使用破圈法啊。

雷明85639720

1、你知道什么是不可免构形吗，什么是构形吗？
2、你画的图能叫不可免构形吗？
3、如果双迹图中有了奇迹圈，就说明就着色是错的，用什么破圈嘛，重着，使图中没有奇圈就行了。

zengyong

别急嘛，看再说。

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 。
(提示：注意:迹的奇圈和平面连通图的区别。)