特殊图类的彩虹边染色毕业论文1.doc
《特殊图类的彩虹边染色毕业论文1.doc》由会员分享,可在线阅读,更多相关《特殊图类的彩虹边染色毕业论文1.doc(30页珍藏版)》请在三一办公上搜索。
1、毕业论文特殊图类的彩虹边染色1 前言我们都知道,图论是源于一个著名的问题哥尼斯堡七桥问题。后来英国的数学家汉密尔顿通过十二面体“绕行世界”的游戏,使得很多人开始关注这个图论中的另一个著名问题,即汉密尔顿问题。谈到了图论中的著名问题,那就不得不提世界近代三大数学难题,同时对图论发展产生了重大影响的“四色猜想”,这使得图论中的染色问题成为了研究的热点问题,图的染色问题不但在理论上有着重要的意义而且在实际问题中也有着重要的应用。说到实际应用,对于图论的许多公开问题,比如说,企业生产管理,交通运输,计算机网络,甚至军事等众多领域一直以来都有许多专家学者所研究。而说到图的染色的实际应用,我们得介绍下何谓
2、染色。所谓的染色问题,就是给定一个图,需要把图中的所有的顶点,或者所有的边进行染色,使得相邻的顶点或者边所染的颜色不同,其中优秀的染色方法,就是尽量使得需要的颜色数最少。同样,图的染色在许多领域都会涉及到将某种对象的集合按照一定的规则进行分类,比如说,学生选课系统、电路布局、排序问题、会议安排、电路安排、考试安排等,这些问题都与图的染色理论密切相关,专家学者对图的不同染色问题的研究,已经有了较为丰富的结果,并且这些结果仍在进一步完善中。2008年,Chartrand, Johns, McKeon和Zhang首次提出了图的彩虹连通性的概念,这是对经典连通性概念的一种加强。我们都知道,彩虹连通数是
3、一个自然的组合概念,除了具有理论上的意义,更重要的是在网络问题中有着很重要的应用。事实上,政府机构之间需要进行一些机密信息的传递,这些传输要保证其安全性,于是便产生了彩虹连通的这些概念。假设信息的传输是在一个蜂窝形状的网络中,而这个网络中的任意两个顶点之间都有一条路相连,并且这条路径上的每一段路需要分配一个独特的频道(比如说,分配不同波段的频率)。显然,我们想要网络中所使用的不同的频道的个数最少,而这个最少的个数就是这个蜂窝网络所对应的无向图的彩虹连通数。在了解图的彩虹连通数之前,我们先对用到的一些图论基础知识做一个简单的介绍。首先,需要了解图的定义,图定义为一个二元组使得,记作。其中,代表图
4、的顶点的集合,记作;代表图的边的集合,记作。可以看出,边集中的元素是顶点集中元素的元子集,并且默认和的交集为空集。图的分类众多,本文所研究的图均为有限的简单无向图。图分为有限的、无限的、可数的等等,是根据图的阶进行分类的。图的阶是指顶点的个数称,记作。在本文中研究的图,我们总是假定为有限的,阶为的有限图,即。另外,若图只有一个顶点,即,那么这样的图称为平凡图,相反,若,那么这样的图就称为非平凡图。简单图就是既不含平行边也不含自环的图,所说的平行边是指在无向图中,如果和顶点和相关联的无向边多于一条,那么则称这些边为平行边,平行边的条数称为重数。而自环是指两端连接着同一顶点的边。前面有说到无向图,
5、简单说就是不具有方向性的图。定义在图的边的集合中,每个元素为一对顶点构成的无序对,表示顶点和相关联的一条无向边,若是无向图,那么和表示的是同一条边。有图必然会有由产生而来的别的图,这里只介绍子图的概念。假设和是两个图,如果顶点集是的一个子集,边集也是的子集,那么就称图是图的一个子图。我们常常以图的度作为研究图的一个参考,一个顶点的度数是指与它相关联的边的数目,若顶点的度为,则称该顶点为孤立顶点,也就是不与其它任何顶点相连接的点。我们把图中最小顶点度称为最小度,记作,把图中最大顶点度称为最大度,记作。研究图,必然需要知道什么是路。图是一条路,其顶点集和边集分别为,这里的均互不相同。在此,顶点和由
6、路连接,并称它们是路的端点,而称为的内部顶点。一条路上的边数称为路的长度,记,称是一条和之间的路。另外,需要了解下研究图的另一个参考量,连通度。一个图是连通的,如果无向图中的任意一对顶点都是连通的。顶点连通是指在无向图中,若从顶点到有路相连,则称和是连通的。相反,如果一个不连通的无向图,称为非连通图。连通图是指一个图的任意两个不同顶点之间都至少有条相互独立的路相连。连通度是指,使得图是连通的最大整数,记作。边连通图是指一个图的任意两个不同顶点之间至少有条相互独立的路相连。边连通度是指,使得图是边连通的最大整数,记作。其中,最简单的2-连通图是圈,并且其它的2-连通图都可以由一个圈通过不断添加路
7、而得到。认识了图的一些基本概念以后,我们来了解下本文研究的图的彩虹连通数。假设图是非平凡的连通的,定义一个边染色 ,其中相邻的边可能染同种颜色。如果图中的一条路径上的边分别染不同的颜色,那么称是图一条彩虹路;如果图任意两个不同顶点和之间至少有一条彩虹路相连,则称图是彩虹连通的。在这种情况下,染色称为图的彩虹边染色。如果使用了种颜色,那么称是一个彩虹染色。如果是对图进行彩虹边染色所需的最少颜色数,称为图的彩虹连通数,记作。显然,彩虹连通图一定是连通的,且将所有边染不同颜色可以得到连通图的一个彩虹染色。如果图中的两个顶点和之间有路相连,则称和之间所有路中最短路的长度为和之间的距离,记为。连通图的任
8、意两个顶点之间距离中的最大值,称为是图的直径,记作。如果图是一个边数为的非平凡连通图,则有。为了说明上述的,我们考虑图。图给出了图的一个3-边染色,可以验证图中任意两个不同顶点之间都有彩虹路相连。故图的3-边染色是一个彩虹染色,从而。因为,所以,图的任何彩虹染色至少使用了两种颜色,即。假设,图有一个彩虹染色,那么对于图的相邻的两条边可能染同种颜色,比如说,边和边染相同的颜色。由于图中任意两个不相邻顶点之间有且仅有一条长度为2 的路,而和之间的2-长路不是一条彩虹路,故和之间没有彩虹路相连,这与是图是一个彩虹染色的假设相矛盾。因此,。图 彩虹染色图接下来,我们考虑另外一个例子,在这个例子中,图是
9、彩虹染色的。假设,是图的一个最小彩虹染色,并且说明了。显然,从图中可以得到,。现在,假设,正如图所示,在图中的条路中至少有一条彩虹路,比如说,是一条彩虹路。进一步假设,。接下来,考虑其它边的染色,首先,如果和是图的任意两个顶点,并且,那么在图中仅有一条长度为的路,而其它所有的路的长度是或者更大,因此,这就说明在图中没有两条相邻的边染色是相同的。据此,我们可以这样染色,即图,这样的染色假设不失一般性。接下来,考虑两种情况:情况,那么,在这种染色下,图中没有彩虹路。情况2,那么,。又得考虑,如果,那么在这种染色下,图中没有彩虹路;如果,那么在这种染色下,图中没有彩虹路。综上所述,在假设下的边染色中
10、至少有两个顶点之间不存在彩虹路,这与假设图中至少有一条是彩虹路是矛盾的。因此,确定。图 图:通过这两个例子,我们可以得出,如果图是一个大小为的非平凡连通图,则有:。通过上述的例子,我们已经初步了解到图的彩虹染色,彩虹连通数等概念,本文针对三类特殊的图进行彩虹染色,并且给出了彩虹连通数的一个上界。对于彩虹连通数,定理给出了等人对于图是完全图,或是一棵树,或是一个圈的彩虹连通数,这个定理对于本文研究的第一类特殊图,度数为的图的彩虹染色有相应地运用。参考文献,作者证明了对于任意的连通图的彩虹连通数的上界,即,利用这个结论证明度数为的图的彩虹染色方法是有意义的;参考了文献,推导出了新轮图的彩虹连通数;
11、参考了文献,从连通图推导出图是一个连通的串并联图,进一步根据连通串并联图,最后得到了考虑广义图,并且本文对广义图进行彩虹染色,得到了彩虹连通数。第一章 特殊图类的彩虹连通数在本文中所研究的图均考虑是有限简单无向图。定理令是大小(顶点数)为的非平凡连通图,即图的阶为,则有:;,是完全图;,是一棵树;,是顶点数的圈。补充说明,一个图是完全图,那么图中任意两个顶点之间都有一条路相连接。接下来,首先了解,什么样的图是图,在这里给出其定义:定义 在平面上嵌入一棵树,的每个内部顶点的度数至少为3,并且至少有一个内部顶点。再做一个圈连接的所有叶子顶点,即圈上的顶点是由的所有叶子顶点组成。这样得到的图被称作图
12、,树叫做特征树,圈叫做伴随圈。根据定义,我们可以知道,图是一个连通图。在文献中,作者证明了:(找出哪篇文章里得到的这个结果)要计算出任意的一个图的彩虹连通数是一个困难的问题。但是,在文献中,作者证明了对于任意的连通图的彩虹连通数的上界,即。第一节 度数为的图的彩虹连通数上面已经给出了图的定义,我们要研究是顶点度数为的一类特殊图。定义 定义一个特殊图类满足以下条件的图:(1)特征树的每个内部顶点(包括根结点)的度数均为;(2)伴随圈的顶点(即的叶子顶点)与相关联的上一层的结点构成了三角形;(3)从根结点到每一个叶子顶点的层数是相同的。对于这样的图,我们可以看到,每个内部结点的度为,并且只有一个根
13、结点,为了简化叙述,可以把根结点记作,把根结点外一层记作第一层,依次往外是第二层、第三层等等。可以从图中看出,第一层有个顶点,第二层有个顶点,第三层有个顶点,第四层有个顶点,以此类推,第层有个顶点。对一个度为,有层的图,记第()层为,其总的顶点数为。图所示的是第四层有个顶点(叶子顶点),总的顶点数为的图。考虑了度为,有层的图的这些特点以后,我们可以这样对其进行边染色。首先考虑伴随圈的染色,因为其顶点(特征树的叶子结点)与相连的结点构成了七个顶点的子图,只考虑这个部分,对子图进行这样的彩虹边染色。比如,所示的图,这是一个层的图,含有与相连的结点构成的七个顶点的子图,即。考虑子图的边染色,我们选取
14、五边形进行染色,每一边分别染,五种颜色。这个子图还剩余4条边未染色,于是我们给着四条边染,这样的染色,子图便使用了七种颜色。相应地,其它的五个子图使用相同的染色方法,同样只需要七种颜色。此时,伴随圈上还有一些边未染色,我们选取中的任意一种颜色对其进行染色,比如说,我们选取了颜色对这些边进行染色。接下来,我们考虑剩余的未染色的特征树上的边,对于这些边我们选取新的颜色对其进行染色,比如说,分别染,共九种颜色。这样就得到了层的图的一种边染色方法,使用了十六种颜色,可以验证,在这种染色方法下,图是彩虹连通的,因此。图 层的图接下来,我们考虑其它层数的图,并且推导出了其彩虹连通数:情况:当时,则有。层数
15、为的图正如图所示,显然,这是一个完全图,因此,彩虹连通数为。图 的图情况:当时层数为的图如图所示,可以看到,三个子图是一个三角形的完全图,于是我们可以分别染颜色,伴随圈中未染色的边可以染,特征树中未染色的边分别染色。这样的图是彩虹连通的,因此。图 的图情况3:当时我们的染色方法同时的图的染色方法相同,层的图的顶点数,图中包含了个(与相连的结点构成的七个顶点)的子图。将所有这样的子图用上述的方法进行染色,共使用七种颜色,而伴随圈上未染色的边可选取中的任意一种颜色对其进行染色。至此,的特征树中未染色的边的数目为,于是我们可以使用新的种颜色对这些边进行染色。这样得到的一个边染色可验证此时是彩虹连通的
16、,边染色所用的颜色数为,因此。进一步说明此种染色方法得到的图是彩虹连通的。情况:图中任取的两个顶点恰巧位于同一个子图中,。因为我们采取的边染色方法已经使得子图是彩虹连通的,所以,任意两个顶点之间至少有一条彩虹路连接;情况:图中任取的两个顶点其中一个位于同一个子图中,另一个位于特征树上(不包含子图中的顶点)。因为特征树上的边的染色是取用新的颜色,结合情况,我们也很容易知道,任意两个顶点之间至少有一条彩虹路连接;情况:图中任取的两个顶点位于不同的一个子图和中,。因为一个子图中任意一个顶点有三条边连接,所以这样的两个顶点之间有许多条路连接,只要确保这条路径在子图和中边的颜色不同,那么这条路一定是彩虹
17、路,也就是说任意两点之间至少有一条彩虹路连接。因此,无论哪种情况,此种染色方法得到的图都能满足,图中任意两个顶点之间至少有一条彩虹路相连。综上所述,当时,;当时,;当时,。在这样的图中,对于一些层数较少的,比如的图,可以通过简单的边染色方法,就能计算出其彩虹连通数,并且彩虹连通数会少于由式子计算出的彩虹连通数。因此,本文需要再次声明,采取的染色方法是较为保守的,但是确保了这种的染色方法,一定使得图中任意两个顶点之间至少有一条彩虹路相连,是满足了让图彩虹连通。或许,还存在比本文更优的一种染色方法,使得最后得到更优的彩虹连通数,由于知识水平有限,本文就不会进一步研究了。要证明所推出的度为,层为,顶
18、点数为的图的彩虹连通数的合理性,本文从连通图的彩虹连通数的角度进行说明。在文献中,现有的关于连通图的彩虹连通数只是一个上界,即,阶为,最小度为。并且这个上界是针对所有的连通图而言的,而本文验证的是一个特殊的连通图,它的所有顶点的度为,即,。但是,利用这个上界验证之前,在它的基础上对于这个上界做了一些改善,使得更为紧一些,即,再以改善后的这个上界来验证本文的结论。现在,我们开始说明这个上界改善的合理性,参考文献:在图染色理论中,有一些方法是通过图的最小度来研究图的彩虹连通数的,等人证明了,如果图是一个阶数为,最小度为的连通图,那么图的彩虹连通数为。和利用阶支配集的方法,证明了有个顶点,最小度为的
19、连通图的彩虹连通数为。而证明了,对于最小度为的图,即,那么它的彩虹连通数为。然后,等人认为这样的结果并不令人满意,于是改善了和的关于彩虹连通数的上界,即,并且证明了对于所有阶数为,最小度为的连通图都是适用的。已经证明了,如果图是一个阶,连通度,最小度,那么彩虹连通度。等人证明了,如果连通度为,那么彩虹连通数。从等人的结论中,我们能够容易推出彩虹连通数的一个上界:因此,对于连通度,彩虹连通数,连通度,彩虹连通数。接下来,我们将对连通度为的彩虹连通数的上界做出改善,即。定理 如果图是一个个顶点的连通图,那么。证明:假设存在这样一个是图的一个最大连通子图,并且满足,其中是图的顶点数。如果,图中含有一
20、个三角形,令,那么。如果,是图的一个子图,令,那么。如果,在图中包含的所有圈的长度为,那么可以令为包含增加一条侧边的图,显然,当时,。接下来,假设,在的外部有四个不同的顶点,分别是,并且它们有三条内部不相交的路径到,进一步假设,这四个顶点,每三个顶点时相邻的。令边映射到顶点,。我们可以把这四个顶点加入图中,从而形成一个更大的子图,它有个顶点。现在进行染色,只使用两种新的颜色色和色对条边进行染色,使用色对边,进行染色,使用色对其它的条边进行染色。那么我们对的选择有了矛盾。这就说明了至少其中有四个顶点,例如,有这样的属性,其中的三条内部不相交路径的长度至少是。而且,其中的所有顶点都满足上述的属性,
21、我们选择顶点使得三条路径的其中一条长度为,比如说,而使路径和的长度之和尽可能大。令,其中,对于所有的和,。不失一般性,我们假设,且。进一步,先假设。我们可以把顶点加入中,从而构成一个更大的子图,它有个顶点。如果是偶数,那么我们可以使路径的条边染色,需要种新颜色。路径的前半部分染色是全部不相同的,路径的后半部分相同序号的颜色是重复的。我们对边的染色可以选择中已经重复的任意一种颜色,那么这就简单验证了是彩虹连通的。如果是奇数,那么我们可以使路径的条边染色,需要种新颜色。路径的中间部分的边和边使用中已经使用过的任意一种颜色进行染色。路径的前部分条边染色是全部不相同的,路径的后部分条边中相同序号的颜色
22、是重复的。这就证明了是彩虹连通的。于是,我们有:这就和的极大性矛盾了。因此,我们只要假设。现在,我们已经证明了。如果,那么;如果,那么;如果,那么。综上所述,很容易推出:。说明是有意义的:上面我们已经按照定义的染色方法推出了,度为,层为,顶点数为的图的彩虹连通数,然后,我们又对连通图的彩虹连通数的上界进行的改善,得到了一个更好的上界,即。这里的指的是连通图中的顶点数,于是,我们可以计算下图中的顶点数,即,是层数。这样,就关于层数的函数,而也可变换为有关层数的函数,。做一个简单的计算,可以得到:,当时。第二节 特殊图类,个内部顶点的轮图前面对轮图做了大致介绍,这里需要做进一步说明。首先定义圈,其
23、边为,。对于的圈,在圈中加入一个顶点,使得与圈上的每个顶点连接,那么这样的图就称作轮图。轮图是一个有个内部顶点,个叶子顶点,且被一个圈连接的图,根据图的定义,可知轮图是一个特殊的图,最小度。 在前面已经证明了圈的彩虹连通数,接下来也将给出轮图的彩虹连通数,并证明。当然我们所研究的不仅仅是这样的轮图,而是圈中加入了个顶点的轮图,并且给出轮图的彩虹连通数和证明。新轮图是一个有个内部顶点,但个顶点之间没有边直接相连接,有个叶子顶点,且被一个圈连接的图,根据图的定义,可知新轮图并不是一个特殊的图,但是它的特殊性值得研究,那么新轮图的最小度。在推导新轮图的彩虹连通数之前,让我们先来看看轮图的彩虹连通数,
24、参考了文献。定理 当时,轮图的彩虹连通数是:证明:假设有一个阶的圈,还有一个顶点连接圈的每个顶点构成的图称为轮图。首先考虑,当时,。这时的轮图是一个完全图,因此。再考虑,当时,轮图不再是一个完全图,于是。定义一个边染色如下:如果是奇数,则,;如果是偶数,则,。可以验证这样的一个边染色就是一个彩虹染色,因此。最后考虑,当时。定义一个边染色如下:如果是奇数,则;如果是偶数,则;对于每个,有。可以验证这样的一个边染色就是一个彩虹边染色,于是。接下来,我们证明。因为的不是一个完全图,于是。现在,做一个相反的假设,同样定义轮图的一个彩虹染色,并假设。对于每个,是中的唯一的长度为的路,所以,对于,。由于,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 特殊 彩虹 染色 毕业论文
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3988049.html