数学实验-图的着色

《数学实验-图的着色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学实验大作业-图的着色1136005班摘要:图的着色问题是典型的优化问题,用Matlab求图的着色的色多项式问题,运用B-L约化算法求解。本文将从背景知识、数学模型和课后习题解答三方面来叙述。关键词：Matlab图的着色数学模型色多项式一、背景知识：图论〔GraphTheory〕是数学的一个分支。图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。1.欧拉——柯尼斯堡七桥问题图论起源于著名的柯尼斯堡七桥问题。在柯尼

2、斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个‘图’。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对於一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。2.四色猜想这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由

3、一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。3.图论应用在19世纪和20世纪的前半期，图论中主要研究一些游戏问题，诸如迷宫问题、博弈问题和棋盘上马的行走路线等等。1847年，克希荷夫应用图论的方法来分析电

4、网络，奠定了现代网络理论的基础，这就是电工原理中的克希荷夫电流定律和克希荷夫电压定律，这是第一次将图论应用于工程技术领域。1936年哥尼格发表了第一本图论专著，从此图论成为一门独立的学科。当应用图论来解决实际问题时，不管是电网络的分析、电路设计、数据的结构或社会科学方面的问题，几乎需要引出复杂的图形，这些图形，如果没有计算机的帮助实际上是不大可能分析的。近几十年来，图论盛行于世，高速数字计算机的出现是其原因之一。二、数学模型-B-L约化算法如图（b）所示，给出一种计算P(F,x)的方法，参阅图（b）、（d）、（f）.注意图（b）中标有e的边，对图的任意一种正常着色，V1与V2相邻，必须涂为

5、不同种颜色，若无边e，则V1与V2颜色可以相同，亦可以不同。所以对V1与V2及e而言，有如下等式：（d）的正常着色数=（b）的正常着色数+（b）的非正常着色数。而（b）关于V1与V2的非正常着色数=（f）的正常着色数。所以有如下等式：（b）的正常着色数=（d）的正常着色数-（f）的正常着色数。这里（f）是合并（d）中V1与V2而得到的，即假设（d）中V1与V2涂同一种颜色时，考察其涂色方式，其方法数为（b）中关于V1与V2的非正常着色数，而这一非正常着色数显然为(f)的正常着色数。注意合并（d）的顶点V1与V2形成（f）的过程，我们将新顶点（1=2）与(f)中顶点3，4之间用边相连，当且仅

6、当（d）中3，4与1或2之间有边相连。定义：用x种颜色对图F所有可能的正常着色数记为P(F,x),称P(F,x)为F的色多项式。则将B-L约化算法的文字叙述以公式形式给出，有如下形式：P(（b）,x)=P((d),x)-P((f),x)。用同样的方法可以分别对（d）,(f)进行去边分解，得到（d1）,(d2)与(f1),(f2)，则着色数P((d),x)与P((f),x)有完全类似的上式的形式，则这一过程可以继续下去，直到所有的图成为空图。三、课后习题解答问题1顶点数n=2,3,4,5,6的完全图其色数是多少？（不要用计算机，仔细思考并清楚地说明你的理由）答：对应顶点数n=2,3,4,5,

7、6的完全图的色数分别为2,3,4,5,6。原因是在完全图中，图中每个顶点都与其余所有顶点相连，任何相连的点颜色不同，故最少染色需要的颜色即为顶点数。问题2F为n个顶点的完全图，给出其色多项式P(F,x)。答：P(F,x)=x!(x≥n)。问题3用44种颜色对图6.9着色，可以有多少种方法？用程序完成。另外，该图的色数和色多项式是什么？答:P(F,x)=15*x^2-5*x-20*x^3+15*x^4-6*x^5+x^6。