论文部分内容阅读
摘 要： 本文使用三角形结构平面图仅有延伸结构和轮形结构两大类不可避免构形集、颜色关系传递、图收缩和顺序着色法解决了四色定理的证明和应用。
关键词： 不可避免构形集 颜色冲突 图收缩 顺序着色法
《四色定理证明新方法》一文已经证明（简介如下）[1] ：
定义：当无环的内小面均为C 的平面连通图称之为三角形结构平面图。其中无轮形结构者称之为延伸结构，用E 表示。已知轮形结构用W 表示。
定理1：三角形结构平面图仅有延伸结构和轮形结构两大类不可避免构形集[2]。
证：可逐个增加三角形结构构造三角形结构平面图，结合欧拉公式使用数学归纳法：（1）当选择增加一个顶点和两条边时产生的是延伸结构，即 f = e 2-v-1 1；（2）当选择增加一个条边时产生一个轮形结构，即f = e 1-v 1（欧拉公式均成立）。此外，不可能有多于两个顶点或三边的情况（会产生割点）。
引理1：轮形结构子图色数≤4[3]。
定理2：延伸结构子图是有序图，其中，E 是传递颜色的因子。延伸结构子图色数=3。
证：因为在两个相邻的三角形结构内不在公共边的两个顶点必然同色，故称E 是传递颜色的因子。使用数学归纳法，假设第n个顶点，延伸结构子图En为有序3-色图；第n 1个顶点必在某E 之中，并与对应的顶点同颜色。即E 仍为有序图。显然，E 仍为3色图。
定理3：在3色图中，当延伸结构子图的两个相同颜色的顶点再有邻接边就发生颜色冲突，但它可以通过调整轮形结构的位置消除冲突。
证：在一个延伸结构子图中，任意两个相同颜色的顶点加一邻接边，则构成颜色冲突。当此边与原来的顶点和边组成K ， 可将中心顶点变成第四色。否则此边与原来的顶点和边组成一个大于K 的轮形结构，此时可以调整轮形结构的位置，消除颜色冲突（见下图）。
由定理4，可知，仅仅证明不可避免构形集和所有构形的可约还是不充分的，必须证明如何鉴别颜色冲突及如何消除颜色冲突才是充分的证明。下面便是本文利用顺序着色法解决这一难题。
顺序着色法定义： 对于一个k色图，根据顶点颜色关系、按照一定顺序能给顶点实现正常k着色，则称此顺序为正确的着色顺序，此方法称为顺序着色法。显然，利用顺序着色法进行着色，后面着色的顶点颜色是顺从于前面着色的顶点颜色关系的。换句话说，在分析前面着色的顶点颜色关系时，后面着色的顶点可以暂时不考虑它们的存在，即可以使用这一原则将复杂的图收缩为简单的图。那么顺序着色法的实际操作步骤就包括：1.图收缩：将复杂的图化为简单的图，进行分析关键顶点的颜色关系；2.确定正确的轮形结构位置；3.恢复被收缩的顶点和边，按照正确的着色顺序完成原图的正常4着色。
顺序着色法的依据和实际操作步骤为：.
1.由于K 的特点，不管外圈三个顶点是什么颜色，中心顶点都可以用第四色着色。因此在4色图中可以将K 看做K 处理，可将复杂的原图收缩为无K 的3色简单图。
2.在简单图中将所有轮形结构的中心顶点用白色着色，再将所有白色中心顶点（及边）删去， 同时删去剩下的自由顶点就能使用图收缩的方法得到一个限制色数为3色的仅含若干个延伸结构子图和它们之间的邻接边组成的简单图。
3.经过收缩得到的简单图中，根据延伸结构子图是有序3色图（E4是传递顶点颜色的最小因子），当遇到两个相同颜色的顶点之间再有邻接边而形成冲突链，而产生顶点颜色冲突。这样就可以判定颜色冲突的顶点位置，同时可以根据定理3重新调整轮形结构的位置消除冲突，那么便可以得到一个没有颜色冲突的正常4着色的4色图。
4.恢复所有轮形结构的中心顶点和边，恢复所有k 和自由顶点并着色，就能得到一个与原图同构的正常4着色的4色图。
上图便是一个顺序着色法例案。根据以上几点就可证明：
定理5：任何复杂的三角形结构平面图都可以使用以上顺序着色法步骤实现正常4着色。 即三角形结构平面图的色数不大于4。
定理6：由于平面连通图的色数不大于三角形结构平面图的色数[4]， 因此任何平面连通图的色数不大于4。
至此， 四色定理的终结证明大功告成.。
结论：1.4色平面图的顶点颜色关系是以具有正确轮形位置的无K 简单图为基础的，而嵌套的K构成更复杂的平面图，但平面图的色数仍等于4。
2.由于本证明是针对任何复杂三角形结构平面图为目的，延伸结构可以是任意复杂的图，因此该证明不是个例，而是具有普遍代表性的。
3.讨论顶点的正常着色仅证明不可避免构形集和所有构形的可约还是不充分的。必须同时证明由构形组合的各种子图还可能产生顶点颜色冲突，以及如何消除才是充分的四色定理证明。
4.本证明展现了一个不依赖计算机的四色定理证明及应用新方法。
参考文獻：
[1] 梁增勇.四色定理证明新方法[DB/CD]. 百度文库，2013，http：/wenku.com/user/....
[2] R.Balakrishnan ， K.Ranganathan，， A Textbook of Graph Theory[M].北京：科学出版社，2011：187-188.
[3] 王树禾.图论[M] .科学出版社，北京：2004：90.
[4] 屈婉玲，耿素云，张立昂.离散数学[M].北京：高等教育出版社，2008：324-325.
关键词： 不可避免构形集 颜色冲突 图收缩 顺序着色法
《四色定理证明新方法》一文已经证明（简介如下）[1] ：
定义：当无环的内小面均为C 的平面连通图称之为三角形结构平面图。其中无轮形结构者称之为延伸结构，用E 表示。已知轮形结构用W 表示。
定理1：三角形结构平面图仅有延伸结构和轮形结构两大类不可避免构形集[2]。
证：可逐个增加三角形结构构造三角形结构平面图，结合欧拉公式使用数学归纳法：（1）当选择增加一个顶点和两条边时产生的是延伸结构，即 f = e 2-v-1 1；（2）当选择增加一个条边时产生一个轮形结构，即f = e 1-v 1（欧拉公式均成立）。此外，不可能有多于两个顶点或三边的情况（会产生割点）。
引理1：轮形结构子图色数≤4[3]。
定理2：延伸结构子图是有序图，其中，E 是传递颜色的因子。延伸结构子图色数=3。
证：因为在两个相邻的三角形结构内不在公共边的两个顶点必然同色，故称E 是传递颜色的因子。使用数学归纳法，假设第n个顶点，延伸结构子图En为有序3-色图；第n 1个顶点必在某E 之中，并与对应的顶点同颜色。即E 仍为有序图。显然，E 仍为3色图。
定理3：在3色图中，当延伸结构子图的两个相同颜色的顶点再有邻接边就发生颜色冲突，但它可以通过调整轮形结构的位置消除冲突。
证：在一个延伸结构子图中，任意两个相同颜色的顶点加一邻接边，则构成颜色冲突。当此边与原来的顶点和边组成K ， 可将中心顶点变成第四色。否则此边与原来的顶点和边组成一个大于K 的轮形结构，此时可以调整轮形结构的位置，消除颜色冲突（见下图）。
由定理4，可知，仅仅证明不可避免构形集和所有构形的可约还是不充分的，必须证明如何鉴别颜色冲突及如何消除颜色冲突才是充分的证明。下面便是本文利用顺序着色法解决这一难题。
顺序着色法定义： 对于一个k色图，根据顶点颜色关系、按照一定顺序能给顶点实现正常k着色，则称此顺序为正确的着色顺序，此方法称为顺序着色法。显然，利用顺序着色法进行着色，后面着色的顶点颜色是顺从于前面着色的顶点颜色关系的。换句话说，在分析前面着色的顶点颜色关系时，后面着色的顶点可以暂时不考虑它们的存在，即可以使用这一原则将复杂的图收缩为简单的图。那么顺序着色法的实际操作步骤就包括：1.图收缩：将复杂的图化为简单的图，进行分析关键顶点的颜色关系；2.确定正确的轮形结构位置；3.恢复被收缩的顶点和边，按照正确的着色顺序完成原图的正常4着色。
顺序着色法的依据和实际操作步骤为：.
1.由于K 的特点，不管外圈三个顶点是什么颜色，中心顶点都可以用第四色着色。因此在4色图中可以将K 看做K 处理，可将复杂的原图收缩为无K 的3色简单图。
2.在简单图中将所有轮形结构的中心顶点用白色着色，再将所有白色中心顶点（及边）删去， 同时删去剩下的自由顶点就能使用图收缩的方法得到一个限制色数为3色的仅含若干个延伸结构子图和它们之间的邻接边组成的简单图。
3.经过收缩得到的简单图中，根据延伸结构子图是有序3色图（E4是传递顶点颜色的最小因子），当遇到两个相同颜色的顶点之间再有邻接边而形成冲突链，而产生顶点颜色冲突。这样就可以判定颜色冲突的顶点位置，同时可以根据定理3重新调整轮形结构的位置消除冲突，那么便可以得到一个没有颜色冲突的正常4着色的4色图。
4.恢复所有轮形结构的中心顶点和边，恢复所有k 和自由顶点并着色，就能得到一个与原图同构的正常4着色的4色图。
上图便是一个顺序着色法例案。根据以上几点就可证明：
定理5：任何复杂的三角形结构平面图都可以使用以上顺序着色法步骤实现正常4着色。 即三角形结构平面图的色数不大于4。
定理6：由于平面连通图的色数不大于三角形结构平面图的色数[4]， 因此任何平面连通图的色数不大于4。
至此， 四色定理的终结证明大功告成.。
结论：1.4色平面图的顶点颜色关系是以具有正确轮形位置的无K 简单图为基础的，而嵌套的K构成更复杂的平面图，但平面图的色数仍等于4。
2.由于本证明是针对任何复杂三角形结构平面图为目的，延伸结构可以是任意复杂的图，因此该证明不是个例，而是具有普遍代表性的。
3.讨论顶点的正常着色仅证明不可避免构形集和所有构形的可约还是不充分的。必须同时证明由构形组合的各种子图还可能产生顶点颜色冲突，以及如何消除才是充分的四色定理证明。
4.本证明展现了一个不依赖计算机的四色定理证明及应用新方法。
参考文獻：
[1] 梁增勇.四色定理证明新方法[DB/CD]. 百度文库，2013，http：/wenku.com/user/....
[2] R.Balakrishnan ， K.Ranganathan，， A Textbook of Graph Theory[M].北京：科学出版社，2011：187-188.
[3] 王树禾.图论[M] .科学出版社，北京：2004：90.
[4] 屈婉玲，耿素云，张立昂.离散数学[M].北京：高等教育出版社，2008：324-325.