图论期末论文VIP

1、浅谈图论四色问题及其应用摘要：在地图上，相邻的国家涂不同的颜色，最少需要多少种颜色？100多年前有人提出了“四色猜想”，即只要用四种颜色就能做到。本文通过对图论中图的基本概念以及四色问题的简单证明，通过分析实际问题，利用C程序进行编译，来解决实例地图的染色问题。关键词：图论；四色问题；染色；C程序0 引 言我们必须承认，有很多优美的数学问题都是来自于最日常的生活，比如在一张世界地图上，最少需要用几种颜色去给每个国家着色，才能使得任何两个相邻的国家的颜色不同？在学习图论这门课之前，我从来没有思考过这个问题，更不知道它是一个非常著名的数学难题。所以我想，也许有的人能成为伟大的数学家不仅依靠天分，更

2、重要的是善于观察和思考生活中蕴涵数学思想的细节，这恰恰是我们这样的学生所缺少的。1 图论的起源1736年是图论的历史元年。这一年，图论之父欧拉解决了哥斯尼堡城的七桥问题，发表了图论的首篇论文。美丽的哥尼斯堡始建于1308年，是东普鲁氏王朝的都市，城内的一条河的两条支流绕过一个岛，有七座桥横跨这两支流。脚下的七座桥触发了人们的灵感，人们有一项消遣活动，就是试图将河上的每座桥恰好走过一遍并回到原出发点，然而吸引了人们无数次的尝试却没人成功。问题看起来不复杂，但谁也解决不了，说不出其所以然来。直到1736年，欧拉解决了这一问题。他将这个问题转化为图论问题，即把每一块陆地用一个点来代替，将每一座桥用连

3、接相应两个点的一条线来代替，从而得到一个点线图。欧拉只用了一步就证明了哥尼斯堡的七桥问题没有解，并且推广了这个问题，给出了任意一种河桥图能否全部不重复、不遗漏地走一次的判定法则：如果通过奇数座桥连接的地方不止两个，满足要求的路线不存在；如果只有两个地方通过奇数座桥连接，则可从其中任一地方出发找到所要求的路线；如果没有一个地方通过奇数座桥连接，则从任一地出发，所求路线都能实现。他还说明怎样快速找到所要的路线，并为此设计了一个15座桥的问题。欧拉的论文在圣彼得堡科学院作了报告，成为图论历史上第一篇重要文献。这项工作使欧拉成为图论（及拓扑学）的创始人。1750年，欧拉和他的一个朋友哥德巴赫(C. G

4、oldbach)通信时说发现了多面体的一个公式：设多面体的顶点数为Nv，棱数为Ne，面数为Nf，则有Nv-Ne+Nf= 2。这类问题成为19世纪后半叶拓扑学研究的主要问题。欧拉多面体公式表述了几何图形的一个基本组合性质，其目的是利用这一关系将多面体进行分类。图论的发展从19世纪中叶开始，图论进入第二个发展阶段。这一时期图论问题大量出现，诸如关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密顿问题等。进入20世纪，图论仍然得以继续快速发展，科学家们通过计算机技术对四色猜想进行了证明等。2 图论基本概念2. 1图的定义有序二元组G = < V(G)，E(G) >称为一个图，其中：

5、（1）V(G) = v1，v2，vn是有穷非空集，称为顶点集，其元素叫做图的顶点； （2）E(G) = e1，e2，en称为边集，其元素叫做图的边。2. 2图的分类在图G中，与V中的有序偶（vi，vj）对应的边e称为图的有向边（或弧），而与V中顶点的无序偶对应的边e称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为G =（V，E）；每一条边都是有向边的图叫做有向图，记为D =（V，E）；既有无向边又有有向边的图叫做混合图。2. 3权如果图G中任意一条边（vi，vj）上都附有一个数Wij，则称这样的图G为赋权图，Wij称为边（vi，vj）上的权（weight）。2. 4 平面图和欧拉公式

6、定义 2.4.1：设一个无向图 G(V, E) (V 中的元素称为顶点，E 中的元素称为边)，如果能把它画在平面上，且除了V 中的顶点外，任意两条边均不相交，则称该图为平面图。如果一个图和一个平面图同构，就称它为可平面图。一个平面图将平面分成若干个部分，每个部分称为一个区域（又称面） ；一个平面图所划分的区域中，总有一个区域是无界的，称其为外部区域，其他的称为内部区域。定义 2.4.2：任何两个顶点之间总可以通过若干条边相连，这样的图称为连通图。定理 2.4.3（Euler 公式） ：设 G 是一个连通平面图，具有 n 个顶点， m 条边及l 个区域，那么有 n-m+l = 2 。推论 2.4

7、.4：具有 n3个顶点的平面图至多有3n-6 条边。推论 2.4.5：每个平面图必含有一个度小于或等于 5 的顶点。定义 2.4.6： 设有平面图G(V, E) ， 满足下列条件的图G'(V ', E') 称为图G 的对偶图：G 的任一区域 Ri 内有且仅有一点vi'；对G 的区域 Ri 和 Rj 的共同边界ek ，画一条边ek' = (vi', vj')且只与ek 交于一点；若ek 完全处于 Ri中，则vi'有一自环ek'。我们容易知道一个平面图的对偶图还是平面图。下图G'是G 的对偶图：3 着色问题定义3.1（

8、顶点着色）：给图 G 的每个顶点指定一种颜色，使得任何两个相邻的顶点颜色均不同。如果用 k 中颜色对图G 进行顶点着色，就称对图G 进行了 k 着色，也称G 是 k -可着色的，若G 是 k -可着色的，但不是 (k-1) -可着色的，则称G是 k 色图，称这样的 k 为图G 的色数，记为c(G)。定义3.2（边着色）：给图G 的每条边指定一种颜色，使得任何两条相邻的边颜色均不同。如果用 k 中颜色对图G 进行边着色，就称对图G 进行了 k 边着色，也称G 是 k -边可着色的，若G 是 k -边可着色的，但不是(k-1) -边可着色的，则称G是 k 边色图，称这样的 k 为图G 的边色数，记

9、为c'(G) 。定义3.3（平面图的面着色）：对平面图G 来说，它将平面分为 r 个区域，现对每个区域染色，使得有公共边的区域颜色均不同，这种染色称为平面图的面着色，如果能用 k 种颜色给平面图 G 进行面着色，则称 G 是 k -面可着色的，进行面着色时，所用的最少颜色数称为平面图的面色数，记为c*(G)。4 四色定理的证明四色定理：每个可平面图是 4-可着色的。证明：设有一个连通图，有 n 个顶点，如果这个图每个顶点都与除了自身以外的其他顶点相邻，则边的总数达到最大值。由于每个顶点的度是 n-1，所以包括重复计算的边总共有 n(n-1) 条边。因为每条边连着两个顶点，所以每条边都被

10、重复计算两次，所以实际上边的总数是 E = n(n-1) 2。由于图中任意两个顶点都相邻，如果相邻的顶点用不同的颜色，则图中 n 个顶点都必须要用不同的颜色去着色，所以总共需要 n 中颜色。如果任意去掉一条边，那么原来这条边所连接的两个顶点可以同色，所以去掉一条边可以少用一种颜色。此时如果再去掉一条边，就不一定会又减少一种颜色了，比如第一次去掉的边是e1,2 ，第二次去掉的边是e1,3，虽然 1 和 2,1 和 3 可以分别着相同颜色，但是由于 2 和 3 相连，所以这 3个点还是需要 2 种颜色。为了保证能再减少一种颜色，第二次至少要去掉 2 条边。同理为了保证再去掉一种颜色，下一次至少需要

11、去掉三条边。由此，如果希望用m 种颜色给图着色 ，至少要减少n - m 种颜色 ， 则应该去掉的边数为1+2+ (n-m) = (n-m)(n-m+1) 2；留下的边数为(m-1)(n-m2) 。所以可以得到的结论是：用m 种颜色给顶点数 n，边数不超过(m- 1)(n-m2)的连通图顶点着色，不管边怎么分布， 都能保证相邻的顶点颜色不同。 当 m = 4 时，对边数不超过3n-6 的图的顶点着色可以保证相邻顶点颜色不同。对于平面连通图，根据推论 2.4.4 可知当 n3时，边数一定不超过3n-6 ，所以用4 种颜色去给平面连通图着色，一定可以保证相邻的顶点颜色不同。5 实际着色问题5.1 问

12、题描述如下图所示，对图中8块区域进行染色。要求相邻的区域不能染相同的颜色。根据四色定理。所以可以用四种颜色进行染色。718536421可以利用C语言程序来解决这个问题。其对应的邻接矩阵即为：0,1,0,0,0,1,0,0,/地图的邻接矩阵1,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,5.2 程序流程求出对地图所对应的邻接矩阵 进行染色是否判断当前染色顶点与相邻区域颜色是否相同重新寻找有效颜色进行染色染色下一个区域直到所

13、有区域染色完毕，显示染色结果5.3 算法分析：回溯法：本例可采用回溯法进行着色。当area =1时，对当前第area个q区域开始着色：若area>n，则已求得一个解，输出着色方案即可。否则，依次对区域area着色，若area与所有其它相邻顶点无颜色冲突，则继续为下一区域着色；否则，回溯，测试上一颜色。回溯法的主要就是选择各种颜色，直到把此区域着完色为止。5.4 编译结果编译运行结果如下：所以染色情况如下:6 总 结 本文通过对图论中图的基本概念，图的染色问题的简单介绍，对四色定理进行了简单的证明和通过对实际的例子来利用C程序（回溯算法）来实现对问题的解决。四色问题的算法可以解决现实生活中

14、很多问题。本学期通过对图论的学习，让我对图论的基本概念和基本算法有了深入理解，图论的应用具有很好的使用价值。参考文献1 张清华. 图论及其应用M. 北京:清华大学出版社，2012.2 严蔚敏. 数据结构M. 北京:清华大学出版社, 1999.3 谭浩强. C+面向对象程序设计M. 北京:清华大学出版社，2005.4 陶然. 四着色新算法及其应用C. 燕山大学，2010.附录（源代码）：# include<stdio.h># include<stdlib.h># define N 8 / N表示区int sN; /栈si来表示地图的区域的颜色序号void MapColor

15、(int distNN,int sN)int color,area,k,i; /color代表颜色，area 表示当前要染色的是第几个区域，k表示已经染色区域的颜色s0=1; /第一个区域先着色为颜色1area=1;/ 从第二区域开始试探染色color=1;/ 从第一种颜色开始试探while(area<N)/ 是否全部染色完毕while(color<=4)k=0;/ 对每一个区域，都从第一个区域的颜色开始比较。 while(k<area)&&(sk*distareak!=color)/ 判断是否重色/ distareak表示当前即将染色区域和已经染色的第K个区

16、域是否相邻。k+;if(k<area)color+; /area 区域与K区域重色elsesarea=color; /保存area区域的颜色area+; /准备颜色下一个区域if(area>=N)break;color=1; /每次都从第一个颜色开始试探if(color>4)/ area没有找到合适的颜色，需要进行回溯area=area-1; / 回溯并修改area-1域并用颜色 color=sarea+1; /将预备要染色的颜色换为当前栈顶区域的下一个颜 色printf("地图区域标号为1-8的染色情况为：n");for(i=0;i<N;i+)printf("NO.%d:",i+1);switch(si)case 0:printf("WRONG MAP!n");break;case 1:printf("REDn");break;case 2:printf("BLUEn");break;case 3:printf("GREENn");break;case 4:print