- 1、本文档共31页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
毕业论文
(此文档为word格式,下载后您可任意编辑修改!)
1 前言
1.1课题背景
图论是数学中的一个重要的分支。它以图为研究的对象。图论原本是应用数学的一个重要的分支,为此,历史上曾有许多位数学家独自地建立过图论。早在1736年欧拉的著作中就出现了关于图论的文字记载,最初他所思考的图论问题都有很强的现实背景。著名的柯尼斯堡七桥问题就是图论的起源。欧拉证明了这个题目没有解,并且把这个题目进行推广,给出了对于一个给定的图可以以某种方法走遍的判定规则。这项研究所取得的成果奠定了欧拉图论〔及拓扑学〕创始人的地位。
染色问题是图论的一类重要的题目,具有重要的实际意义和理论意义。不同类型的图的染色问题一直是图论中的热点题目,而连通图的染色问题又是其中一种很重要的分支。染色问题就是给定一个图,把它所有顶点或所有的边染上颜色,使得相邻顶点或边的颜色都不相同时所需要的最少的不同的颜色数,边的染色题目可以转化为点染色题目,它们都能归于将一个图划分为独立子集的理论。目前,伴随着图的染色问题在实际问题中被广泛的应用,研究这类问题的学者在逐渐的增多。对不同图类的染色问题的研究,已经有了比较丰富的成果,并且这些结论还在不断的完善之中。
连通性是图论中最重要的性质之一,2008年,Chartrand,Johns等人首次提出了图的彩虹连通性的概念,是经典连通性概念的一种加强。作为一个自然的组合概念,彩虹连通数不但有其了理论意义,而且在网络问题中起到了非常重要的作用。事实上,它产生于政府机构之间机密信息的安全传输,在网络安全等实际问题中有很多的应用。假如我们需要在一个蜂窝网络中进行信息的传输。在网络中的任意两点在之间都要有一条路相连接,而且在该路径上的每段都被分配一个独特的频道(例如,不同的频率)。显而易见,我们需要求出的是能在网络中所使用的最少的(不同)频道个数。而这个最少个数恰好是这个网络所对应无向图的彩虹连通数。彩虹点连通的概念是由Krivelevich,Yuster首次提出的,是彩虹连通性的一种重要推广。它也有着很多实际的应用,也同样是研究的热点问题之一。
1.2问题来源
在教学工作中,我们常常能遇到类似这样的题目:一所学校有n种课程需要由学生来选修,学期结束后要对学生进行考试。显然,每个考生每场只能参加一门课程的考试。试问这次考试最少要进行几场? 显然,不可以在同一个时间进行同一个学生所选修的两门课程的考试。当然,不会出现同一个学生的不同课程在同一个时间所进行的考试。我们可以把这样的问题归结为:在一个平面上取个顶点分别来表示这门课程。如果有同学同时选择了课程和,则把点之间连一条边,可以得到一个有个顶点的无向图。这样的问题可以看做给图的每一个顶点染色,并要求相邻的两个顶点染不同的颜色,求最少要进行几场考试,就是最少能用多少种颜色使得图的相邻顶点都有不同颜色。这样的问题就是顶点染色问题。有关顶点染色问题的形式有很多种,它们在实际应用中也都有着不同的用处。
图的染色问题也是由地图的染色问题延申而来的:用种颜色给地图染色,让地图上的每一个区域都有一种一种颜色,并使得相邻的地区颜色不同。
问题处理:如果把每一个地区看作一个顶点,把相邻两个地区用一条边连接起来,就能够把一个区域图看作一个平面图。例如,图1(a)所示的区域图可看作为图1(b)所表示的平面图。19世纪50年代,英国学者提出了任何地图都可以用4种颜色来染色的问题并称之为4色猜想。100多年之后,才由美国学者在计算机证明了这个问题,这就是著名的四色定理。例如,在图1中,把不同的区域用城市的名字来表示,所染的颜色用不同的数字来表示,则在图中表示了不同的地区用不同的染色来染色的问题。跟图的边着色问题一样,生活中的很多问题,也可以给它们建立一个模型并看作为图的顶点染色问题来处理。例如课程安排问题,电视频道分配问题,变址寄存器问题等等。1852年,格里斯注意到可以用4种颜色来为美国地图进行染色,使得相邻地区(有一段公共边界,不只一个公共点)有不同的颜色,进一步指出了四色猜想。
图 1
1.3 研究该课题的意义
在日常生活中,还有许多问题可以用彩虹顶点染色加以解决,比如电视频道分配问题,变址寄存器等,可以运用彩虹染色方法轻松解决,图的染色理论是图论中的重要内容,也是图论的起源之一。几百年来,很多的数学家们都为此花费了大量的心血去研究。迄今为止,图论的许多公开问题一直是专家学者们的钻研的重点题目。在生产管理、军事、交通运输、计算机网络等许多的领域图论的知识在其中都有着重要的应用,彩虹连接数在网络领域也有很多的应用。假设G代表一个一个细胞网络,我们希望在管道的任意两个顶点之间能够传递消息,这要求每个链接上的顶点之间的路由都分配了一个不同的渠道(如不同的频率)。显然,我们希望使用不同渠道的数量降至最低,用彩虹染色的方法就
文档评论(0)