图的有界染色

《图的有界染色》由会员分享，可在线阅读，更多相关《图的有界染色（42页珍藏版）》请在金锄头文库上搜索。

1、山东大学 硕士学位论文 图的有界染色 姓名：战新刚 申请学位级别：硕士 专业：运筹学与控制论 指导教师：刘桂真 20040330 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：照蟊旦1 2 日期：垄! 垒：主：丕Q 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子

2、版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：烂0 藓丑I L 导师签名： 期：丕! 熟i ：主皇 山东大学硕士学位论文 图的有界染色 战新刚 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 本文考虑的图均为有限无向简单图对于一个图G ，我们用1 7 ( G ) 和E ( G ) 分别表示它的顶点集和边集对任意的f V ( G ) ，我们用d e g ( z ) 表示。在G 中的次数，a ( G ) 表

3、示图G 的最大独立集的顶点数目图G 的一个k 一顶点染色 是指对G 的顶点分配k 种颜色，1 ，2 ，k ；这个顶点染色是正常的是指任何两 个相邻的顶点都分配不同的颜色如果G 有一个正常的k - 顶点染色，就称G 是 k 顶点可染的图G 的顶点染色数x ( G ) 是使得G 能够k - 顶点可染的最小的 数k 图G 的k 有界染色是图G 的一个最多有k 个顶点染同一种颜色的顶点 染色。图G 的“有界染色数X k ( G ) 是指对G 进行k 有界染色所用的最少颜色 数本文中没有给出的定义可见f 2 】 图的染色问题是图论中研究的主要阿题之一图的染色问题一般可分为顶点 染色和边染色两类不同的染色

4、，本文我们要考虑的是图的有界顶点染色问题有 界染色阿题是对顶点染色问题的一个自然的限制，即对同一颜色的顶点数目的限 制，在实际应用中，这可以是对可用的房间数，机器数或其它资源的数目限制 图的顶点染色问题的一个应用是作为时闯表安排问题的一个模型( 可参阅 1 7 1 ) ， 在这个模型中，顶点代表要安排的任务，两个顶点是相邻的表示它们代表的任务 不重复，对此问题的一个自然的限制是在同- B e 间内不允许安排太多的任务，那 么加上这个限制的时间表安排问题就可以甩有界染色这个模型来表示。 H a n s e n ，H e r t z 和K u p l i n s k y 研究了图的有界染色数的上界

5、和下界，给出了下 面的定理： 定理2 1 1 【3 】设G 是有n 个顶点的图，图G 的染色数为x ( G ) ，k 有界染 色数为妯( G ) ，那么就有 一删) 鲰c 哪螂，+ 【竿 并且上界和下界都是紧的。 山东大学硕士学位论文 对于外平面图我们得到了以下推论 推论2 1 9 设G 是有n 个顶点的外平面图，图G 的染色数为x ( G ) ，女一有 界染色数为x ( G ) ，则 吲，x ( G ) ) 鲰( G 坯旧+ 2 同时，H a n s e n ，H e r t z 和K u p l i n s k y 证明了如果是固定的。那么就有一个 多项式时间算法得到二分图G 的一个有界染

6、色数为x k ( C ) 的一有界染色，并且 提出一个猜想 猜想2 1 2 ( 3 j 如果作为输入的数值，那么确定二分图的有界染色数是 p 完全问题 B o d l a e n d e r 和J a n s e a 在 4 】中证明了，如果k 作为输入，那么判断二分图是 否能用三种颜色一有界染色是P 完全问题，这就证明了猜想1 2 是正确的 M a r kJ a r v i s 和B i n gZ h o u 在【5 】中证明了即使k 作为输入。也能在多项式时 间内确定树的k 一有界染色数并给出了一个有效的有界染色方法，这是目前已知 的最好结果 显然树是外平面图的一种，本文考虑结构比树复杂的

7、外平面图的情况，得到 一些新的结果。本文第一章简单介绍了图的有界染色问题的已有的主要结果； 第二章给出了n 个顶点的不含奇圈的外平面图能用f n 七 种颜色k - 有界染色 的一些充分条件，我们引用了M a r kJ a r v i s 和B i n gZ h o u 在【5 】中的一个如下引理： 引理2 2 1 设T 是一个森林，j ，是丁的染两种不同颜色的顶点 集，则K 中度超过l 的顶点个数最多为嗽f I 。 利用上述引理，我们主要得到了以下结果 定理2 2 2 图G 是有n 个顶点的不含有奇圈的连通外平面图，设G 的两 个染不同颜色的顶点集分别为K 和K ，其中j K j = C 1

8、+ r 1 ，J | = o k + r 2 ， 0Sr l ，r 2 k ，I K I k ，那么x k ( C ) = 礼州。 定理2 2 4 图G 是n 个顶点的不含奇圈的连通外平面图，设G 的两个染不 2 山东大学硕士学位论文 同颜色的顶点集为K ，K ，其中I H I = c l k + r l ，l K l = r 2 ，0 t 1 ，r 。 k ，l K I = c a k + r 3 r 3 ，并且 0 r ； 七，1 1 j l = c a k + r a r 3 ，并且0 冬r 女t h e nx k ( G ) = f n k T h e o r e m2 2 4 L e

9、 tGb eac o n n e c t e do u t e r p l a n a rg r a p hw i t hn v e r t i c e sa n d n oo d d c y c l e ，Ua n d K b e t w oc o l o rc l a s s e ss u c h t h a t 川= e l k + r t ，I K I = c 2 k + r 2 w l l e r e0Sr l ，r 2 七a n d 【I 引= c a k + 7 3 r 3w h e r e0Sn 七a n di l j l = c 3 k + n r 3w h e r e0 r

10、 k ，那么x k ( G ) = f n k 1 。 证明我们对r l 和，o 的不同情况进行讨论 情况1r l + r 2 此时，显然f n k 1 = c l + c 2 + 2 ，我们分别对顶点集K 和I 利用G r e e d y C o l o r i n g 算法进行 一有界染色，即用c - 4 - 1 种颜包给I _ 1 中的顶点- 有界染色，用c 2 + 1 种颜色给l 中的顶点 一有界染色因此，用的总的颜色数目为c l + c 2 + 2 ，所 以从( G ) = f n 纠 情况2r l4 - r 2Sk 此时，显然胁卅= C l + C 2 + 1 自于r c + r

11、2Sk ，所以，r I ，r 2e e l , 有 一个小于或等于k 2 ，不妨设为r 1 因为n 纠是) ( ( G ) 的一个下界，所以， 我们只需构造一个k 一有界染色数为f n k 的染色即可，过程如下： 1 重复下面的操作，直到H 中有r - 个顶点被染色： 取出l j 中度最小的顶点z ，将z 染为颜色1 ，从G 中删掉z 和其邻点。 2 将 j 中剩下的顶点中任意1 “ 2 个顶点染颜色1 3 分别对H ，K 中未染色的顶点利用G r e e d yC o l o r i n g 算法进行k 一有界 染色。 以下我们证明第2 步的可行性，即证明第1 步执行完之后，K 中至少剩下

12、r 2 个顶点没有被删掉。如果每次执行第1 步时，I ，j 中都有度不超过l 的顶点， 那么显然至多删掉K 中的r - 个顶点，这时中剩下的顶点个数满足要求。否 则，我们假设G 中每个顶点的度都大于等于2 我们可以分以下两种情况考虑 ( ，) 图G 是2 连通的外平面图，即图G 没有割点，由外平面图的定义可知， 每两个内面只有一条公共边由定理2 18 可知，2 i 连通的外平面图的拟对偶图 1 4 山东大学硕士学位论文 是一裸树，又每棵树至少有两个顶点度为1 ，所以，2 连通平面图至少有两个 悬挂内面由定义2 1 5 可知，悬挂内面只有一条边和其他内面相邻，即只有两 个点度大于2 ，其他的点必

13、然位于外面上，且度为2 ，又因为图G 不含奇圈， 所以每个面的边界上的点必然都构成偶圈 显然，最小的偶圈是4 圈，所以每个悬挂内面上至少有两个顶点度为2 ，并 且度为2 的顶点个数必然为偶数。不妨设为2 m ，其中必有m 个顶点属于K 。 于是去掉一个H 中的度为2 的顶点和其邻点时最多去掉两个K 中的顶点 因为图G 是2 一连通的外平面图，所以由定理2 1 8 可知，图G 的拟对偶图 是树，而在树了1 G 中删掉一个叶子( 度为l 的顶点) 后，剩下的图依然还是 树，所以我们只要对的一个叶子f 所对应的图G 的悬挂内面，l 执行第1 步操 作，这样每次删除的K 中的顶点个数至多为删除的K 中

14、顶点个数的2 倍将 上的K 中度不超过2 的顶点删除以后。再从T G f ) 中找一个新的叶子，再对它 对应的图G ，l ( 不去掉 与另一内面的边界) 中的悬挂内面执行第1 步操作， 显然这个过程可以一直进行下去，直到有r t 个U 中的顶点被染色此时删掉的 K 中的顶点个数至多为2 r 1 个因为r l k 2 ，所以2 r l 七，于是执行完第1 步时，K 中剩下的顶点个数设为I “I ，应满足 I K I = c 2 k + r 2 2 r l ( c 2 一1 ) k + r 2 r 2 ， 从而，第2 步可以执行 ( ，) 图G 含有割点。此时。由图G 是连通的外平面图可知，图G

15、的2 一连 通部分之间或者有公共点( 即割点) 或者有路相连，我们可以先对图G 的2 连 通部分执行第1 步操作，如果当图G 的所有的2 一连通部分都执行完第1 步操作 时，u 中被染色的顶点个数小于r - ，那么图G 剩下的部分必然为森林 由引理2 2 1 可知，在继续执行第l 步操作时，K 中至少有一个度不超过l 的顶点被染色，因此，删除的与其相邻的K 中的顶点个数不超过l ，因此，执行 完第1 步时，删掉的K 中的顶点个数小于2 r 。个。从而。第2 步可以执行 综上所述，第2 步操作总是可以执行的在执行第3 步时，H ，K 中已 经染色的顶点个数分别为r - 和r 2 ，所以，K ，K

16、 中未染色顶点个数分别为 c t k 和c 2 k ，从而，分别对H 。K 中未染色的顶点利用G r e e d yC o l o r i n g 算 法进行k - 有界染色用的颜色数目分别为c t 和C 2 从而，总共用的颜色数日为 c l + C 2 + 1 = n 七 ，即X k ( G ) = n 女1 ，证毕 从情况1 中，我们可以知道，对于外平面图G 的两个染不同颜色的顶点集 H = C 1 k + r l 和K = c 2 k + r 2 来说，只要r l + r 2 k ，那么就有f n 明= c l + c 2 + 2 ， 】5 山东大学硕士学位论文 因此，我们只要用n + 1 种颜色给M 中的顶点七- 有界染色，用c 2 + 1 种颜色给 K 中的顶点k 一有界染