（运筹学与控制论专业论文）一些图的圆边染色.pdf

山东火学硕士学位论文 一些图的圆边染色 程志 山东大学数学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 本文考虑的图若无特殊声明均为简单图。一个简单图的k 可边染色是一个 从含k 种颜色的色集到图g 的边集合的映射，并且使得相邻两边染不同的颜 色。对于一个k 可边染色的图g 来说，最小的就是图g 的边色数。v i n c e 提出了图的圆染色的概念，图的圆边染色就是图的圆染色由点到边的推广。 图g 是一个图，正整数k ，d 满足2 d k ，那么图的( k ，d ) 边染色是指从颜 色集 0 ，l ，k l 】到图g 的边的映射c ，并且任意相邻的两边e 1 ，e 2 满 足d i c ( e 1 ) 一c ( e 2 ) l k d 图g 的圆边染色数砭( g ) 就是图g 含有( k ，d ) 边 染色中的k i d 比值的下界。即：砭( g ) = i n f k d ：g 含有一个( k ，d ) 边染色) 图的圆边染色的许多基本性质被h a c k m a n n 证明： 定理0 1 3 1 如果g 是一个含有q 条边的图，那么 砭( g ) = r a i n k d ：g 含有一个( k ，d ) 边染色且ksq ) 定理0 2 【3 】 如果g 是第一类图，那么砭( g ) = a ( g ) 如果g 是第二类图，那么a ( g ) 譬= f g ，检验图g 是 否含有( k 2 ，d 2 ) 染色，如果没有，砭( g ) = 争；如果含有( 后2 ，d 2 ) 染色，继续检 验( ，d 3 ) 染色，依次类推。本文根据以上算法来确定一些图的圆边染色。全 文共分四章，第一章介绍图论的一些基本概念，并给出图的染色理论的已有定 理证明及圆边染色的理论。第二章介绍解决圆边染色的算法。 第三章我们给出了顶点数小于7 的所有第二类图的圆边染色数。主要结论 有： 定理0 4 在顶点小于7 的所有第二类图中，其圆边染色数： x ：( g 。) = 3 ，x ：( g z ) = 兰，) ( ：( g 。) = 4 ，x o ( a t ) = 兰， x ：( g 5 ) = 5 ，x ：( g 6 ) = 4 ，x ：( g 7 ) = 5 ，x ：( g 8 ) = 5 定理0 5如果g 是一个c axc 3 的笛卡尔积图，那么其圆边色数为： x ：( g ) = x ( c ) = 5 第四章给出了一类链图凰的圆边染色数及其证明。 定理0 6定义风是如图4 ，具体定义如下： y ( 风) = 锄，玩，q ，盔，m t ，啦：i = l ，竹) u 口) e ( 风) = o t 玩，玩q ，q 也，也m ，仇t 啦， r t i a i ，玩m ，白m ，也啦+ 1 ：i = 1 ，n ) u 【u 0 1 】 其中a n + 1 = u 那么，砭( 巩) = 3 + i 1 关键词：图，图的圆染色，图的圆边染色，笛卡尔积图，边染色 山东大学硕士学位论文 t h eci r c u l a rc h r o m a t i ci n d e xo fs o m eg r a p h s c h e n g z h i s c h o o lo fm a t h & s y s s c i s h a n d o n gu n i v e r s i t y s h a n d o n gj i n a n 2 5 0 1 0 0 a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r es i m p l e 铲a p t l s ak - e d g ec o l o r i n go fa s i m p l eg r a p hgi sa na s s i g n m e n to fkc o l o r st ot h ee d g e so fg s u c ht h a ta d j a c e n t e d g e sa r ec o l o r e dd i f f e r e n t l y t h em i n i m u mn u m b e rkf o rw h i c hag r a p hg a d m i t s ak - e d g ec o l o r i n gi st h ec h r o m a t i ci n d e xx 7 ( g ) o fg i nt h i sp a p e rw ec o n s i d e r ar e f i n e m e n to ft h ec h r o m a t i ci n d e xw h i c hc o n t a i n sm o r ei n f o r m a t i o na b o u tt h e s t r u c t u r eo ft h eg r a p hg t h ec i r c u l a rc h r o m a t i ci n d e xi san a t u r a lg e n e r a l i z a t i o no ft h ec h r o m a t i c i n d e xo fag r a p h ，o b t a i n e db yc a r r y i n go v e rt h ed e f i n i t i o no ft h ec i r c u l a rc h r o m a t i c n u m b e r ，i n t r o d u c e db yv i n c e ，f r o mv e r t e xt oe d g ec o l o r i n g l e tgb eag r a p h a n dl e tk ，db ep o s i t i v ei n t e g e r ss u c ht h a t2 dsk t h e na ( k ，d ) - e d g ec o l o r i n g o fg r a p hi sa l la s s i g n m e n teo fc o l o r s ( o ，l ，k 一1 】t ot h ee d g e so fgs u c h t h a tf o ra n yt w oa d j a c e n te d g e se l ，e 2w eh a v ed i c ( e 1 ) 一c ( e 2 ) i 后一d t h e c i r c u l a rc h r o m a t i ci n d e x 砭( g ) o fgi sd e f i n e da st h ei n f i m u mo ft h er a t i oo f k df o rw h i c ht h e r ee x i s t sa ( k ，回一e d g ec o l o r i n go fg 砭( g ) = i n f k d ：gh a sa ( 七，d ) 一e d g ec o l o r i n g t h e o r e m0 1i fgi sag r a p ho nq e d g e st h e n x ：( g ) = m i n k d ：gh a s 口( k ，d ) 一e d 9 ec o l o r i n gw i t hk g ) t h e o r e m0 2i fgi sc l a s s1t h e n 砭( g ) = ( g ) i fgi sc l a s s2t h e n a ( g ) 砭( g ) a ( a ) + 1 t h e o r e m0 3i f gi sc l a s s2t h e ne i t h e r 砭( g ) = a ( a ) + 1o r v 山东大学硕士学位论文 ( g ) + 丽1 x ( g ) + o z 7 ( g ) 一1 口7 ( g ) w h e r e 乜7 ( g ) i st h ee d g ei n d e p e n d e n c en u m b e ro fg a l lt h ec i r c u l a rc h r o m a t i ci n d e xp r o b l e m so fg r a p h so fc l a s so n ea r es o l v e d ， b u ti t i st o od i f f i c u l tf o rt h eg r a p h so fc l a s st w o i nt h i sp a p e r ，w e 1 1t r yt og i v es o m er e s u l t sa b o u tt h ep r o p e r t i e so fs o m e 鲈a p h so fc l a s st w o t h ep a p e ri sd i v i d e di n t of o u rc h a p t e r s i nc h a p t e ro n e ，w ei n t r o d u c es o m e b a s i cc o n c e p t i o n so fg r a p ht h e o r y i nc h a p t e rt w o ，s o m eb a s i cp r o p e r t i e so ft h e c i r c u l a rc h r o m a t i ci n d e xo fg r a p h sa r ei n t r o d u c e d t h i st w o c h a p t e r sa r et h eb a s e o ff o l l o w i n gc h a p t e r s c h a p t e rt h r e eg i v e ss o m er e s u l t sa b o u tt h ec i r c u l a rc h r o m a t i ci n d e xo fa l l t h eg r a p h sw h o s ev e r t i c e s & r en om o r et h a n7 t h em a i nr e s u l t sa r et h ef o l l o w i n g p r o p e r t i e s t h e o r e m0 4 t h e r ea r e8g r a p l l so fc l a s s2w i t ht h ev e r t i c e sn om o r et h a n 7i nf i g1 t h ec i r c u l a rc h r o m a t i ci n d e xo ft h eg r a p h sa r ea sf o l l o w s ： 砭( g 1 ) = 3 ， x ：( g 2 ) = 百5 ， x ：( g 3 ) ：4 ， 砭( g 4 ) - i 9 ， x ：( g 5 ) = 5 ，砭( 瓯) = 4 ，x ：( 岛) = 5 ，x c ( g s ) = 5 t h e o r e m0 5gi sac a r t e s i a np r o d u c tg r a p hg c 3 ，t h e nt h ec i r c u l a r c h r o m a t i ci n d e xo fgi s x o ( c ) = x ( a ) = 5 i nt h ec h a p t e rf o u r ，w ew i l lg i v et h ec i r c u l a rc h r o m a t i ci n d e x o f 4 t h e o r e m0 5 g r a p h 风i sd e f i n e da sf o l l o w s ： y ( ) = a i ，玩，c i ，也，t i $ i ，啦：i = l ，n iu 口】 e ( 风) = 瓯6 t ，玩q ，c j c 反，也m t ，m i n i ，n i a i ，6 i m ，q 仡，也。件1 ：i = 1 ，礼) u v a l 】 一v 1 - 山东大学硕士学位论文 ! ! 竺= ! = = ! = = = = 竺! ! ! ! ! = ! = = = = = = = = = = = = = = = ：= = ：! = = = = = = = = = = = = = = = = = = ! = = = - w h e r e + 12 可 t h e nf o ra n yp o s i t i v ei n t e g e r 佗w eh a v e 砭( 巩) = 3 + 击 k e y w o r d s ：g r a p h ，t h ec i r c u l a rc h r o m a t i cn u m b e r ，t h ec i r c u l a rc h r o m a t i c i n d e x ，t h ec a r t e s i a np r o d u c tg r a p h ，c h r o m a t i ci n d e x - v 1 1 - 山东大学硕士学位论文 v ( g ) e ( g ) 5 ( g ) a ( g ) 如( 秒) g 吲 g s g 一口 x 7 ( g ) g o d 砭( g ) 符号说明 g 的顶点集合 g 的边集合 g 的最小度 g 的最大度 u 在图g 中的度 s 导出的g 的子图 y ( g ) s 的导出子图 y ( g ) ) 的导出子图 g 的边染色数 最大公约数 g 的圆边染色数 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：跹 日期：丝! 墨：7 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件 和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者虢靼导师虢避日 山东大学硕士学位论文 第一章前言 图论是一门应用十分广泛且内容非常丰富的数学分支，是近年来较为活跃 的数学分支之一。它起源很早，瑞士著名数学家欧拉( l e u l e r ) 在1 7 3 6 年解决 了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而促进了图论的 诞生和发展，成为了图论和拓扑学的创始人。2 0 世纪，图论的发展进入了黄金 时代，图论的应用渗透到许多其他学科领域如物理、化学、信息学、运筹学、 博弈论、计算机网络、社会学、语言学，以及集合论、矩阵论等。从2 0 世纪 5 0 年代始，计算机的迅速发展，也有力的促进了图论的飞跃发展。 图的染色理论是图论中的一个重要分支，在现实生活中有很多问题，例如 排序问题、工作分配问题、时间安排、无线电频率分配问题、卫星通讯、交通 控制等问题最终都可以归结为图的染色问题。染色按照点边的不同又分为点染 色和边染色。本文研究的主要是边染色中的圆边染色问题，利用前人总结方法 解决了另一种二类图的圆边染色性质。 本章第一节首先介绍一些在本文用到的图论的基本概念，第二节介绍图论 中点染色、圆染色、边染色，圆边染色问题，第三节介绍本文的主要结果。 1 1 基本概念 本文涉及到的图均为简单图。我们首先介绍一些常用的图论术语。我 们通常称二元集合g = g ( y ( g ) ，e ( g ) ) 为一个图，其中v ( v ) 毋，叫做 顶点集合，v ( g ) 的元素叫做图g 的顶点；e ( g ) 叫做边集合，e ( g ) 的元 素叫做图g 的边。当i y ( g ) i 十l e ( g ) l 0 0 时，图g 叫做有限图，否则称 为无限图。v ( g ) = 1 且e ( g ) = 0 的图我们称为平凡图，其他图为非平凡 图。对于图g 的两个顶点让和移，如果e = u 口e ( g ) ，则称缸和 相邻 接，u 和口互为邻点，且称u 和 是边e 的端点，u 和口分别与边e 相关联。 若图g 的边e 1 和e 2 有一个公共端点，则称边e 1 和e 2 相邻接。只与个顶点 相关联的边叫做环。对于一个图，如果它没有环也没有两条边连接同一对顶 点，则称该图为简单图。对于一个图g = g ( y ( g ) ，e ( g ) ) ，我们用d g ( 口) 表 示顶点”在g 中的度数。a ( g ) 和6 ( g ) 分别表示图g 的最大度和最小度。 对v ( g ) 的子集s ，用g s 表示从g 中删去顶点集合s 及其关联的边所得到 1 一 山东大学硕士学位论文 的子图。若s = f u ) ，则令g 一 = g 一如 _ 。对e ( g ) 的子集x ，用g x 表 示从g 中删去边集合x 所得的子图。若x = e ) ，则g 一 e ) 简记为g e 。 若存在v ( g ) 的两个不交子集x 、y ，使得v ( g ) = x u y ，且g 的所有边均 一个端点在x 内，另一个端点在y 内，则称g 为二部图【1 3 】。 g = ( ve ) 和h = ( v 7 ，e 7 ) 是两个图，如果y 7 y 和e 7 e ，则 称豆是g 的子图，记为h g 。如果日是g 的子图，并且v ( h ) = v ( g ) ， 则称日是g 的生成子图。如果日是g 的子图，其中v ( h ) = y ( a ) 和e ( g ) = e ( h ) 至少有一个不成立，就称日是g 的真子图。假设y 7 是v ( g ) 的一个 非空真子集，则以g y 表示从g 中删去y 7 内的所有顶点以及以及与这些 顶点相关联的边所得到的子图。若v 7 = 和 ，常把g 一和 简记为g v 。 用g v 7 1 表示g 一( y y ) 称为g 的由y 7 导出的子图。关于边子集也有类似 的定义。设e 7 是e ( g ) 的子集，以g e7 表示在g 中删去e 7 中所有的边所得 到的子图，而在g 中加上边集e ( e ne ( g ) = 咖) 内的所有边所得到的图记 为g + e 。同样用g e ( 或g + ，ge ( g ) ) 表示g 一1 e ) ( 或g + e ) ) 。 用a l e 7 1 表示以e 7 为边集，以e 7 内的边的端点为顶点的集合所构成的图，称 为g 的由e 7 导出的子图。 对于图中的每个顶点口，与口相邻接的边的个数称为u 的度，用p ( u ) ， 在本文中图的最大度均用( g ) 表示，简写为。如果图g 中所有顶点的度 数都相等，那么称图g 是一个正则图。图g = ( ve ) 是一个点边交替出现 的有限序列w = 伽e 1 1e 2v 2 一1e 讥，这里忱( 0 i k ) 是g 的顶 点，e t ( 0 i ) 是g 的边，满足e i 两个端点就是 i 一1 和协( 1 i 七) ，则 称是g 的一条从咖到魄的途径，简称( v o - - v k ) 途径。饥( 0 i 七一1 ) 称 为的内部顶点；k 称为途径形的长度；和讥分别称为彬的起点与终 点，或称为的端点。如果途径的边互不重复，则称这条途径为迹。如果一 条途径中的顶点也互不相同，则称这条途径为路，如果一条途径的起点和终点 相同，则称这条途径为闭途径。对于图g 中两个给定的顶点铭和 ，若g 中 存在( u 一口) 路则必定存在一条最短的m 一 ) 路岛，称r 是一条m 一口) 最 短路。r 的长度称为顶点和 的距离。g 的所有两点间距离最大者称g 的 直径。我们通常把起点及内部顶点互不相同的闭迹称为回路( 或圈) 。长度 为n 的圈记为g ，把长度为奇( 偶) 数的回路称为奇( 偶) 回路( 圈) 。 我们用( v 1 ，y 2 ，仇) 表示从顶点v l 依次经过忱，仇一1 到口( 惫) 的路： 若u 1 = 讥则表示一个圈。若是g 的一个k 正则支撑子图，则称为g 的 2 山东大学硕士学位论文 一个k 因子；g 能分解成k 因子并且这些k 因子两两边不交，则称g 可k 一因 子分解。 设图g和h，v ( a ) = u l ，u 2 ，) ，v ( h ) = v l ，v 2 ，) 【8 】。g 和h 的笛卡尔积g h 定义为： v ( gxh ) = 【i = ( 饥，吻) ，1 i n ，1 j 仇) ； e ( g h ) = ( ，w , k ) i 啦= u z 且( 吻，仇) e ( h ) 或= y k 且( 妣，让1 ) e ( g ) ) 1 2 图的染色理论 图的染色理论是图论的重要组成部分。图的染色问题的研究来源于著名的 四色猜想。四色猜想也许就是图论中最出名、最难解决的问题，对这个问题的 研究也就成为许多科学家研究的原始动力。所谓四色猜想就是在平面上任何一 张地图，总可以用至多四种颜色给每一个国家染色使得任何相邻国家的颜色是 不同的。1 8 5 2 年由g u t h r i e 兄弟在通信中提出了四色问题。小g u t h r i e 求教于 他的老师d em o r g a n 。m o r g a n 无法给予解决。1 8 7 8 年c z y l e y 在伦敦数学会上 宣布了这个问题，引起了数学界的广泛注意。但是在此后的一个多世纪中都没 有人解决这个问题。直到1 9 7 6 年美国的a p p e l 和h a k e n 借助于高速电子计算 机用了1 2 0 0 多个小时证明了四色猜想成立。然而给四色定理一个无需借助计 算机的理论证明仍然是一个未获解决的问题。 图的染色分为点染色和边染色。下面介绍一下图的点染色和边染色的定 义。 g 的一个正常k 顶点染色是指k 种颜色1 ，2 ，3 ，k 对于g 的各顶点的 一个分配，使得任意两个相邻的顶点分配以不同颜色。若图g 有一个正常k 顶 点染色，就称g 是七顶点可染色的。而g 的色数是指g 有正常k 顶点染色 的数k 的最小值，用x ( g ) 表示。我们通常把“正常k 顶点染色”简称为k 染 色，类似地，把“k 顶点可染色”简称为k 可染色。 g 的一个k 边正常染色是指七种颜色1 ，2 ，k ，对于g 的各边的一个分 配，使得相邻的两条边染以不同的颜色。若g 有k 边正常染色，则称g 是k 边 可染色的。g 的边色数是指g 为k 边可染色的最小值k ，记为x 7 ( g ) 。它有以 下性质： 3 一 山东大学硕士学位论文 定理1 1 二分图g = ( x ，y ；e ) 的边色数) ( 7 ( g ) = ( g ) 。 定理1 2 若g 是简单图，则a ( g ) sx 7 ( g ) ( g ) + l 。 若图g 满足x 7 ( g ) = a ( g ) ，则称g 为第一类图；若g 满足x 7 ( g ) = a ( g ) + l ，则称g 为第二类图。 下面介绍图的圆染色。 考虑设计一个十字路口的交通信号控制系统。分配给每个交通流一个时间 段，在此时间段它可通行，即绿灯亮。一个完整的交通信号周期是指每个交通 流都轮到一次绿灯的一段时间。我们需要设计一个红绿灯周期，使这个周期能 永远被重复下去，设每个绿灯时间段是一个单位长度，我们的目标是使一个完 整的交通信号周期的长度最小【1 1 | 。 现在我们把这一问题转化成一个图论问题。图g 的每个顶点表示一个交 通流。如果两个交通流有交织，则相应的两顶点连一条边。很自然，要解决这 个交通信号控制问题，实际上就是寻找对应每个独立集一个绿灯时间段，使 不同的独立集对应不同的绿灯时间段。这个完整交通长度就等于图g 的点色 数x ( g ) 。 然而，我们将看到这个方法没有提供最优的解决方案。我们把一个完整的 交通信号周期看成一个圆c ，每个顶点( 即每个交通流) 分配给一个单位长度 的时间段( 这个时间段表示此交通流轮到一次绿灯) 。两个相邻的顶点在c 上 分配给不相交的时间段。我们的目标是使圆c 的总长度最小。这就导出了图的 圆染色和圆色数的概念 5 】【6 】【7 】【9 】。 图g 的圆色数( 星色数) x 。( g ) 是由v i n c e 在1 9 8 8 年提出的，它是图的色 数的自然推广。令南和d 为满足七2 d 的正整数，且记= 0 ，l ，七一 1 】。图g 的一个( 七，d ) 染色是从顶点集合v ( g ) 到k 1 的一个映射c ，使得 对g 中任意相邻的顶点z ，y 有d j c ( x ) 一c ( 剪) is 七一d 。图g 的圆色 数x 。( g ) 是满足g 有( k ，d ) 染色的所有k d 的下确界。如果i y ( g ) i = n 且g 有 一个( k ，d ) 染色，那么存在整数后7 和d ，使得g 有一个( k 7 ，) 染色满 足k d k d 且k 7sn 。所以，要想知道x 。( g ) 的值，只要考虑所有满 足2 d 七礼的数对后，d 即可。因此： x 。( g ) = m i n k d ：g 存在( 七，d ) 染色，2 d ksn ) 4 山东大学硕士学位论文 同理可以给出圆边染色的定义。g 是一个简单图，且正整数对k ，d 满 足k 2 d ( 当图的最大度a 1 时k d ) 。那么图g 的一个( k ，d ) 边染 色就是一个从边集合e ( g ) 到颜色集合c o ，1 ，k l 】的映射，并且满 足dsi c ( 龟) 一c ( e j ) l k d ，色，e ，为相邻接的边。那么圆边色数就是图g 中 满足( k ，d ) 边染色的分数k d 的下界： x ：( g ) = i n f k d ：g 含有一个( k ，d ) 边染色， 1 3 圆边染色的基本性质 圆边染色与圆染色有着千丝万缕的联系，所以圆边染色拥有许多圆染色相 类似的性质。下面介绍一下关于图的圆边染色的已有结论。 如果g 含有一个k d 圆边染色并且七7 d k d ，那么g 明显的含有一 个七7 d ，圆边染色。这就意味着每一个( k ，d ) 圆可边染色的图g 必含有一 个( k 7 ，d ) 圆边染色，这里g c d ( k 7 ，d ，) = 1 ，并且七7 d = k d 。 定理1 3 如果g 是一个边数为q 的图，那么 x ：( g ) = m i n k d ：g 含有一个( k ，d ) 边染色，这里k = g 】- 定理1 4 如果图g 是第一类图，那么砭( g ) = ( g ) ；如果图g 是第二 类图，那么( g ) 0 ，存在一个数9 ，任何 一个围长至少是口的无桥立方图的圆边色数至多是3 + e 。 关于围长和圆色数的著名问题就是p e n t a g o n 问题：是否每一个围长充分 大的立方围都5 - 圈同构? 所谓图g 到日的同构就是v ( v ) 到v ( h ) 和g 中边 到日中边的一个映射。以上同构存在当且仅当g 的圆色数至多为5 2 而本文 研究的是圆边色数，圆边色数就是图g 线图的圆色数。 p a f s h a n i 证明了 下结论： 定理1 1 4 对任意整数a 1 ，实数e 0 ，存在一个正整数9 使得g 的 最大度为并且围长至少为g ，那么砭( g ) a + e 1 4 圆边染色的复杂度 图的圆边染色有着很多性质，对它的研究正在不断扩大。随着计算机的发 展，许多问题不得不依靠这些技术得以解决。所以对圆边染色的复杂度的分析 尤为必要。 定理1 1 5给定一个图来确定其圆边染色数的问题是一个n p 问题 定理l ，1 6给定一个第二类图来确定其圆边染色数的问题是一个n p 问 题 定理1 1 7 给定一个图g 来确定砭( g ) = ) ( 7 ( g ) 是否成立是一个p 问 题 1 5 本文的主要结果 早先a n d r e ah a c k m a n n 在t h ec i r c u l a rc h r o m a t i ci n d e x ( 圆边染色) 指 出了圆边染色的许多性质，并且给出了以下结论：如果g 是第一类图，那么 8 一 山东大学硕士学位论文 砭( g ) = ( g ) ：如果g 是第二类图，那么( g ) 鲁 舞= i g ，检验图g 是否含 有( 如，d 2 ) 染色，如果没有，砭( g ) = 鲁；如果含有( k 2 ，d 2 ) 染色，继续检 验( ，d 3 ) 染色，依次类推。 定理1 1 87 个顶点以内的所有2 类图如上所示g l ，g 2 ，g 8 ，其圆边 色数为： ) ( ：( g 1 ) = 3 ，x o ( c 2 ) = 芸， x ：( g 3 ) = 4 ， ) ( ：( g 4 ) = 丢， 置0 x ：( g 5 ) = 5 ，x ：( g 6 ) = 4 ，) ( ：( g 7 ) = ) ( ：( g 8 ) = 5 本文主要讨论的是关于一类笛卡尔积图的c 3 c 2 n + 1 的圆边色数的探讨并 给出了一个圆边色数的一个算法。 定理1 1 9 g 是笛卡尔积图c 3 c 3 ，那么x c ( g ) = 5 定理1 2 的证明，部分借助电子计算机。所编程序除了解决上图的圆边染色 问题外，对其他复杂度不是很巨大的情形也能实现图的圆边染色问题。 本文通过以上算法的计算给出了如下第二类图的圆边染色数，并进行分类 列表如下： 9 一 山东大学硕士学位论文 g 砭( g )x 7 ( g ) 分类 g 1 33c l a s s2 b g 2 5 3c l a s s2 a 2 g 3 44 c l a s s2 b g 4 9 5 c l a s s2 a 2 g s 5 5c l a s s2 b g 6 44c l a s s2 b g 7 55c l a s s2 b g 8 55c l a s s2 b g 9 9 5c l a s s2 a 2 第四章给出了一类链图玩的圆边染色数及其证明。 定理1 2 0定义玩是如图4 ，具体定义如下： y ( 日n ) = 砚，玩，龟，盔，t n i ，吼：i = 1 ，佗) u 秽 e ( 风) = q t 玩，玩龟，倪幺，以m ，m e 啦，n i a i ，6 m l ，岛n l ，也口件1 ：i = l ，n ) u u n l 】 其中a ，l + 1 = u 那么，砭( 凰) = 3 + 击 1 0 山东大学硕士学位论文 图l 1g t 图1 - 3g 3 图1 - 5g 5 图1 1 2g 2 图1 4g 4 图1 - 6g 6 图1 rg 7 图1 - 8g s 图2 ：顶点数小于7 的所有第二类图 一1 1 山东大学硕士学位论文 第二章解决圆边染色的算法 2 1 圆边染色的算法 在上一章的复杂度的研究中可知，找寻是否砭( g ) = x 7 ( g ) 本身就是一 个p 问题，所以在这种情形下，针对解决一些复杂度不是很高的情形，运用 了以下算法。 算法： l 确定给定图g 的圆边色数f o ( a ) 首先给出k 满足2 ksi e ( g ) i ，2 d k ，满足f g k d u g ，f g 2 是下界，u gsi e ( g ) i 是上界，所有的分数按照降序排列， u g = k l d l 乜d 2 k 如= f g 2 接下来就是采用循环的方法来确定g 是否含有( 锄，如) 染色。 首先给定一组颜色集记为l l ( e t ) = 0 ，1 ，一1 ，用这些颜色赋 予边龟，i = 1 ，i e ( g ) i 不失一般性，边e t 染颜色0 ，然后将0 从l i ( e 1 ) 中去掉。然后，其他颜色集l l ( e ) ，j = 2 ，f e ( g ) l 依次可 得并记为l 2 ( e f ) ，这样就保证了我们可以顺原路返回知道原来的颜色集。 其次，如果e j ( 其中j = 2 ，i e ( g ) i ) 与e 1 相邻，那些不 在g 中的( ，d 2 ) 染色的颜色将从l 2 ( 勺) 中去掉。然后将l 2 ( e 2 ) 中 最小的颜色染给边e 2 ，并且将这种颜色从其颜色集中去掉。颜色 集l 2 ( 勺) ，j = 3 ，l e ( g ) i 依次可得，并被记为l s ( e j ) 。那些不能 用在图g 的( ，c c 2 ) 染色的颜色将从l s ( e ，) 去掉，j 3 ，这里e ，是 与e 2 相邻的边。 3 在两种情况下，以上过程将会继续。其一是过程结束在一个( ，如) 染 色中，其二是结束在边岛，此时边e 。不能被l 。( e 。) 中的颜色染 色( 即厶( 岛) 是空的) 。在第二种情形下，需要按原路返回重新染色。 1 3 山东大学硕士学位论文 所有颜色集l 。( 勺) ，j 8 将被去掉。如果厶一l ( e 。一1 ) 是非空的，然后将 最小的颜色染给e 。一l ，并且在这个颜色集中将其去掉，然后其他颜色 集l ，l ( e j ) 依次可得( j s ) ，并被记为厶( e j ) 。如果l 一1 ( e 。一1 ) 是空 的，只要有非空颜色集的边e e 1 ，那么就需要按原路返回。如果这样的 边不存在，即说明图g 不含有( k 2 ，d 2 ) 染色，也就说明也( g ) = k t d 1 但 是如果图g 能被成功的( k 2 ，d 2 ) 染色，则按此算法继续检验下一个小的分 数k a d 3 ，依次类推。 由于这个问题本身就是一个n p 问题，所以问题的复杂度可想而知。但是 借助于计算机就能够解决相当部分图的圆边染色问题。以下程序就是图转化 为邻接矩阵进行运算，从而辅助解决图的圆边染色问题。 2 2 算法举例 本节是对笛卡尔积图c sx 晚的圆边染色数的求解过程。通过这个过程对 以上算法作出解释。gx 岛的图如下： 其邻接矩阵为； 1 4 山东大学硕士学位论文 011 1001o0 101 o 10o10 1 1o00 1001 l0o01 1 l00 01o1 0 1010 0011 1o001 lo0100011 01o0l010l 001o01 1 10 步骤1 首先由第一章内容确定上图的圆边染色数的值的范围。g o 的边独立 数o c ，= 4 ，其边数j e ( g ) i = 1 8 由砭( g ) 学得到我们要考虑的分数 按照降序排列，u g = ； 孚= l o 下面需要检验图g 是否含有o r ，4 ) 染 色，如果不存在即说明图g 是第二类的b 图，即砭( g ) = x 7 ( g ) 步骤2 采用循环枚举的方法来确定图g 是否含有( 9 ，2 ) 染色。图1 中给出 了图g 的邻接矩阵。首先给出颜色集n o ，2 ，3 ，9 ) ，不失一般 性给第一行第一个非零元素赋予颜色1 ，然后将颜色1 从上述颜色 集中去掉，重新记为1 ，对同一行第二个非零元素染色以颜色i ，使 得2si l 冬7 ，即3 冬i 8 ，然后将颜色i 从颜色集中去掉，重新 记为2 ，对同行第三个非零元素染色以颜色歹，使得2 b i is7 。 同行同列的元素依次进行染色。 步骤3 以上循环在遇到两种情况下停止，情况之一是图g 是含有( 9 ，2 ) 染色。 另一种情况就是生成的颜色集s 是空集，那么染色就按原路返回，重新 检验上一级染色集的其它元素。 要实现以上步骤通过以下程序具体实现； 源代码2 1 1 5 - 山东大学硕士学位论文 # i n c l u d e i n td 9 1 1 9 1 = ( 【o ，1 0 0 ，1 0 0 ，1 0 0 ，0 ，0 ，i 0 0 ，0 ，o ) o ，0 ，1 0 0 ，0 ，1 0 0 ，0 ，0 ，t 0 0 ，o ) ， 0 ，0 ，0 ，0 ，0 ，1 0 0 ，0 ，0 ，1 0 0 ， o ，0 ，0 ，0 ，1 0 0 ，i 0 0 ，i 0 0 ，0 ，o ) ， o ，0 ，0 ，0 ，0 ，1 0 0 ，0 ，1 0 0 ，o - ， o ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，1 0 0 ， o ，0 ，0 ，0 ，0 ，0 ，0 ，1 0 0 ，i 0 0 ， ( 0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，1 0 0 ) ， o ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，o ) ； i n tx i a _ j i e = 1 ： i n ts h a n g _ j i e = 3 ： i n tm a x = 1 4 ； i n tm i l l = l ： i n tm a t r i x n = 9 ： # d e f i n ed b 孝d e f i n ew i t h o u t _ n o w n u m _ e r r1 弗d e f i n ew i t h n o w a n u m _ e r r2 斧d e f i n e n o e r r4 i n t t r y _ n u m ( i n tr ，i n tc ，i 1 1 tn ) i n tt r a p 2 0 ； m e m s e t ( t m p ，0 ，2 0 , s i z e o f ( i n t ) ) ； i n tp o i n t = 0 ； 带i fd b p r i n t f ( ”n ( d ，d ，d ) 。”，r ，c ，n ) ； # e n d i f 1 6 f o r ( i n ti = o i d i 】 c 】) _ o p p t y p e = o p p _ b r e a k ； r e t u r nw l t h _ n o w _ n u m _ e r r ； ) e l s e o p p t y p e = o p p _ s e t ； o p p m u m = d i 【c 】一s h a n g j i e ； r e