特殊图类的彩虹边染色.doc

《特殊图类的彩虹边染色.doc》由会员分享，可在线阅读，更多相关《特殊图类的彩虹边染色.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流特殊图类的彩虹边染色.精品文档.1 前言我们都知道，图论是源于一个著名的问题哥尼斯堡七桥问题。后来英国的数学家汉密尔顿通过十二面体“绕行世界”的游戏，使得很多人开始关注这个图论中的另一个著名问题，即汉密尔顿问题。谈到了图论中的著名问题，那就不得不提世界近代三大数学难题，同时对图论发展产生了重大影响的“四色猜想”，这使得图论中的染色问题成为了研究的热点问题，图的染色问题不但在理论上有着重要的意义而且在实际问题中也有着重要的应用。说到实际应用，对于图论的许多公开问题，比如说，企业生产管理，交通运输，计算机网络，甚至军事等众多领域一直以来都有许多专

2、家学者所研究。而说到图的染色的实际应用，我们得介绍下何谓染色。所谓的染色问题，就是给定一个图，需要把图中的所有的顶点，或者所有的边进行染色，使得相邻的顶点或者边所染的颜色不同，其中优秀的染色方法，就是尽量使得需要的颜色数最少。同样，图的染色在许多领域都会涉及到将某种对象的集合按照一定的规则进行分类，比如说，学生选课系统、电路布局、排序问题、会议安排、电路安排、考试安排等，这些问题都与图的染色理论密切相关，专家学者对图的不同染色问题的研究，已经有了较为丰富的结果，并且这些结果仍在进一步完善中。2008年，Chartrand, Johns, McKeon和Zhang首次提出了图的彩虹连通性的概念，

3、这是对经典连通性概念的一种加强。我们都知道，彩虹连通数是一个自然的组合概念，除了具有理论上的意义，更重要的是在网络问题中有着很重要的应用。事实上，政府机构之间需要进行一些机密信息的传递，这些传输要保证其安全性，于是便产生了彩虹连通的这些概念。假设信息的传输是在一个蜂窝形状的网络中，而这个网络中的任意两个顶点之间都有一条路相连，并且这条路径上的每一段路需要分配一个独特的频道（比如说，分配不同波段的频率）。显然，我们想要网络中所使用的不同的频道的个数最少，而这个最少的个数就是这个蜂窝网络所对应的无向图的彩虹连通数。在了解图的彩虹连通数之前，我们先对用到的一些图论基础知识做一个简单的介绍。首先，需要

4、了解图的定义，图定义为一个二元组使得，记作。其中，代表图的顶点的集合，记作；代表图的边的集合，记作。可以看出，边集中的元素是顶点集中元素的元子集，并且默认和的交集为空集。图的分类众多，本文所研究的图均为有限的简单无向图。图分为有限的、无限的、可数的等等，是根据图的阶进行分类的。图的阶是指顶点的个数称，记作。在本文中研究的图，我们总是假定为有限的，阶为的有限图，即。另外，若图只有一个顶点，即，那么这样的图称为平凡图，相反，若，那么这样的图就称为非平凡图。简单图就是既不含平行边也不含自环的图，所说的平行边是指在无向图中，如果和顶点和相关联的无向边多于一条，那么则称这些边为平行边，平行边的条数称为重

5、数。而自环是指两端连接着同一顶点的边。前面有说到无向图，简单说就是不具有方向性的图。定义在图的边的集合中，每个元素为一对顶点构成的无序对，表示顶点和相关联的一条无向边，若是无向图，那么和表示的是同一条边。有图必然会有由产生而来的别的图，这里只介绍子图的概念。假设和是两个图，如果顶点集是的一个子集，边集也是的子集，那么就称图是图的一个子图。我们常常以图的度作为研究图的一个参考，一个顶点的度数是指与它相关联的边的数目，若顶点的度为，则称该顶点为孤立顶点，也就是不与其它任何顶点相连接的点。我们把图中最小顶点度称为最小度，记作，把图中最大顶点度称为最大度，记作。研究图，必然需要知道什么是路。图是一条路

6、，其顶点集和边集分别为，这里的均互不相同。在此，顶点和由路连接，并称它们是路的端点，而称为的内部顶点。一条路上的边数称为路的长度，记，称是一条和之间的路。另外，需要了解下研究图的另一个参考量，连通度。一个图是连通的，如果无向图中的任意一对顶点都是连通的。顶点连通是指在无向图中，若从顶点到有路相连，则称和是连通的。相反，如果一个不连通的无向图，称为非连通图。连通图是指一个图的任意两个不同顶点之间都至少有条相互独立的路相连。连通度是指，使得图是连通的最大整数，记作。边连通图是指一个图的任意两个不同顶点之间至少有条相互独立的路相连。边连通度是指，使得图是边连通的最大整数，记作。其中，最简单的2-连通

7、图是圈，并且其它的2-连通图都可以由一个圈通过不断添加路而得到。认识了图的一些基本概念以后，我们来了解下本文研究的图的彩虹连通数。假设图是非平凡的连通的，定义一个边染色 ，其中相邻的边可能染同种颜色。如果图中的一条路径上的边分别染不同的颜色，那么称是图一条彩虹路；如果图任意两个不同顶点和之间至少有一条彩虹路相连，则称图是彩虹连通的。在这种情况下，染色称为图的彩虹边染色。如果使用了种颜色，那么称是一个彩虹染色。如果是对图进行彩虹边染色所需的最少颜色数，称为图的彩虹连通数，记作。显然，彩虹连通图一定是连通的，且将所有边染不同颜色可以得到连通图的一个彩虹染色。如果图中的两个顶点和之间有路相连，则称和

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、轮图的彩虹连通数之前，让我们先来看看轮图的彩虹连通数，参考了文献。定理 当时，轮图的彩虹连通数是：证明：假设有一个阶的圈，还有一个顶点连接圈的每个顶点构成的图称为轮图。首先考虑，当时，。这时的轮图是一个完全图，因此。再考虑，当时，轮图不再是一个完全图，于是。定义一个边染色如下：如果是奇数，则，；如果是偶数，则，。可以验证这样的一个边染色就是一个彩虹染色，因此。最后考虑，当时。定义一个边染色如下：如果是奇数，则；如果是偶数，则；对于每个，有。可以验证这样的一个边染色就是一个彩虹边染色，于是。接下来，我们证明。因为的不是一个完全图，于是。现在，做一个相反的假设，同样定义轮图的一个彩虹染色，并假设。

25、对于每个，是中的唯一的长度为的路，所以，对于，。由于，于是。这就使得，反过来使得。类似的，使得。因为和，从而在图中路径不是一条彩虹路，这就产生了矛盾。于是。因此综上，。考虑新轮图，一个阶的圈，还有个顶点连接圈的每个顶点，且这个顶点之间没有边直接相连，这样构成的图就是新轮图。对新轮图进行染色，因为个内部顶点之间没有直接的边连接，为了确保内部顶点之间至少有一条彩虹路连接，所以先考虑个内部顶点之间的彩虹路。为了叙述简洁，给出一个的新轮图，如图所示，圈，并有的内部顶点。为了便于观看，只选取了圈上的一个顶点与内部的顶点相连，同时省略了个内部顶点与圈上别的顶点之间的连接边。可以看出，个内部顶点之间存在一条

26、最短的路，且，于是决定将此条路染色成彩虹路，因此边分别染，这样的染色方法确保了个内部顶点之间的最短路径是一条彩虹路。至于个内部顶点与圈上别的顶点之间相连边的颜色，也完全可以从种颜色中取出，且远远满足染色需要。类似的，对于个内部顶点，要保证个内部顶点中，任意两个顶点之间有一条彩虹路相连，则需要的颜色数为。图 的新轮图接下来结合圈考虑新轮图是彩虹连通的，可分三类情况进行讨论：情况：圈上的顶点数与内部顶点数相同，即。按照上述的染色方法，能够保证任意两个内部顶点和，之间至少存在一条彩虹路相连，圈上的边的染色需要的颜色完全可以取自种颜色，并且不需要取全部的种颜色就能使得在图中，任意两个顶点之间至少有一条

27、彩虹路相连。因此，彩虹连通数。情况：圈上的顶点数少于内部顶点数相同，即。同情况类似，圈上的边的染色需要的颜色完全可以取自种颜色，且远远少于种，就能够满足在图中，任意两个顶点之间至少有一条彩虹路相连，种颜色就已经使得图彩虹连通。因此，彩虹连通数。情况：圈上的顶点数多余于内部顶点数，即。断言这种情况下的彩虹连通数应是，假设，那么对于内部的个顶点而言，会使得其中某些顶点之间没有彩虹路相连，比如说顶点和，之间连接的边染了同种颜色，就没有彩虹路。所以，假设不成立。另一方面，要使图中，任意两个顶点之间至少有一条彩虹路相连，种颜色就已经满足染色需求，不需要多一种的颜色。这点可以从一个简单的例子进行说明。为说

28、明情况，给出一个的新轮图，如图所示，圈，有个内部顶点，所以彩虹连通数，就是说这个图只需要中颜色进行染色，就可以使得图中任意两个顶点之间至少有一条彩虹路相连，即图是彩虹连通的。之前有说明，顶点数的轮图的彩虹连通数是，增加一个内部顶点以后，可以使得彩虹连通数变为。因此，研究这类的新轮图是有一定意义的。图 的新轮图对上述的讨论作补充说明：情况中的圈上的顶点数多余于内部顶点数相同，即，只是相对而言，数量多，而不是远远大于。比如说，圈中，而内部顶点数，像这样的远远大于的情况是不属于情况中所说的范围，我们只是针对，但是两者之间较为接近的情况进行的一个讨论。因为远远大于的这种情况属于特例，某些情况下甚至找不

29、到任何一种染色方法使得它彩虹连通，或者说它就不存在彩虹连通图。那么这样的图类对于我们的研究没有任何的意义，所以就不是情况所讨论的范围。类似的，情况中圈上的顶点数少于内部顶点数相同，即，只是针对和相差并不是很大的情况。比方说，圈中，而内部顶点数，按照本文的染色方法，就需要种颜色才能使得图彩虹连通，即，对于这类的图，虽然可以计算出彩虹连通数，但是失去了图的彩虹染色的意义，在实际的应用中，我们对于这样两方相差悬殊，必定会对少的一方做一些补充，否则投入成本过大，这也就失去了实际应用的意义。综上所述，我们可以确定新轮图的彩虹连通数。当，时，新轮图的彩虹连通数是：。第三节 特殊图类，广义图的彩虹连通数在讨

30、论广义图之前，我们先来了解几个定义。这些定来自参考文献。首先是彩虹连通，如果一条路的边分别染不同的颜色，那么这条边染色路就是一条彩虹路。如果图中任意两个顶点之间是连通的，并且由条内部顶点不相交的彩虹路连通，那么边染色图就是彩虹连通的，其中。接下来，我们给出彩虹连通数的定义：若存在图的一个边染色，使用种颜色就能够使得图彩虹连通，其中是最小的整数，那么彩虹连通数为：。对于连通图的彩虹连通数，记作，即。本文的概念定义部分介绍了，一个图是连通的，当且仅当任意两个顶点之间是连通的，并且由条内部顶点不相交的路径连通。因此，前面定义的仅仅是针对连通图而言的。我们继续说明，在参考文献中，对于，等人证明了，如果

31、图的阶数为，那么，如果图是连通的，即，那么。等人证明了，如果图的最小度为，那么，并且证明了对于所有阶数为，最小度为的连通图都是适用的。因此，如果图是连通的，那么。另外，上文有说明图是连通的，即，可以采用改善后的界，即。参考了文献以后，接下来的部分是从连通图，推及到连通的串并联图，在推广到广义图，并且对它们的彩虹连通数做出了证明，特别是对于路径数的广义图，其彩虹连通数是或者是。本文会提供一种新的染色方法，使得广义图是彩虹连通的，并且彩虹连通数小于。首先，了解连通图：定理如果是一个连通图，顶点，那么。在情况中，如果图是一个连通串并联图是一个简单图，从三个顶点开始，反复运用一个操作序列，这个序列是一

32、个分支，由一条边变换成双条边，反复增加分支边。那么这样的连通图就是一个著名的亚族。证明定理，我们是通过先证明一个强有力的定理的结论，然后间接证明定理。定理如果是一个连通图，顶点，那么存在图的一个边染色，至多是种颜色满足以下结论： 对于任意两个顶点，这里存在两条不相交的彩虹路； 对于任意一个顶点，任意集合，且，这里两条彩虹路，只有顶点相同； 对于任意两个集合，且，这里的两条彩虹路不相交。对于而言，如果，那么其中的一条路径取自顶点。类似的，对于，如果和相交，那么一条适合的路径是一个点，这点在中。显然，定理是来自定理，所以先证明定理，证明之前先给出一个定理。定理令是一个连通图。对于任意的顶点和任意集

33、合，这里有从到的条路径，使得对于其中的任意两条路，仅仅只有一个共同顶点。定理的证明：首先定义图的一些子图，其中，。因为任意的连通图都含有一个顶点至少是的圈，于是令是图的一个顶点至少是的圈。现在，假设找到这样一些图，如果，那么集合，否则的话，这里存在一个顶点。根据定理，发出路到，这里的每对路径仅仅汇集与，那些路是的一个细分。令是一些路的集合。重复这个过程，直到结束。对于每个，归纳证明了，存在一个的边染色，至多使用种颜色，使得定理中的到的性质成立，这里使用代替。那么，集合就意味着对于而言定理成立。接下里，先对每个定义一个边染色。显然，是一个圈，它是彩虹染色的。假设有一个边染色，颜色是，其中。通过附

34、加一个细分的到得到图，其中条路径汇集于顶点。假设路径是，。对于的情况，可以假设。令，是路劲的另一个端点，其中。分别把的第一条边和最后一条边射入到和。情况：，。彩虹染色使用的颜色为。就而言，的染色使用颜色为，采用这样的染色方法，每种颜色至少出现过次。总的，使用了种新的颜色。情况：，。彩虹染色使用的颜色为。染使用的所有颜色数为。总的，使用了种新颜色。情况：。假设存在最大的整数，使得。对边进行染色，路径的第一条边和路径的最后一条边染色，路径的最后一条边和路径的第一条边染色。路径的最后一条边和路径（每一条长度为1）染色。的其余的边染不同的新的颜色。总的使用了种新的颜色。重复归纳，可以得到的一个染色，。

35、归纳证明了，对于的染色满足所有的需求，。显然，对于，我们使用了种颜色，定理的到成立。现在，假设对于的染色，至多使用了种颜色，定理的到成立。对于情况和情况，因为，所以的总的使用颜色数至多是。对于情况，因为，所以的总的使用颜色数至多是：最后，我们在情况到情况中验证，定理的到成立对于成立。对于归纳假设，如果。类似的，对于，；对于，。现在，对于证明了到成立。这就完成了定理的证明，因此定理也就成立了。完成了连通图的介绍，接下来考虑图是一个连通的串并联图，参考文献：定理如果图是一个连通的串并联图，顶点，那么。我们可以知道，当时圈，有个顶点时，彩虹连通数。这是特殊情况，更为一般的情况是，图是一个广义图。定义

36、广义图：令，它是的路径的集合，路径的长度，其中，并且路劲上的每对内部顶点时不相交的，而且都有两个相同的端点。如图所示的就是一个有四条路径的广义图。图 四条路径的广义图定理证明：首先定义一些子图，是一个圈。是从附加一条长度至少为的路径到得到的，用两个不同的顶点来辨别路径的末端点。和一定是一些路径的末端点，如果一些路径的末端点是路径的的内部顶点，那么路径一定包含了路径的两个端点。每个是一个连通串并联图。构造串并联图，设置，先确定一个圈，以顺时针旋转作为参考。对于定义一个方向和一个平面，以的外部为导向顺时针圈，且包含。而且，假设路径是以外部为导向，。如果增加的路径是以外部为导向，那么导向使得，任然在

37、新的外部圈中。另外，如果，对于选择外部和导向使得是的末顶点。否则，删除直到第一个使得加入的在的外部。加入的和方向同上面方法一样。注意点，是加入到由造出的外部界，当加入的外部。因此，我们能够重复加入和重复导向，按照这样做法，对于达到一个外部和一个导向。最后，重复标签分别是。对于每个重复，直到。假设是的外部圈，使得。接下来，的边染色，种颜色。首先，是彩虹染色，使用了中颜色。假设是染色，使用了中颜色。加入到的外部。那么是染色的，使用了种颜色。因此，证明了，对于每个，是彩虹连通的。所以证明了定理。完成了连通串并联图，最后考虑广义图，参考了文献：定理如果是一个广义图，顶点数为，那么定理证明：假设是条路径

38、，是条路径的共同的端点。显然，时，图就是一个圈。因此，假设。首先，因为，如果给图染色，少于种颜色，那么对于某些顶点，在中存在唯一的路径不是彩虹路。但是在中，有唯一的一对不相交的路，并且是其中的一条路径。因此，。接下来，对染色。路径的边染色映射到端点和，分别染色和，其中。下一步，对别的边染不同的颜色。那么对于使用了种颜色，并且这种染色是一个彩虹连通的，其中。因此，。现在，我们考虑对于广义图进行彩虹染色，这是在已有的基础上提出更优的彩色方法。以简单的只有条路径的广义图来说明染色方法，然后推理到有条路径的广义图。如图所示，广义图的端点是和，四条路径分别是：。我们的染色方法是从里面的路径开始，以相对的

39、两条路径为一对来进行染色。比如说，考虑路径和路径为一对，路径和路径为另一对。路径上有个顶点，有条边；路径上有个顶点，有条边。于是，我们可以得到，边数总是比顶点数多，那么假设上有个顶点，就有条边，类似的，上有个顶点，就有条边，。回到路径和路径的染色上，显然这两条路径加上端点和就是一个圈，总的有条边，考虑最远的两个顶点（端点和不作为首先考虑的顶点），和，这样就形成了两条路，顺时针的一条，即，长度为，逆时针的一条，即，长度为。此时要选取长度较长的一条进行染色，于是选取以顺时针的一条染色，分别染。剩下边的染色，颜色一定取自这五种颜色，我们这么考虑，路径，也可以分为顺时针的一条，和逆时针的一条，可以看到

40、的是顺时针的一条长度是，所以考虑这条路径的染色，发现边没有染色，并且中颜色中只剩下，所以染。类似的，对于路径，也取长度为的路径，未染色的边只有，并且只能染。这样的染色后，只剩下边和边未被染色，可以分别取和，就能确保在中，任意两个顶点之间至少有一条彩虹路，那么彩虹连通数。我们都知道，一个图是圈的话，它的彩虹连通数是，如果从圈的角度来验证，图的彩虹连通数是满足的。回到图的推广上，上面的例子中的路径和上的顶点数是具体的，如果的顶点数变为，的顶点数变为，那么对于图还是采用上述的方法进行彩虹染色，于是彩虹连通数是：。图 四条路径的广义图完成了路径和的彩虹染色，我们再来考虑另外一对路径和的彩虹染色。采取相

41、同的染色方法，考虑图，如图所示，图上总的有条边，考虑最远的两个顶点（端点和不作为首先考虑的顶点），和，形成了两条路，顺时针的一条，即，长度为，逆时针的一条，即，长度也为。因为长度都相等，所以选取哪一条染色都不会影响结果，为了便于叙述，我们还是选取顺时针的一条染色，分别染新的颜色，即。剩下边的染色，颜色一定取自这五种颜色，所以我们可以这样考虑，路径，也可以分为顺时针的一条，长度是，和逆时针的一条，长度也是，还是对顺时针的一条进行染色，发现只有边没有染色，并且五种颜色中只可以选取，所以染。类似的，对于路径，也选取顺时针的一条，长度是，只有边未染色，并且只能染。再选取路径，选取顺时针的一条，长度是，

42、只有边未染色，并且只能染。这样的染色后，只剩下边和边未被染色，可以分别取和，就能确保在图中，任意两个顶点之间至少有一条彩虹路，那么彩虹连通数。按照上面的推广，如果的顶点数变为，的顶点数变为，那么对于图还是采用上述的方法进行彩虹染色，于是彩虹连通数是：。图 四条路径的广义图到这一步，我们就完成了这个只有四条路径的广义图的彩虹染色，运用这样的彩色方法，就使得图中任意两个顶点之间至少有一条彩虹路相连，广义图是彩虹连通的，并且彩虹连通数是。在前面，我们给出了有个顶点，路径数的广义图的彩虹连通数或者，按照这样的计算，本文的四条路径的广义图，顶点数（不计算端点和），那么彩虹连通数至少也是。而按照本文的染色

43、方法得到的彩虹连通数是，少于计算出的彩虹连通数，所以本文的给出的针对广义图的染色方法可以减少所使用的颜色数，是有意义的染色方法。接下来，我们考虑顶点数是（不计算端点和），路径数的广义图。按照本文的染色方法，我们分路径数是偶数和奇数的情况讨论：情况：，且是偶数。这类广义图从最里的一对路径和开始染色，直到最外的一对路径和。如果路径的顶点数分别是：，且，那么彩虹连通数，。情况：，且是奇数。这类广义图从最里的一对路径和开始染色，直到最外的一对路径和，这些染色方式按照本文介绍的方法进行染色。这里的问题只是在于还有一条单一的路径，我们只需要使得这条路径是一条彩虹路，就能够保证整个广义图彩虹连通。要使是一条

44、彩虹路，则这条路上的边必须染不同的颜色，有个顶点，则需要种颜色。所以，这类的广义图的彩虹连通数，。无论是情况还是情况，按照本文方法进行的彩虹染色，得到的彩虹连通数都优于。综上所述，个顶点的广义图的彩虹连通数是：其中，个顶点是指不计算端点和，只是条路径上顶点的总数，即，。第三章 结语本文是课题是“特殊图类的彩虹边染色”，选取三类特殊图。第一类是：度为的图，按照本文的染色方法进行彩虹染色，使得图是彩虹连通的，并计算出了这类图的彩虹连通数，其中是层数，且。利用改善后的连通图的彩虹连通数说明了是有意义的。第二类是：圈为，有个内部顶点的新轮图，按照本文的染色方法进行彩虹染色，使得图是彩虹连通的，并计算出

45、了这类图的彩虹连通数，其中圈上顶点数，内部的顶点数。并且说明了，当时，轮图的彩虹连通数是，而增加一个内部顶点，变成新轮图，虽然边数增加，但是彩虹连通数却是，比轮图减少了。第三类是：个顶点的广义图，按照本文的染色方法进行彩虹染色，使得广义图是彩虹连通的，并计算出了这类图的彩虹连通数，而现有的广义图的彩虹连通数是，其中路径数，本文染色得出的远比现有的优异许多。本文选取这三类特殊图进行彩虹染色，也得到了相应的彩虹连通数，或许本文的染色方法并不是最优异的，得到的彩虹连通数也不是最小的，这点是由于知识水平的有限，不能做到最优秀，还望阅读过本文的读者给予意见，我会进一步改善染色方法，得到更优的彩虹连通数。

46、参考文献1宋慧敏 吴建良. Halin图的均匀边染色J. 山东大学学报，2003 38:31-34；2董九英，李学良.图的彩虹连通数与最小度和J.中国科学：数学，2013,43:7-14；5万慧敏，史小艺，王艳丽.几种特殊图的边染色J.五邑大学学报，2012 26:7-8；6苗莲英.图的边覆盖染色D.山东大学博士论文，2000 25:21-24；7G.Chartrand,et al. Rainbow connection in graphs. Math Bohem，2008;8G.Chartrand，P.Zhang.Introduction to Graph Theory. Boston，20

47、05；9N.Alon，J.H.Spencer. The Probabilistic Method. New York，2000;10Y.Caro,et al. On rainbow connection. Electron J Combin 15, R57 (2008);11Chandran L，Das A，Rajendraprasad D，et al.Rainbow connection number and connected dominating sets. J Graph Theory，2012，71：206-218;12Xueliang Li, Yongtang Shi.Rainbo

48、w connection in 3-connectedGraphs;13Bondy, J.A. and Murty, U.S.R.: Graph Theory, GTM 244, Springer(2008)14Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness andalgorithms for rainbow connectivity, J. Comb. Optim. (in press)15Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (atmost) reciprocal to its minimum degree, J. Graph Theory 63(3), 185191(2010)16Li, X., and Sun, Y., Rainbow Connections of Graphs, S