地图着色问题算法分析
摘要………………………………………………………1
第一部分 地图着色问题和四色定理…………………2
第二部分 算法介绍……………………………………3
第三部分 地图的着色…………………………………6
1 预备知识……………………………………………6
2自由补全图的三着色………………………………7
3三着色的脉及其性质………………………………8
4 脉组存在性定理…………………………………10
第四部分 着色实例……………………………………11
第五部分 总结…………………………………………15
第优部分 小组成员分工情况…………………………17
参考文献…………………………………………………17
附录………………………………………………………18
地图着色界面…………………………………………18
参考代码………………………………………………18
参考代码结果…………………………………………23
摘 要
本文对地图的着色问题进行了研究，地图的着色问题是一个N P 难题，它源自著名的四色问题。着色问题主要研究如何将图的点或者边用给定数目的颜色涂染， 使得相邻两点或者两边着色不同. 本文通过考察三剖分边着色的性质，提出了脉组的思想，并证明了覆盖平滑三剖分所有区的脉组的存在性。根据以上的分析，我们给出了两个算法:一个是平滑三剖分边的三着色的D N A算法。任何一个地图的着色问题都可以转化成三剖分从而平滑三剖分的顶点着色问题，因此对于任何一个地图，我们都可以对它进行着色。最后我们给出了一个计算机程序对算法进行了 模拟。理想的，分别用十几步生化操作就可以找出一个平滑三剖分图的三着色和四着色，而所需的D N A分子链并不是很多，因此可以解决很大级别的图着色问题，从而验证了D N A计算在并行计算上的优越性。本文的编码方式十分简单、直观，编码具有规律性，易于实现。在读取操作中，我们将一条脉组上的着色信息转化为芯片上的荧光颜色，从而可以读取着色的信息。本文的算法和四色问题联系十分密切，因为构型的自由补全图是一类平滑三剖分，因此可以用我们的算法来讲行着色。
关键词: 地图着色问题; 四色问题; D N A计算; D N A芯片
地图着色问题
一、地图着色问题和四色定理
地图三着色、四着色问题是和四色定理紧密相关的问题。 本文中所指三着色是指对边的着色， 四着色是对点的着色。 地图四色定理是一个几乎每个人都可以理解的数学难题。 它的提法也是具有迷惑性的简单: 任何一个无环的平面图的顶点可以四着色。地图四色定理最先是由一位叫古德里 ( F r a n c i s G u t h r i e )的英国大学生提出来的。德• 摩尔根 切， D e Mo r g a n , 1 8 0 6 1 8 7 1 ) 1 8 5 2年1 0月2 3日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。 他在信中简述了自己证明四色定理的设想与感受。 一个多世纪以来， 数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。1 9 7 6年美国数学家K . A p p e l 与W . H a k e n 宣告借助电子计算机获得了四色定理的证明。 < . 7 5 ] ， 又为用计算机证明数学定理开拓了 前景。 他们用了三台I B M 计算机经过1 0 0 0 多个小时( 约5 2 天) 的运算， 证明了G u t h r i e 提出的结论是正确的。 由于证明的完成借助了计算机以及其证明的过程庞大， 使得很多人对此解决方法存在怀疑。 事实上，
A p p e l 和H a k e n 的论文有1 0 0 多页， 而其计算机程序达到4 0 0 多页， 对这个证明的验证几乎是很难的。1 9 9 6 年， N e i l R o b e r t s o n 等人在此基础上提出了一个更为简洁的计算机解决方案( a s . 3 7 1 ，使得四色问题的解决过程变得更为清晰。N e i l R o b e r t s o n等人的证明过程是从研究三着色出发，这是因为研究任何一个无环可平面地图的点的四着色是否存在的问题， 可以转化成研究地图三剖分中构形自由补全图边的三着色的问题，从而使得研究更加方便。
因此，寻找自由补全图全部三着色问题是四色问题解决中的一个重要问题。如果能有有效的三着色算法，这可以成为四色问题的D N A 算法的突破口。而三着色和四着色问 题是相互等价的， 对于任一张地图， 若能得到一个三着色的方案，那么可以把三着色转化成四着色。476
[1] [2] [3] [4] [5] [6] [7] 下一页