大学毕业论文-—特殊图类的彩虹点染色.doc

1 前言1.1课题背景图论是数学中的一个重要的分支。它以图为研究的对象。图论原本是应用数学的一个重要的分支，为此，历史上曾有许多位数学家独自地建立过图论。早在1736年欧拉的著作中就出现了关于图论的文字记载，最初他所思考的图论问题都有很强的现实背景。著名的柯尼斯堡七桥问题就是图论的起源。欧拉证明了这个题目没有解，并且把这个题目进行推广，给出了对于一个给定的图可以以某种方法走遍的判定规则。这项研究所取得的成果奠定了欧拉图论及拓扑学创始人的地位。染色问题是图论的一类重要的题目，具有重要的实际意义和理论意义。不同类型的图的染色问题一直是图论中的热点题目，而连通图的染色问题又是其中一种很重要的分支。染色问题就是给定一个图，把它所有顶点或所有的边染上颜色，使得相邻顶点或边的颜色都不相同时所需要的最少的不同的颜色数，边的染色题目可以转化为点染色题目，它们都能归于将一个图划分为独立子集的理论。目前，伴随着图的染色问题在实际问题中被广泛的应用，研究这类问题的学者在逐渐的增多。对不同图类的染色问题的研究，已经有了比较丰富的成果，并且这些结论还在不断的完善之中。连通性是图论中最重要的性质之一，2008年，Chartrand，Johns等人首次提出了图的彩虹连通性的概念，是经典连通性概念的一种加强。作为一个自然的组合概念，彩虹连通数不但有其了理论意义，而且在网络问题中起到了非常重要的作用。事实上，它产生于政府机构之间机密信息的安全传输，在网络安全等实际问题中有很多的应用。假如我们需要在一个蜂窝网络中进行信息的传输。在网络中的任意两点在之间都要有一条路相连接，而且在该路径上的每段都被分配一个独特的频道（例如，不同的频率）。显而易见，我们需要求出的是能在网络中所使用的最少的（不同）频道个数。而这个最少个数恰好是这个网络所对应无向图的彩虹连通数。彩虹点连通的概念是由Krivelevich，Yuster首次提出的，是彩虹连通性的一种重要推广。它也有着很多实际的应用，也同样是研究的热点问题之一。1.2问题来源在教学工作中,我们常常能遇到类似这样的题目：一所学校有n种课程需要由学生来选修，学期结束后要对学生进行考试。显然，每个考生每场只能参加一门课程的考试。试问这次考试最少要进行几场? 显然，不可以在同一个时间进行同一个学生所选修的两门课程的考试。当然，不会出现同一个学生的不同课程在同一个时间所进行的考试。我们可以把这样的问题归结为：在一个平面上取个顶点分别来表示这门课程。如果有同学同时选择了课程和，则把点之间连一条边，可以得到一个有个顶点的无向图。这样的问题可以看做给图的每一个顶点染色，并要求相邻的两个顶点染不同的颜色，求最少要进行几场考试，就是最少能用多少种颜色使得图的相邻顶点都有不同颜色。这样的问题就是顶点染色问题。有关顶点染色问题的形式有很多种，它们在实际应用中也都有着不同的用处。图的染色问题也是由地图的染色问题延申而来的：用种颜色给地图染色，让地图上的每一个区域都有一种一种颜色，并使得相邻的地区颜色不同。问题处理：如果把每一个地区看作一个顶点，把相邻两个地区用一条边连接起来，就能够把一个区域图看作一个平面图。例如，图1（a）所示的区域图可看作为图1（b）所表示的平面图。19世纪50年代，英国学者提出了任何地图都可以用4种颜色来染色的问题并称之为4色猜想。100多年之后，才由美国学者在计算机证明了这个问题，这就是著名的四色定理。例如，在图1中，把不同的区域用城市的名字来表示，所染的颜色用不同的数字来表示，则在图中表示了不同的地区用不同的染色来染色的问题。跟图的边着色问题一样，生活中的很多问题，也可以给它们建立一个模型并看作为图的顶点染色问题来处理。例如课程安排问题，电视频道分配问题，变址寄存器问题等等。1852年，格里斯注意到可以用4种颜色来为美国地图进行染色，使得相邻地区（有一段公共边界，不只一个公共点）有不同的颜色，进一步指出了四色猜想。图 11.3 研究该课题的意义在日常生活中，还有许多问题可以用彩虹顶点染色加以解决，比如电视频道分配问题，变址寄存器等，可以运用彩虹染色方法轻松解决，图的染色理论是图论中的重要内容，也是图论的起源之一。几百年来，很多的数学家们都为此花费了大量的心血去研究。迄今为止，图论的许多公开问题一直是专家学者们的钻研的重点题目。在生产管理、军事、交通运输、计算机网络等许多的领域图论的知识在其中都有着重要的应用，彩虹连接数在网络领域也有很多的应用。假设G代表一个一个细胞网络，我们希望在管道的任意两个顶点之间能够传递消息，这要求每个链接上的顶点之间的路由都分配了一个不同的渠道(如不同的频率)。显然，我们希望使用不同渠道的数量降至最低，用彩虹染色的方法就可以解决这个问题。2 基本概念2.1图论、染色问题的基本概念图是一个二元组使得，所以的元素是的元子集。并且认为和的交集为空集。图的顶点集合是中的各个元素，顶点的集合记作；而图的边的集合为中的元素，边的集合记作。一个图的阶就是图的顶点个数，记作。根据图的阶数，我们把图分为有限的、无限的、可数的等等，在本文中所研究的图，我们总是假定图是有限的，阶为的有限图，即。此外，仅有一个顶点的图称为平凡图，即平凡图的阶，相反，阶的图称为非平凡图。在无向图中，如果与顶点和相连接的无向边多于一条，则把这些边称作平行边，而平行边的条数我们称之为重数。自环是两端连接着同一顶点的边，既不含平行边也不含自环的图称为简单图。图的边的集合中，每个元素对为一对顶点构成的无序对，表示顶点和相关联的一条无向边，因此和是同一条边。若是图中所有的边都是无向边，这类图称为无向图。本文所研究用到的图均为有限的简单无向图。假设有两个图和，如果两个图的顶点集有这样的关系，是的一个子集，边集是的一个子集，那么就称图是图的子图。一个顶点的度数是指与它相关联的边的数目。不与其它的任何顶点邻接的顶点，即度为0的顶点称为孤立顶点。图形的最小度指的是所有顶点之间的最小度，记为；而图最大度：指的是所有顶点之间的最大度数，记为。图是一条路，如果其顶点集和边集分别为，这里的均互不相同。顶点和由路连接，并称它们是路的端点，而称为的内部顶点。一条路上的边数称为路的长度，记，称是一条和之间的一条路。在无向图中，若从顶点到有一条路相连，则称和之间是连通的。如果无向图中的任一对顶点之间都是连通的，则称图是连通图，反之，如果一个无向图不是连通的，则称作非连通图。如果一个图的任意两个不同的顶点之间都有条相互独立的路连接，则把图称作连通的。其中使得图是连通时的最大整数称作的连通度，记作。如果图的任意两个不同顶点之间都有条边不相交的路相连，则称图是边连通的。其中使得图是边连通的最大整数称为的边连通度，记为。图的顶点染色称为正常（顶点）染色，如果的每条边的两端点都染不同颜色。图的种颜色的正常（顶点）染色称为（顶点）染色色。这样的一个顶点染色给出了的一个划分（）使每个都是的一个独立集。如果有一个（顶点）着色，则称是（顶点）可染色。我们可以得出以下简单的结果。例： 为1-可着色的 Û 为一完全图。 为可着色的 Û 为部图。 为可着色的 Þ 为可着色的（k<=j）最简单的连通图是圈，并且其它的图都可以由一个圈通过不断添加路而得到。图的任意两个顶点之间的最大距离，称为是图的直径，记作。如果图是一个边数为的非平凡连通图，则有。若把图的一个顶点染色看作是一个映射，并令它的任意两个相邻的点和都满足。我们称里的颜色为可用颜色，并且主要研究的是的基数。通常，我们都会去试着去找出一个最小的整数，使得有一个染色，即一个顶点染色，这个就成为图的顶点所需的色数，表示作。若，我们就把图称作色的；如果，则称图为可染色的。若把图的一个边染色看作是一个映射，并令它的任意两条相邻的边和，满足。边染色称为图的一个边染色，所使用的最小整数称为的边色数，也成为色指数，记做。2.2 彩虹连通基本知识Chartrand，Johns等人首次提出了图的彩虹连通性的概念。如果一个边染色图的任意两个不同顶点之间有一条边染不同染色的路径相连，那么就称它是彩虹连通的。彩虹边连通数就是一个连通图使它构成彩虹边连通所需要的最小的颜色数，称为记做。Krivelevich和Yuster提出了彩虹点联通的概念。一个点染色图的任意两点之间有一条内部顶点染不同颜色的路相连，则称它是彩虹点连通的。彩虹点连通数就是一个连通图它构成彩虹点连通图所需的最少的颜色数，记做。一个简单的发现是如果一个图有个顶点，则有；当且仅当它是一个完全图时有。注意到，当图直径为1和2时，它们相等。对于彩虹边连通和彩虹点联通，一些例子表明它们的彩虹连通路并不相同。在某些情况下可以比要小得多。例如，而。另一方面，在某些其他情况下，可以比小很多。取个顶点不相交的三角形，并给它们中的每一个指定一个顶点，在指定点上添加一个完全图。此图有个切点，因此。事实上，的着色只要求每个切点有不同的颜色。另一方面，不难看出，。只要给条边染色，比如说，颜色1和三角形的其它边的颜色2,3,4。这些例子表明彩虹边染色的证明与彩虹点染色的不同。由于自然组合的概念，彩虹边连通和彩虹点连通吸引了许多学者的兴趣。除了一些相关的定理，彩虹连通性也已经应用到了一些网络问题中。事实上，这个新概念形成于政府机构之间的信息传递。假设我们要在蜂窝网络的两个顶点之间传递信息，每个连接在网络上都会有不同的渠道。我们不得不采用路径最少的渠道，彩虹连通性就可以解决这个问题。定理1 对于一个顶点数的圈有令是图的一种彩虹染色。对的任何两个顶点和，中的一条彩虹测地线是一条长度为的彩虹路，则图称为强彩虹连通。如果对中的每对不同顶点和都存在一条彩虹测地线。这种情况下，染色称为的强彩虹染色。类似的我们定义连通图的强彩虹连通数是使图强彩虹连通所需要的最少的颜色数，记作。显然有：，这里和分别表示图的直径和边数。同样的，连通图的强彩虹点连通数是使图强彩虹点连通所需要的最少的颜色数，记作。彩虹顶点连通数，强彩虹顶点连通数（简单有限无向图），对于任意非平凡连通图有。对于一个阶连通图，给出的上下界，其中彩虹连通数，强彩虹连通数，对于任意非平凡连通图有。定理2.1 令是一个阶的非平凡连通图，则有：（1） 当且仅当是一个完全图；（2） 当且仅当。如果H是非平凡连通图的一个联通生成子图，那么，无单调性。引理2.1 令，是连通图的两个顶点，如果距离，那么不存在包含和作为内部定点的测地线。定理2.2 令是一个阶（）的连通图，那么，则这个界是精确的。定理2.3（1）当且仅当是一个完全图；（2）当且仅当；（3）当且仅当是一条n阶的路。引理2.2令是一个阶（）的连通图，如果不只有一条路，那么有。定理2.4对于每对整数，存在一个连通图使得。定理2.5 一个有个顶点的连通图有。定理2.5的证明定理1.5的证明还需要我们找到一个相对较小的2阶点集。然而，我们需要从它的额外的重要要求。我们所说的2阶点集k-强如果每一个并非由它支配的顶点有至少存在这是由它支配相邻的。引理2.3 若是具有个顶点和最小度的图形，则有二阶点集，其大小至多为。证明：初始化，然后只要，取一个顶点在的最小度至少为，将它添加到并通过删除和它相邻点集更新。观察到，当过程已经停止，其余的每个顶点已经失去了超过的度，因此有超过的与它相邻在被删除的顶点集合中。显然，这个过程持续了至多为步。显然注意到，但很重要的事实是：添加顶点到一个2阶点集不降低它的度。引理2.4 若是有最小度的连通图，然后它有一个连通的生成子图最小度为并有少于条边。证明:删除从中度数大于的边连接的两个顶点，只要不是任何我们以最小度得到一个子图和小于的边。这个生成子图的每个连接的部分都有至少有个顶点。因此，通过加最多条边，我们可以使他联通。定理2.5的证明：定理的语句在是不准确的，所以我们假定。假设是有个顶点和最小为的连通图。由引理2.4，我们可以假设有小于条边。我们用引理2.3构建一个集合是一个强2阶点集，大小。由引理2.4，我们最多只能添加的顶点和得到这么一个连接和也是一个强2阶点集。观察。令和考虑分区，其中为直接支配的顶点集和是不被支配的点集。由于是强，每个具有至少个相邻的点在中。我们进一步把分成2份和，其中是那些在中至少有个相邻的点。请注意，否则将有至少条边，与我们的假设矛盾。 我们也把L划分成两个部分和，其中是那些具有在中至少一个邻点的顶点。我们现在已经准备好着色方案。的顶点各自被染上不同的颜色。的顶点只要用到五种新的颜色，所以的每个顶点随机的和独立的从中所有其它的顶点中来选择它颜色。的顶点不被染色。以上使用的颜色的总数不超过。3 生活中的一些实际问题3.1 图着色问题的应用选课问题类似于图的边染色的问题，生活中的许多问题都可以建立模型为图的顶点着色问题来处理。例如课程安排问题。课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：几何学(G),线性代数(LA),高等微积分(AC),近世代数(MA),图论(GT)和统计学(S)。现有10名学生选修了这些课程(如下所示)。依据这些信息，使这些课程的开设所需要的最少时间段数得以确定，使得学生不会发生选课冲突。(学生用Ai表示）A1: LA, S ; A2: MA, LA, G ; A3: MA, G, LA;A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC;A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA;A10：GT，S。建立如下图所示的模型，把课程看作为图的顶点，两顶点之间的连线当且仅当有某个学生同时选了这两门课程。图 2如果我们用相同的颜色给同一时段进行的课程顶点染色，那么，问题转化为在状态图中求所谓的点色数问题。3.2 储藏问题一家公司制造种化学制品，其中某些制品是互不相容的，如果它们互相接触，则会引起爆炸，作为一种预防措施，公司希望把它的仓库分为间隔，以便把不相容的化学制品储藏在不同的间隔里，试问：这个仓库至少应该分成几个间隔？问题处理：构造一个图，其顶点集是两个顶点和相连当且仅党化学制品和互不相容，则仓库的最小间隔数即为的顶点数。4 彩虹染色方面的著名定理4.1四色与五色定理4.1.1 四色定理如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不相同；另一个通俗的说法是：每个地图都可以用少于四种的颜色来染色，而且没有两个邻接区域的颜色相同。邻接的两个区域指的是它们有一段公共的边界，而不仅仅是一个公共的交点。 1852年，刚毕业于伦敦大学的格斯里(18311899)发现：给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。当这个定理被提出后，很多科学家都希望能对此进行证明，但都没有成功。也有一些证明当时被确立后来又被推翻，经过了各种专家学者的一个多世纪的研究和证明，直到1976年才由两位美国数学家通过电子计算机得以完全的证明。但这个证明一直受到一些数学家的质疑，因为直到现在都没有数学家不借助计算机能够证明。4.1.2五色定理把一个平面分成若干的区域，给这些区域进行染色，并使任意相邻的区域染上不同的染色，满足这些条件所需的颜色数最多为五种。五色定理稍弱于比四色定理，但是它证明起来就容易多了。1879年，阿尔弗雷德·布雷·肯普给出了四色定理的一个证明方法，被当时的人们所接受，但11年后，珀西·约翰·希伍德却发现了这个证明中存在了一些错误，他对肯普的证明加以修改，就得到了现在的五色定理。 我们对图的顶点作数学归纳证明。当时，结论显然。设时，结论成立。考虑的平面图。因是平面图，所以。设，令。由归纳假设，是可用5种颜色正常顶点染色的。设c是的5着色方案。 (1) 如果, 显然c可以扩充为的5正常顶点染色； (2) 如果, 分两种情况讨论。情形1 在c下，如果在与相邻接点中，至少有两个顶点着相同颜色，则容易知道，c可以扩充为的5正常顶点着色；情形2在c下，设在与的相邻接点中，5个顶点着了5种不同颜色。图 34.2 贪心（greedy）着色法 用色1，2，逐步（按某一顶点排序）对每个顶点进行正常着色，每次选用尽可能少的颜色进行着色。例如，对任意图，按任一顺序进行贪心着色，则每当尝试对某一顶点着色时，其邻集中至多出现种色，因此总可从种颜色中挑选一中着在上。整个着色过程至多用种颜色，故为可着色的。从而得到推论。显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图的一个着色为。按 的顺序任作一顶点排序（同一色集内随意排序），按此顺序进行贪心着色，显然恰好使用了种颜色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到一个较好的着色结果（如Brooks定理之证明）。5 特殊图类的彩虹点染色5.1广义图的彩虹点染色5.1.1广义图的介绍在讨论广义图之前，我们先来了解几个定义。首先是彩虹连通，如果一条路的边分别染不同的颜色，那么这条边染色路就是一条彩虹路。如果图中任意两个顶点之间是连通的，并且由条内部顶点不相交的彩虹路连通，那么边染色图就是彩虹连通的，其中。接下来，我们给出彩虹连通数的定义：若存在图的一个边染色，使用种颜色就能够使得图彩虹连通，其中是最小的整数，那么彩虹连通数为：。对于连通图的彩虹连通数，记作，即。本文的概念定义部分介绍了，一个图是连通的，当且仅当任意两个顶点之间是连通的，并且由条内部顶点不相交的路径连通。因此，前面定义的仅仅是针对连通图而言的。我们继续说明，对于，等人证明了，如果图的阶数为，那么，如果图是连通的，即，那么。等人证明了，如果图的最小度为，那么，并且证明了对于所有阶数为，最小度为的连通图都是适用的。因此，如果图是连通的，那么。另外，上文有说明图是连通的，即，可以采用改善后的界，即。首先，了解连通图：定理1 如果是一个连通图，顶点，那么。在情况中，如果图是一个连通串并联图是一个简单图，从三个顶点开始，反复运用一个操作序列，这个序列是一个分支，由一条边变换成双条边，反复增加分支边。那么这样的连通图就是一个著名的亚族。证明定理，我们是通过先证明一个强有力的定理的结论，然后间接证明定理。定理2如果是一个连通图，顶点，那么存在图的一个边染色，至多是种颜色满足以下结论： 对于任意两个顶点，这里存在两条不相交的彩虹路； 对于任意一个顶点，任意集合，且，这里两条彩虹路，只有顶点相同； 对于任意两个集合，且，这里的两条彩虹路不相交。对于而言，如果，那么其中的一条路径取自顶点。类似的，对于，如果和相交，那么一条适合的路径是一个点，这点在中。显然，定理是来自定理，所以先证明定理，证明之前先给出一个定理。定理3令是一个连通图。对于任意的顶点和任意集合，这里有从到的条路径，使得对于其中的任意两条路，仅仅只有一个共同顶点。定理，证明：首先定义图的一些子图，其中，。因为任意的连通图都含有一个顶点至少是的圈，于是令是图的一个顶点至少是的圈。现在，假设找到这样一些图，如果，那么集合，否则的话，这里存在一个顶点。根据定理3，发出路到，这里的每对路径仅仅汇集与，那些路是的一个细分。令是一些路的集合。重复这个过程，直到结束。对于每个，归纳证明了，存在一个的边染色，至多使用种颜色，使得定理中的到的性质成立，这里使用代替。那么，集合就意味着对于而言定理成立。接下来，先对每个定义一个边染色。显然，是一个圈，它是彩虹染色的。假设有一个边染色，颜色是，其中。通过附加一个细分的到得到图，其中条路径汇集于顶点。假设路径是，。对于的情况，可以假设。令，是路劲的另一个端点，其中。分别把的第一条边和最后一条边射入到和。情况：，。彩虹染色使用的颜色为。就而言，的染色使用颜色为，采用这样的染色方法，每种颜色至少出现过次。总的，使用了种新的颜色。情况：，。彩虹染色使用的颜色为。染使用的所有颜色数为。总的，使用了种新颜色。情况：。假设存在最大的整数，使得。对边进行染色，路径的第一条边和路径的最后一条边染色，路径的最后一条边和路径的第一条边染色。路径的最后一条边和路径（每一条长度为1）染色。的其余的边染不同的新的颜色。总的使用了种新的颜色。重复归纳，可以得到的一个染色，。归纳证明了，对于的染色满足所有的需求，。显然，对于，我们使用了种颜色，定理的到成立。现在，假设对于的染色，至多使用了种颜色，定理的到成立。对于情况和情况，因为，所以的总的使用颜色数至多是。对于情况，因为，所以的总的使用颜色数至多是：。最后，我们在情况到情况中验证，定理的到成立对于成立。对于归纳假设，如果。类似的，对于，；对于，。现在，对于证明了到成立。这就完成了定理的证明，因此定理也就成立了。完成了连通图的介绍，接下来考虑图是一个连通的串并联图：定理如果图是一个连通的串并联图，顶点，那么。我们可以知道，当时圈，有个顶点时，彩虹连通数。这是特殊情况，更为一般的情况是，图是一个广义图。定义广义图：令，它是的路径的集合，路径的长度，其中，并且路劲上的每对内部顶点时不相交的，而且都有两个相同的端点。如图4所示的就是一个有四条路径的广义图。图 4定理证明：首先定义一些子图，是一个圈。是从附加一条长度至少为的路径到得到的，用两个不同的顶点来辨别路径的末端点。和一定是一些路径的末端点，如果一些路径的末端点是路径的的内部顶点，那么路径一定包含了路径的两个端点。每个是一个连通串并联图。构造串并联图，设置，先确定一个圈，以顺时针旋转作为参考。对于定义一个方向和一个平面，以的外部为导向顺时针圈，且包含。而且，假设路径是以外部为导向，。如果增加的路径是以外部为导向，那么导向使得，任然在新的外部圈中。另外，如果，对于选择外部和导向使得是的末顶点。否则，删除直到第一个使得加入的在的外部。加入的和方向同上面方法一样。注意点，是加入到由造出的外部界，当加入的外部。因此，我们能够重复加入和重复导向，按照这样做法，对于达到一个外部和一个导向。最后，重复标签分别是。对于每个重复，直到。假设是的外部圈，使得。接下来，的边染色，种颜色。首先，是彩虹染色，使用了中颜色。假设是染色，使用了中颜色。加入到的外部。那么是染色的，使用了种颜色。因此，证明了，对于每个，是彩虹连通的。所以证明了定理。完成了连通串并联图，最后考虑广义图：定理5如果是一个广义图，顶点数为，那么定理证明：假设是条路径，是条路径的共同的端点。显然，时，图就是一个圈。因此，假设。首先，因为，如果给图染色，少于种颜色，那么对于某些顶点，在中存在唯一的路径不是彩虹路。但是在中，有唯一的一对不相交的路，并且是其中的一条路径。因此，。接下来，对染色。路径的边染色映射到端点和，分别染色和，其中。下一步，对别的边染不同的颜色。那么对于使用了种颜色，并且这种染色是一个彩虹连通的，其中。因此，。5.1.2广义图的彩虹顶点连通性建立一个广义图，它由条边连成，如下图所示。其中t为图所包含的边数，为它所有的顶点数，为每条边上的顶点数不包含两个公共的顶点。图 5现在我们来讨论一下广义图的彩虹顶点连通性。讨论的过程主要分为几个步骤来研究，首先来由两条边所围成的一个圈来讨论，为一个圈时它的彩虹点连通数有上界，设彩虹顶点连通所使用的颜色数为S，即，染色情况如下图所示：图 6然后在增加一条边来看，令彩虹顶点连通所使用的颜色数为S，当为偶数时取中间的两个顶点染上所用过的颜色，其余点分别进行染色；当为奇数时取中间的一个点染所使用的颜色，其余点分别进行染色，如下图所示图 7从而有的彩虹点连通数，按照这个方法对图的剩下的边进行研究，最后得出图的彩虹顶点连通数的一个上界：。5.2一类特殊的图类的彩虹点连通性的研究5.2.1图类的介绍接下来我们再来研究一类特殊的图形，是由一个由n个顶点的圈为基础，把圈上相对的顶点依次相连，构成一类图，相连的边的数量记为t。我们把这类图分为两种情况去研究，第一种为圈上的顶点为偶数，第二种圈上的顶点为奇数，奇数顶点时圈上总会有一个顶点是独立的，不与其他点相连的。5.2.2彩虹点连通性的研究下面我们先来讨论一下圈上顶点数为偶数时的情况，我们先以顶点数n为10为例，如下图：图 8然后分别给每幅图染色，不加边时染5色，加一条染4色，加两条染4色，加三条染3色，如下图：图 9可以看出，随着连接边数的增加彩虹连通数在逐渐的减小，我们接下来继续观察，加四条边时染3色，加五条边时染2色，如下图：图 10由上所给出的图形可以看出，在顶点连线增加的过程中彩虹顶点连通数不是严格递减的。通过对大量图形的研究与总结这类图形的的彩虹点连通数随着所连接的边数的增多而减少。5.3轮图的彩虹点连通性5.3.1轮图以及它的推广图的介绍我们再来研究一类图轮图，轮图可简单定义为，因为加入到中，产生了一个新的顶点与的每个顶点相连。接下来我们对轮图进一步说明，首先定义圈，边为。对于的圈，在圈中加入一个顶点，使得与圈上的每个顶点连接，那么这样的图就称作轮图。轮图是一个有个内部顶点，个叶子顶点，且被一个圈连接的图，根据Halin图的定义，可知轮图是一个特殊的图，最小度。下面我们先介绍一下Halin图的定义：在平面上嵌入一棵树，的每个内部顶点的度数至少为，并且至少有一个内部顶点。再做一个圈连接的所有叶子顶点，即圈上的顶点时由的所有叶子顶点组成。这样的得到的图被称作图，树叫做特征树，圈叫做伴随圈。我们已经在前面说明了圈的彩虹点连通数，接下来也将给出轮图的彩虹连通数，并证明。当然我们所研究的不仅仅是这样的轮图，而是圈中加入了个顶点的轮图，并且给出轮图的彩虹连通数和证明。新轮图是一个有个内部顶点，但个顶点之间没有边直接相连接，有个叶子顶点，且被一个圈连接的图，根据图的定义，可知新轮图并不是一个特殊的图，但是它的特殊性值得研究，那么新轮图的最小度。研究5.3.2 轮图以及它的推广图彩虹连通性的研究在推导新轮图的彩虹连通数之前，让我们先来看看轮图的彩虹点连通数。经过图例的观察内部顶点为一个时的轮图，发现当时轮图是一个完全图，；当时，无论怎样的去增加圈上的顶点它的始终不变，。然后我们也发现增加轮图的内部顶点，它的也是不变的，如图所示：图 11下面我们来研究一下轮图的推广图，在圈的外部在增加一个圈，两个圈上的顶点都与内部顶点相连，称为二层轮图。它所有的的顶点集为，它所有的边的集合为，。如下图所示：图 12研究这类图形，我们分为几个方面来讨论，当时：（1） 我们先来研究顶点和圈的连线，它们之间并没有内部顶点虹顶点，所以彩虹连通数；（2） 在看与的连线，他们的连线上只有一个内部顶点，所以也只需要一种颜色足以使它们彩虹顶点连通，则；（3） 要使自己内部顶点彩虹连通，则需要借助顶点，这样就构成了一个轮图，所以它也只需一种颜色即可满足彩虹顶点连通；（4） 要使自己内部顶点彩虹连通，可如图所示，它所需的最小颜色数是4，则有；图 13（5） 使圈与上的点彩虹连通，最多需要3种颜色，所以它的彩虹顶点连通数有。综上所述，这类二层轮图的彩虹顶点连通数有一个上界。上述研究只是一个大概的范围，下面我们来研究一下，当圈上的点数为具体数值时的情况。我们先来看一下时，显然；当时，；当时，；图 14当时，。图 15综上所述，有。6 结束语 在本文中我们主要谈到了图论中的一个并不为大家所熟知的一个领域，其主要讨论了彩虹连通性相关的一些相关的知识，让大家对这些知识有一些初步的了解，同时也对彩虹连通性的研究在一些实际生活中的应用有了一些认识。我所研究的这些图形只是一些简单的图形，研究起来相对容易，对于一些复杂的图形在研究时需要注意很多的条件，所以在选择图形时我只选取了一些简单图以便研究。我所研究的第一个图类是广义图，这类图形的变化形式很多，要考虑的条件也有很多我在文章中所求出的彩虹连通数是有意义的但是否为最佳的还有待考证。第二种图类是在圈的基础上的一种推广形式，这种图形也还有一些更复杂的变换形式，我在文章中只解出了其中的一种形式。第三种图类是在轮图的基础上进行的推广，这类图也还可以有很多种变换，我所研究的都是这些图雷中相对简单的，所以还需要更多时间和努力才能把这些图类研究透彻。最后由于我个人能力和知识水平的有限，还有题目比较新颖所能参阅的资料不足，所以文章中可以会有一些错误或者不准确的地方，还希望看过这篇文章的读者能够提出一些问题或改进意见，让这些研究能更接近于正确，而我也能从中更好地学习这些知识。参考文献1 王维凡,李超.非负特征图的线性染色M中国科学A 辑,2008,38:1321-1334.2 黄丹君,王维凡.高度平面的邻点可区别全染色J中国科学:数学,2012,42:151-164.3 万慧敏,史小艺,王艳丽.几种特殊图的边染色J五邑大学学报,2012.4 李学良,董英九.图的彩虹连通数与最小度和J中国科学,数学,2013年01期:8-15.5王淑栋,李崇明,许进,庞善臣J若干图类的邻强边染色,数学研究.2002(04)412-417.6 马德,刘林忠,张忠辅.树的邻强边染色J数学研究与评论.2000(02):299-305.7 林全文,轮图和多轮图的生成树的计数J数学的实践与认识.2002(03)450-454.8 Rehinhard Diestel著,于青林,王涛,王光辉,图论第四版(M)高等教育出版社,2012,108-115.9 孙惠泉,图论及其应用M科学出版社,2004,100-108.10 Y.Caro，A.Lev，Y.Roditty，Z.Tuza，R. Yuster，On rainbow connection.JElectron J Combon 15（2008），R57.11 Chandran L, Das A, Rajendraprasad D, et al. Rainbow connection number andconnected dominating sets J Graph Theory, 2012, 71: 206-218.12 C. Nomikos, A. Pagourtzis and S. Zachos. Routing and path multicoloring.JInformation Processing Letters, 80(2001) 249-256.13 D. de Werra, Lausanne, Heuristics for graph coloring.JComputingSupplementum, 7(1990)191-208.14 I. Holyer. The NP-Completeness of edge-coloring. SIAM J. Computing, 10: 4(1981) 718-720.15.O.V. Borodin and A.V. Kostochka. List edge and list total colorings of multigraphs.JJournal of Combinatorial Theory, (Ser. B), 71(1997), 184-204.16 Xiao Zhou, H. Suzuki and T. Nishizeki. An NC parallel algorithm for edge-coloring series-parallel multigraphs.J Journal of Algorithms, 23(1997) 359-374.17 Krivelevich M, Yuster R. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J Graph Theory, 2010, 63: 185-19.