特殊图类的彩虹边染色毕业论文(编辑修改稿)

特殊图类的彩虹边染色毕业论文(编辑修改稿)内容摘要：

颜色。 路径的中间部分的边和边 0e 使用 H中已经使用过的任意一种颜色进行染色。 路径的前部分 2 1ts 条边染色是全部不相同的，路径的后部分 2 1ts 条边中相同序号的颜色是重复的。 这就证明了H 是彩虹连通的。 于是，我们有： 515 )1(32 151532 1)()(    tshtshtsHrcHrc 这就和 H 的极大性矛盾了。 因此，我们只要假设 21  ts。 现在，我们已经证明了 3nh。 如果 3nh ，那么 5 )1(32515 )3(32)()(  nhHrcGrc ； XIV 如果 2nh ，那么 5 )1(32515 )2(32)()(  nhHrcGrc ； 如果 1nh ，那么 5 )1(31515 )1(31)()(  nhHrcGrc。 综上所述，很容易推出： 5 )1(3)(  nGrc。 说明 )( xGrc 是有意义的： 上面我们已经按照定义的染色方法推出了，度为 3 ，层为 3k ，顶点数为 n的 Halin 图的彩虹连通数 423)( 2  kkGrc ，然后，我们又对 3 连通图的彩虹连通数的上界进行的改善，得到了一个更好的上界，即 5 )1(3)(  nGrc。 这里的 n 指的是 3 连通图中的顶点数，于是，我们可以计算下图 xG 中的顶点数，即 223  kn ， k 是层数。 这样， )( xGrc 就关于层数 k 的函数，423)( 2  kkGrc ，而 )(Grc 也可变换为有关层数 k 的函数， 5 329)(  xGrc。 做一个简单的 计算，可以得到： 5 329)(423)( 2   xkx GrcGrc ，当 Nkk  ,3 时。 第二节 特殊图类， k 个内部顶点的轮图 前面对轮图做了大致介绍，这里需要做进一步说明。 首先定义圈1121 , vvvvvC nnn   ，其边为 1 iii ve ， ni1。 对于 3n 的圈，在圈中加入一个顶点 1K ，使得 1K 与圈上的每个顶点连接，那么这样的图 1KCn 就称作轮图 nW。 轮图 nW 是一个有 1个内部顶点 1K ， n 个叶子顶点，且被一个圈连接的图，根据 Halin 图的定义，可知轮图 nW 是一个特殊的 Halin 图，最小度 3。 在前面已经证明了圈 nC 的彩虹连通数  2)( nCrc n，接下来也将给出轮图 nW的彩虹连通数，并证明。 当然我们所研究的不仅仅是这样的轮图，而是圈中加入了 k 个顶点的轮图 kn KC ，并且给出轮图 knW 的彩虹连通数和证明。 新轮图 knW 是一个有 k 个内部顶点 kvvv , 21  ，但 k 个顶点之间没有边直接 XV 相连接，有 n 个叶子顶点，且被一个圈连接的图，根据 Halin 图的定义，可知新轮图 knW 并不是一个特殊的 Halin 图，但是它的特殊性值得研究，那么新轮图knW 的最小度 },2m in{ nk 。 在推导新轮图 knW 的彩虹连通数之前，让我们先来看看轮图 nW 的彩虹连通数，参考了文献 ]7[。 定理 .3 当 3n 时，轮图 nW 的彩虹连通数是： .73,642,31)(nnnWrc n若若若 证明：假设有一个 n 阶的圈 1121 ,: vvvvvC nnn  ，还有一个顶点 K 连接 圈nC 的每个顶点构成的图称为轮图 nW。 首先考虑，当 3n 时， 43 KW。 这时的轮图是一个完全图，因此 1)( 3 Wrc。 再考虑，当 64 n 时，轮图 nW 不再是一个完全图，于是 2)( nWrc。 定义一个 2 边染色 }2,1{)(: nWEc 如下：如果 i 是奇数，则 1)( vvc i ， 1)( 1 iivvc ；如果 i 是偶数，则 2)( vvc i ， 2)( 1 iivvc。 可以验证这样的 一个边染色就是一个彩虹染色，因此 2)( nWrc。 最后考虑，当 7n 时。 定义一个 3 边染色 }3,2,1{)(: nWEc 如下：如果 i 是奇数，则 1)( vvc i ；如果 i 是偶数，则 2)( vvc i ；对于每个 )( nCEe ，有 3)( ec。 可以验证这样的一个边染色就是一个彩虹边染色，于是 3)( nWrc。 接下来，我们证明 3)( nWrc。 因为 7n 的 nW 不是一个完全图，于是2)( nWrc。 现在，做一个相反的假设， 2)( nWrc ，同样定义轮图 nW 的一个彩虹 2 染色 c ，并假设 1)( 1  vvc。 对于每个 i ， 24  ni ， ivvv ,1 是 nW 中的唯一的长度为 2 的 ivv1 路，所以，对于 24  ni ， 2)(  vvc i。 由于 2)( 4 vvc ，于是 1)( vvc n。 这就使得 2)( 3 vvc ，反过来使得 1)( 1 vvc n。 类似的， 1)( 1 vvc n XVI 使得 2)( 2 vvc。 因为 2)( 2 vvc 和 2)( 5 vvc ，从而在图 nW 中路径 52 vv 不是一条彩虹路，这就产生了矛盾。 于是 2)( nWrc。 因此综上， 3)( nWrc。 考虑新轮图 knW ， 一个 n 阶的圈 1121 , vvvvvC nnn   ，还有 k 个顶点kuuu , 21 连接圈 nC 的每个顶点，且这 k 个顶点之间没有边直接相连，这样构成的图就是新轮图 knW。 对新轮图 knW 进行染色，因为 k 个内部顶点 kuuu , 21 之间没有直接的边连接，为了确保内部顶点之间至少有一条彩虹路连接，所以先考虑 k 个内部顶点之间的彩虹路。 为了叙述简洁，给出一个 88W 的新轮图，如图 5 所示，圈 8C ，并有 8 的内部顶点 821 , uuu 。 为了便于观看，只选取了圈 8C 上的一个顶点 v 与内部 8 的顶点相连，同时省略了 8 个内部顶点与圈 8C 上别的顶点之间的连接边。 可以看出， 8 个内部顶点之间存在一条最短的路 ji KvK  ， }8,2,1{, ji 且ji ，于是决定将此条路染色成彩虹路，因此边分别染 色，色，色， 821 vK i ，8,2,1 i ，这样的染色方法确保了 8 个内部顶点之间的最短路径 ji KvK  是一条彩虹路。 至于 8 个内部顶点与圈 8C 上别的顶点之间相连边的颜色，也完全可以从 8 种颜色中取出，且远远满足染色需要。 类似的，对于 k 个内部顶点，要保证 k个内部顶点中，任意两个顶点之间有一条彩虹路相连，则需要的颜色数为 k。 XVII 图 5 88W 的新轮图 接下来结合圈 nC 考虑新轮图 knW 是彩虹连通的，可分三类情况进行讨论： 情况 1：圈 nC 上的顶点数与内部顶点 数 k 相同，即 kn。 按照上述的染色方法，能够保证任意两个内部顶点 ik 和 jk ， ji ，之间至少存在一条彩虹路相连，圈 上的边的染色需要的颜色完全可以取自 k 种颜色，并且不需要取全部的 k 种颜色就能使得在图 knW 中，任意两个顶点之间至少有一条彩虹路相连。 因此，彩虹连通数 kWrc kn  )(。 情况 2 ：圈 nC 上的顶点数少于内部顶点数 k 相同，即 kn。 同情况 1类似，圈 nC 上的边的染色需要的颜色完全可以取自 k 种颜色，且远远少于 k 种，就能够满足在图 knW 中，任意两个顶点之间至少有一条彩虹路相连， k 种颜色就已经使得图 knW 彩虹连通。 因此，彩虹连通数 kWrc kn  )(。 XVIII 情况 3 ：圈 nC 上的顶点数多余于内部顶点数 k ，即 kn。 断言这种情况下的彩虹连通数应是 kWrc kn  )( ，假设 kWrc kn  )( ，那么对于内部的 k 个顶点而言，会使得其中某些顶点之间没有彩虹路相连，比如说顶点 ik 和 jk ， ji ，},2,1{, kji  之间连接的边染了同种颜色，就没有彩虹路。 所以，假设不成立。 另一方面，要使图 knW 中，任意两个顶点之间至少有一条彩虹路相连， k 种颜 色就已经满足染色需求，不需要多一种的颜色。 这点可以从一个简单的例子进行说明。 为说明情况 3 ，给出一个 28W 的新轮图，如图 6 所示，圈 8C ，有 2 个内部顶点，所以彩虹连通数 2)( 28 Wrc ，就是说这个图只需要 2 中颜色进行染色，就可以使得图 28W 中任意两个顶点之间至少有一条彩虹路相连，即图 28W 是彩虹连通的。 之前有说明 ，顶点数 8n 的轮图 8W 的彩虹连通数是 3)( 8 Wrc ，增加一个内部顶点以后，可以使得彩虹连通数变为 2)( 28 Wrc。 因此，研究这类的新轮图knW 是有一定意义的。 XIX 图 6 28W 的新轮图 对上述的讨论作补充说明： 情况 3 中的圈 nC 上的顶点数多余于内部顶点数 k 相同，即 kn ， n 只是相对k 而言，数量多，而不是远远大于 k。 比如说，圈 nC 中 500n ，而内部顶点数 2k ，像这样的 n 远远大于 k 的情况是不属于情况 3 中所说的范围，我们只是针对kn ，但是两者之间较为接近的情况进行的一个讨论。 因为 n 远远大于 k 的这种情况属于特例，某些情况下甚至找不到任何一种染色方法使得它彩虹连通，或者说它就不存在彩虹连通图。 那么这样的图类对于我们的研究没有任何的意义，所以就不是情况 3 所讨论的范围。 类似的，情况 2 中圈 nC 上的顶点数少于内部顶点数 k 相同，即 kn ，只是针对 n 和 k 相差并不是很大的情况。 比方说，圈 nC 中 3n ，而内部顶点数 500k ，按照本文的染色方法，就需要 500 种颜色才能使得图 5003W 彩虹连通，即500)( 5003 Wrc ，对于这类的图，虽然可以计算出彩虹连通数，但是失去了图的彩虹染色的意义，在实际的应用中，我们对于这样两方相差悬殊，必定会对少的一方做一些补充，否则投入成本过大，这也就失去了实际应用的意义。 综上所述，我们可以确定新轮图 knW 的彩虹连通数。 当 3n ， 2k 时，新轮图 knW 的彩虹连通数是： kWrc kn  )(。 第三节 特殊图类，广义  图的彩虹连通数 在讨论广义  图之前，我们先来了解几个定义。 这些定来自参考文献 ]18[。 首先是彩虹 k 连通，如果一条路的边分别染不同的颜色，那么这条边染色路就是一条彩虹路。 如果图 G 中任意两个顶点之间是连通的，并且由 k 条内部顶点不相交的彩虹路连通，那么边染色图 G 就是彩虹 k 连通的，其中 Nk。 接下来，我们给出彩虹 k 连通数 )(Grck 的定义：若存在图 G 的一个边染色，使用 t 种颜色就能够使得图 G 彩虹 k 连通，其中 t 是最小的整数，那么彩虹 k 连通数为：tGrck )(。 对于 1 连通图的彩虹连通数，记作 )(Grc ，即 )()( 1 GrcGrc 。 本文的概念定 义部分介绍了，一个图 G 是 k 连通的，当且仅当任意两个顶点之间是连通的，并且由 k 条内部顶点不相交的路径连通。 因此，前面定义的 )(Grck 仅仅是针对 k 连通图而言的。 XX 我们继续说明 )(Grck ，在参考文献 ]18[ 中，对于 1k ， Caro 等人证明了，如果图 G 的阶数为。