（运筹学与控制论专业论文）图的距离二标号与组路覆盖.pdf

摘要 图的l ( 2 ，1 ) - 标- 9 来自所谓的频道分配问题t 某一区域有若干电台，不同的电台要使用 无线电渡发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位 置较近的电台要使用有一定相差的频道将频道分配给电台。目标是在保证电台互不干扰 的前提下使用最少的频道资源 图g 的l ( j ，k ) 一标号( 五k z + ，j2 ) 是图的l ( 2 ，1 ) 一标号的推广，它要求图中相邻 的点的标号至少相差j ，距离为2 的点的标号至少相差图g 的工o ，) 一标号数是指图g 的所有l 0 ，k ) - 标号的最大标号的最小值，记为 ( g ) 图g 的m 一0 ，女) 一圆标号着色是 指，个从点集v ( c ) 到非负整数集的函数，满足，( 1 ) l f ( u ) 一f ( v ) l 。，若w e ( g ) ；( 2 ) i f ( u ) 一，( ”) k2k ，若砘 的距离为2 ，其中。= m i n ( i = l ，m h ) 若m 是个正整数， 使得图g 存在一个f ，l u ，) 一圆标号，则称所有这些m 中最小的那个数为图g 的6 ，k 一 数，记为毛，k ( g ) l 0 ，) 一标号为一一对应的l 0 ，i ) 一标号，m 一0 ，) l 圆标号为一一对应的 m 一) 一圆标号当j = d e = l 似2 ) ，工 k ) - 标号就是三 i ) 一标号，m 一伉k ) - 圆标 号就是m 一( d ，1 ) 一圆标号 本文首先对图的一个概念一一路覆盖进行了推广，得到了r 一组路覆盖的概念，并由此 得到图的另一个不变量一一r - - 组路覆盖数 在第二章中。我们给出了图g 的 z l ( g ) 与其补图g c 的( d 一1 ) - 组路覆盖数之问确定 的数量关系，并给出了求二部图的广数的多项式时间算法 在第三章中，对于直径为2 的图g ，我们建立了，k 与g c 的【壬j 一组路覆盖之间的关 系利用上述结论，得到了一些比较复杂的图，如一珞口k 。，j 0 口j 0 ，j 等的工u ，) 一 标号数 在第四五章中，我们根据图g c 所含有的哈密顿i * - - 方圈的情况( r 1 ) ，确立了一般 图g 的越1 ( g ) 与屹l ( g ) 之间的关系及直径为2 的图g 的女( g ) 与易，k ( g ) 之问的关系 关键词：频道分配问题，r 一组路覆盖，哈密顿r 一方圈，缸盼一标号，m 一0 ，女) 一圆标 号。二部图 a b s t r a c t t h ed e f i m t i o no fn ( 2 ，1 ) - l a b e l l i n go f8g r a p hf l , r o f l ef r o mt h ee l a a m a e la s s i g n m e n tp r o b l e m s u p p o s ean u m b e ro fb r o a d c a s t i n gs t a t i o n sa r eg i v e n t h e s es t a t i o n sn e e dt r a n s m i ts i g n a l sb y r a d i o i no r d e rt ol _ e a l u e et h ei n t e r f e f e n e e ，a n yt w o v e r yc l o s e s t a t i o n sm u s tr e c e i v ed a m m e l s a p a r t e n o u c h ，a n da n yt w o d o s e s t a i t i o n sn l l l s tr e c e i v ed i f f e r e n te l a a m a e l s w eo u g h tt ou 舱t h el e a s t c h a n n e ll e s o u r c et oa s s i g nc h a n n e l st oe a c hs t a t i o ns u d at h a tt h ei n t e r f e r e n c ei 8a v o i d e d 工0 ，) 一l a b e l l i n go fag r a p hgi sag e n e r a l i z a t i o no fl ( 2 ，1 ) - i a b e u i n g a nl u ，) 一l a b e l l i n gi s a s s i g n m e n tf u n c t i o nf r o mt h ev e r t e xs e ty ( g ) t on o l m e g a t i v ei n t e g e r am d at h a tt h ed i t e e r e n e e b e t w e e al a b e l so fa n yt w oa d j a c e n tv e r t i c e si 8a tl e a s tj ，a n dt h ed i 疵r e 嘶b e t w e e nl a b e l so fa n y t w ov e r t i c e st h a ta r ea td i 丑t a l l c et w oa p a r ti sa tl e a s t t h em i n i n l u l nr a n g eo fl a b e l so v e ra l l l ( j ，砂i n b e l l i n g s o f a g r a p h c c a l l e d t h e h 矿n u m b 口o f g ，d e n o t e d b y k i ( g ) a n m - ( j ，后) 匆r c i l l a r l a b e l l i n go f8g r a p hg i saf i m e t i o n ，：矿( g ) o ，1 ，m l s u c ht h a t ( 1 ) i ，( u ) 一f ( v ) l m 五 i f 砒，冒( 研；( 2 ，f ( u ) 一，( 旬j m 毛i f 烈，= 2 ，w h e r ek f m = m i n f 霉f ，仇一 限t h el n i l l j l l l t m l ms u c ht h a tt h e r ee x i t s 缸 l - uk ) - c i r e l ：f l a rh b e l l i n gf o rg r a p hgi se 斌l e dt h e 毋，k n u m b e ro fg a n dd e n o t e db 毛，女( g ) f u ，) - l a b e l l i n gi st h e e t 0 el 0 ，) - l a b e l l i n ga n dm - d ，) 7 - c i r c u l a r l a b e l l m gi st h eo n e - t o - o n em - o ，七) c i r c l l l 盯l a b e l l i n g 、) l 】h e 七= 1 ，j = d ( d 2 ) ，f o ，七) 一l a b e l l i n g i st h e 王，( d ，1 ) - l a b e l l i n ga n d 竹扣o ，七y 幽1 1 l a rl a b e l l i n gi st h e 卜( d ，1 ) 7 - c i r c u l a rl a b e l l i n g ht h i 8t h 础，mf i r s t 即n 目妇t h ec o n c e p to ft h ep a t he o n v e r i n gt or - g r i pp a t hc c m 啦 o f8g r a p h i nc h 印胁t w o ，w eb u i l du pt h er e h t i o 璐h i pb e t w e e n 心l ( g ) dt h e ( d 一1 ) 一g r o u pp a t h c o v e r i n gn u m b e ro fg c ，u s i n gt i mr e s u l t ，w ed e s i g nap o l y n o m i a lt i m ea 培0 r i t h mt oc o m p u t et h e k , 1 - n l l m b e r f o ra n yb i p a r t i t eg r a p h i c h a p t e rt h r e e ，w eb u i l du pt h er e l a t i o n s h i pb e t w e e n ，k ( g ) a n dt h e l - g r o u pp a t h e e r m gn u m b e ro f 伊勋ad i a m e t e r2g r a p hg u s i n gt i mr e s u l t ，i ti se a s yt od e c i d et h e 如，p n t t m b 口f o r 1 eg r a p h s ，s u c h k d ，口，凰xk m i uc h a p t e r 栅a n d 胁，mo b t a j 】at h er e l a t i o n s h i p sb e t w e e n 1 ( g ) a n d 吃l ( g ) f o rg e n e r a l g r a p h sg ，a n d ，膏( g ) a n d 毛， ( g ) f o rd i a m e t e r2g r a p h sgb yt h eh a m i l t o nr - p o 咄e y r i eo f 伊 k e o r d s ：出a n da s s i g n m e n tp r o b l e m ，r g r o u pp a t hc o v e r i n g ，h a m i l t o nr p o w e rc y c l e ， d ，砂l a b e l l i n g ，* 0 ，) r a l l a rl a b e l l i n g ，b i p a r t i t eg r a p h i i 一、学位论文独创性声明 东南大学学位论文 独创性声明及使用授权的说明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 签名：l 区日期：丝丝! 厶扩签名：王域日期：丛生! 厶扩 东南大学中国科学技术信息研究所国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容和纸 质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理 第一章引言 图的着色问题研究近年来受到广泛地关注，它是图论研究中的一个重要分支而图的 着色有诸多定义，譬如点着色边着色圆着色、分式着色列表着色等等这些定义往往 来自于现实世界中为了描述某个问题而建立的抽象模型标号最初来自于上世纪九十年代 为研究频道分配问题而建立的数学模型，它是关于图的一种特殊的顶点着色最近十几年 来。图的标号研究已有很多结果。 1 1 标号的定义和背景 标号是从频道分配问题中运用图论方法抽象出来的一种图的着色频道分配问题【l 】 ( r a d i o c h a p e ll a r e q u e n c ya s s i g n m e n t ) 是讨论如何最优地给某一地理区域内不同的电台分 配有限个频道的问题在某一个区域内有多个电台，每个电台都要利用无线电波发送自己 的信号。但是，如果不同的电台使用了相同的或者相近的频道时，就可能产生相互干扰，所 以各个电台要避免使用可能产生干扰的频道同时，地理位置也会影响频道的分配如果两 个电台相距的足够远，那么即使用了相同的频道也不会影响其正常工作而对于地理位置 接近的电台就要保证使用的频道有一定的相差，对于地理位置十分接近的电台，仅仅不同 的频道是不够的，还必须使用相差足够远的频道才能保证互不干扰将频道分配给电台。目 标是在保证电台互不干扰的前提下使用最少的频道资源简单地说，频道分配问题就是将 尽可能少的频道分配给若干电台，使得可能产生干扰的两个电台所用的频道之差落在允许 的范围内，从而避免干扰 w k h a l e 曾用图论中t - c o l o r i n g 的概念来描述和研究过频道分配问题，最先把该问题 转化为图的着色问题1 9 8 8 年，f s r o b e r t s 提出了频道分配问题的一个变形问题，即相隔 很近的电台使用的频道至少相差2 ，相隔较近的电台必须使用不同的频道j 1 lg r i g g s 和 rk y e h 将此问题转化为不同于t - c o l o r i n g 的另一种图着色问题，并且考虑了更一般的情 形他们引入了l d ( 2 ，1 ) 一标号； 定义1 1 1 旧对于简单图g ( v e ) 和任意给定的实数d 0 ，图的标号( l d ( 2 ，1 ) 一l a b e l l i n g ) 是一个非负函数，：y ( 研一f 0 ，) ，满足条件t ( 1 ) l f c u ) 一f c v ) 2 d ，若口e ( g ) ； ( 2 ) i ，( u ) 一，( ) i d ，若d ( u ， ) = 2 1 东南大学硕士学位论文 2 若，是图g 的一个l d ( 2 ，1 ) 一l a b e l l i n g ，我们就称，el d ( 2 ，1 ) ( g ) 每个点在，下的 象称为该点的标号定义i i ，( g ) = m “ ，( v ) ：f y ( g ) ，则图g 的标号数( l d ( 2 ，1 ) 一 l a b e l l i n gn u m b e r ) 定义为t ( g ，d ) = m i n l0 ，( g ) 1 1 上述定义可用频道分配的语言来描述。其中g 中的点表示电台，如果两个电台十分接 近，则在g 中代表这两个电台的点虬口相邻；如果两个电台比较接近，则d ( u ，= 2 在所 有的点 上指定值，( ) ( 代表电台使用的频道) ，根据定义这就保证了各电台之间不会相互 干扰我们的目标就是在所有满足条件的频道分配中，寻求使用频道资源最少的分配 r o b e r t s 提出的这一数学模型清楚地描述了频道分配问题的约束和目标，而g r i g g s 和 y e h 提出的k ( 2 ，1 l 一标号更有一般意义由于这里的着色使用了实数的概念，和以往图的 整数值点着色有较大区别，给我们研究该问题增加了不少困难和麻烦g d g g s 和y e h 很好 的解决了这个问题他们在【2 1 中绘出了下面两个引理，将实数值标号l e t ( 2 ，1 ) - l a b e l l i n g 和 r o b e r t s 提出的整数值标号l ( 2 ，1 ) 一l a b e l l i n g 建立了联系 引理1 1 1 旧，”0 ，d 0 ，k z + ，如果忙一y i k d 。那么f 一矿l k d ，其中 一= i x d i d , l ，= 【u d j d 引理1 1 2 【砑对任意的实数d ，a ( g ，回= d a ( g ，1 ) 由这两个引理，对于任意的实数d 0 ，如果函数，满足约束( 1 ) 和( 2 ) ，那么任意 口y ( g ) ，取，( 口) = 【f ( v ) d j d ，也满足约束( 1 ) 和( 2 ) ；如果a ( g ，d ) = i f l l ，其中， 厶( 2 ，1 ) ( g ) ，那么存在g 的一个整数值的l 1 ( 2 ，1 ) 一l a b e l l i n g 函数，满足，= d ， 所以有下面的定理； 定理1 1 3 阍对千任意的图g ，存在一个整数值的l 1 ( 2 ，1 ) 一l a b e l l i n g 函数，：v ( g ) 一 口，j ，马) 使得i i i ( g ) i i = a ( g ，1 ) 从而，关于图l d ( 2 ，1 ) 一l a b e l l i n g 问题的研究就只需考虑整数值的l i ( 2 ，1 ) 一l a b e l l i n g 问题 了为了简便，我们将二1 ( 2 ，1 ) 一l a b e l l i n g 简记作l ( 2 ，1 ) 一l a b e l l i n g 对于一个给定的图g 它 的l ( 2 ，1 ) 一l a b e l l i n g ( 二( 2 ，1 ) 一标号) 是定义在v ( g ) 上的非负整数函数，满足条件t ( 1 ) j ，( 一，( 口) i22 ，若f 4 g ) ；( 2 ) i ，( u ) 一，( 口) i 1 ，若d ，口) = 2 相应的我们将 l l ( 2 ，1 ) ( g ) 记作l ( 2 ，1 ) ( g ) ， ( g ，1 ) 记作k ，1 ( g ) k - l ( 2 ，l 卜l a b e l l i n g 表示最大标号不大于k 的l ( 2 ，1 ) - l a b d l i n g g r i g g s 和y e h 提出和研究了更一般的标号，其中，满足条件：i ，( ) 一，( ) 2 拖若 d ( z ，y ) = 对1s sn ，其中是正整数，m 1 ，m 2 ，f r t n ( m l ，砌2 f n n 0 ) 是 给定的正整数如果n = m 1 = 1 ，那么，就是正常的点着色如果n = 2 ，m l = r n 2 = k ， 壅童奎耋堡主耋堡塞塞 3 则，就是工u ，) 一l a b e l l i n g 也就是说，对于一个给定的图g 及正整数j 和d k ) ，图g 的个工缸k ) 一l a b e l l i n 9 是定义在v ( g ) 上的非负整数函数，满足：i y ( u ) 一，( ”) i2j 若 d ( u ，口) = 1 ；l f ( u ) 一，( 口) l 若d ( “，= 2 我们称之为工u k ) - 标号定义图g 的工0 ，k ) - 标号数x j , k ( c ) = m i n im a x f ( v ) ：口y ( g ) ) 工u ，动一l a b e l l i n g 当值恰为1 时就是所谓的l ( d ，1 ) 一l a b e l l i n g ，我们称之为z ( d ，1 ) 一标 号着色给定一个图g 和正整数d ，图g 的个l ( d ，1 ) 一l a b e l l i n g 是定义在y ( g ) 上的非 负整数函数，满足tl ，( 妨一，( i 之d 若碳“，口) = l ；l ，( 一，( ”) 2 1 若d 如，= 2 定义图 g 的z ( d ，1 ) 一标号数为x d , l ( g ) = m i n i m a x y ( v ) ： y ( g ) ) 当d = 2 时，l ( d ，1 ) - l a b e u i n g 就是以2 ，1 ) 一l a b e l l i n g ，k l ( g ) 即为z ( 2 ，1 ) 一标号数) t 2 , t ( g ) 。若对g 的某个烈吐1 ) 一标号 ，m a x f ( v ) ： y ( g ) = 沁，i ( g ) ，别称，是最优标号或简称，是最优的若，为一对 应，即图g 的每个顶点标号都不相同，则z ( d ，1 ) 一记为f ( d ，1 ) - 标号，相应的定义工，( d ，1 ) 一 标号数。并记作屹1 ( 6 3 同样可以求出l ( d ，1 ) 一标号的最优标号我们统称这一类标号为 图的距离2 标号 图的距离2 圆标号是由h e u v w l ，l e e s e 和s h e p h e r d 在1 9 9 8 年【3 】引入的令伊是一个 长度为r 的圆在伊上任意确定个顶点，给它标号为0 对于上的其他顶点，根据 它到点0 的弧的长度( 按伊的逆时针方向) ，给它个标号z 协【0 ，r ) ) 伊上两个顶 点z ，的圆距离定义为k 一乩= m t , a i z 一i ，r k y l 对于正整数j ，k ，j2k ，图g 的m 一缸) 一圆标号( 可记为m o ，的。一标号) 是个从点集v ( g ) 到非负整数集的函数 ，满足t ( 1 ) ，( ) 一f ( v ) l 。2j ，若wee ( g ) ；( 2 ) l f ( u ) 一，( 口) k ，若d ( ) = 2 。其中 。= m 叫mm 一) 若m 为正整数，使得图g 存在个t ，l u ，k ) - 圆标号，则称所有 这些m 中最小的那个数为图g 的屯一数，记为毋，k ( g ) 与上，u 女) 一标号相似，m 一 女) 7 一 圆标号为一一对应的m 一0 ，砂一圆标号当= 1 ，j = d ( d 2 ) 时，m u ，砷一圆标号就是 m 一( d ，1 ) 一圆标号，且对于图g 有颤i ( g ) 为缸l ( g ) 图的z ( 2 ，l 卜标号和l ( 1 ，1 ) 一标号曾在过去十凡年里得到了广泛研究，并且有了很多结 果l ( a ，1 ) - - , l ) 一标号和m 一( 2 ，1 ) 。，m 一匕) 。一标号也有些研究结果 1 2 关于标号已有的基本结果 在频道分配向题的现实背景下，标号这一概念的提出并得到广泛研究无疑具有实际意 义最近十几年很多人进行了相关的研究，也得出了一些重要的结果 壅里奎兰堡圭耋堡垒塞 4 对于图的l ( 2 ，1 ) 一标号，确定了路圈、树及一些特殊图类的k 1 一数，并且给出了一些 图的地，一数的上下界，如弦图很多人利用图的一些不变量，得到了标号的一些结果，如 下 c h a n g 和k u o 剃用图的最大度得到了如下定理， 定理1 2 1 若图g 舌寺最大度为，则k i ( g ) 2 + 2 a g r i g g s 和y e h 对一般图做了如下猜想t 猜想1 嘲对任意最大度a 2 的圈g ，b 1 ( g ) s 2 对几类特殊的图诸如弦图、直径为二的囹等，这个猜想被证明是正确的但对于一般的 图，此猜想仍未得到证实 g r i g g s 和y e h 建立了图g 的沁，1 ( g ) 与x ( g ) ( 图g 的色数) 的关系。 定理1 2 2 【习g 为一个度为n 的图，则如。1 ( g ) s n + x ( g ) 一2 此外g e o r g e s 和m a y o 等研究了沁，1 ( g ) 与图的个不变量一一g c 的路覆盖数c ( g c ) ( 图 g 的路覆盖数是指覆盖图的所有顶点的最小的点不交的路的条数) 之间的关系，证明了下 述定理 定理1 2 3 【司 ( 1 ) 沁，l ( g ) s n 一1 当且仅当o ( 伊) = 1 ( 2 ) r 是一个整数，r 2 ，则沁1 ( g ) = n + r 一2 当且仅当c ( 伊) = r 除上述结果外，对积图( p r o d u c tg r a p h ) 诸如路积图，路圈积图、圈积图，p r a n a v ak j i m 等巳做了研究，给出了l ( 2 ，1 ) 一标号的相关结果【6 】外平面图( o u 娜l a n a rg r a p h ) ，平面图， 直径为2 的图，排列图( p e r m u t a t i o ng r a p h ) ，分裂图( s p l i tg r a p h ) 等都已有人进行了l ( 2 ，1 ) - 标号研究，得到了相应的界 z ( 2 ，1 ) 一标号问题已被证明是n p - 完全问题即使对一些特殊图类。如弦图平面图 二部图，分裂图等，工( 2 ，1 ) 一标号问题仍然是n p - 完全问题 关于l ( d i 卜标号同题研究，其难度无疑比默2 ，1 ) 一标号问题要大很多下面是有关 l ( d ，1 ) 一标号的一些基本结果； 定理1 2 4 【习对任何囊大度为的国g ，k 1 ( g ) 2 + g i ) a 定理1 2 5 【刁对任何置大度为的树t ，a + d - 1 k ，l ( m i n + 2 d 一2 ，2 a + d 一2 ) 定理1 2 6 嘲若g 是囊大度为的弦i l l ( c h o r d a lg r a p h ) ，则h l ( g ) s ( 2 d + a 1 ) 2 4 定理1 2 。7 if 若g 是最大度为的奇强弦圉( o d ds t r o n g l yc h o r d a lg r a p h o s f - c h o r d a l ) ， 则沁1 ( g ) d 东南大学硬士学位论文 定理1 2 8 嘲令p n 为包含n 个顶点的路则有h 1 ( 忍) = d ，k ，l ( p 3 ) = d + 1 ，知1 ( r ) = d + 2 ，k 1 ( j ) = d + 2 ，v n 5 g e o r g e s ，m a u r o ，s t e i n 对故女) 一标号傲了较多的研究，他们给出了完全图的积图和树 等特殊图类的二u k ) - 标号数，参见【9 】f 1 1 】特别地证明了b ， ( g ) 与伊的哈密顿【t j 一方 路之间的关系如下z 定理1 2 9 【翻设g 是一个有n 个顶点，直径为2 的图， ( 1 ) 若，女( q ；一1 ，则对于所有的r ，2 曼r 畦1 ，( 产舍有一条哈密顿p 一1 ) 一方 路 ( 2 ) 若g 。有一条哈密顿( r - 1 ) - 方路，则对于所有的j ，当tsr 时，b ，k ( c ) = ( n - 1 ) k l 女) 一标号相对于l ( 2 ，1 ) 一标号在研究中给我们又增加了些许困难很多图类即使 我们得到了l ( 2 ，1 ) 一标号数，也很难得到工( d ，1 ) 一标号数或l ( j ，功一标号数过去十几年 中，l ( 2 ，1 ) 一标号的研究相对来说已经比较丰富工( d ，1 ) 一标号和l u ，k ) - 标号的研究还有很 多空缺之处，其原因主要在于问题的难度加深了 下面给出图的距离2 圆标号的一些结果 图的距离2 圆标号，是由h e u v w l ，l e e s e 和s h e p h e r d 在1 9 9 8 年【3 】引入的他们对无限 网格傲了研究其后，很多人散了相关的研究，得到一些结果； 定理1 2 1 0 【删对于最大度为的树t 。白，l ( 研= 2 j + a 一1 l i u 和z h u 在【1 3 】中证明了下述定理，并完全确定了圈的白，1 一数 定理1 2 i i 口司对于i 大度为的树t ，毛，k ( = 2 j + ( a 一1 ) k 定理1 2 1 2 嘲对于任意图g ，而，( g ) + 1 鸟，k ( 研b ，k 够) + j 我们还必须特别指出，当j = 2 ，= 1 时，对于图g ，如1 ( g ) 为沁1 ( g ) + l 或沁1 ( g ) + 2 即使如此，已知沁1 ( g ) ，欲确定是1 ( g ) 仍然是不容易的 l i u 【1 4 】确定了图g 的如，1 ( g ) 与其补图g c 的路覆盖数c ( g c ) 之问的关系如下t 定理1 2 1 3 1 锄( g “如， 若伊为哈密顿图， i ；n + c ( e 产) ， 若g 。的路覆盖数为c ( ( 产) ( 2 ) l s m ，l i u 和v 沌建立了图g 的弓，( g ) 与其补图g ”的【纠一方圈的关系； 定理1 2 1 4 口司设g 是一个有n 个顶最，直径为2 的图，则 ( 1 ) 若屯( g ) = 砥，则对于所有的n2sr 扪，g _ 含有一条哈密顿r 一方围， 5 变堕奎耋堡圭耋堡丝奎 6 ( 2 ) 若g c 有一条哈密顿r - 访 l ，科斗千所有的j ，k ，当女sr 时。白，( g ) = n k 定理1 2 1 5 口司设g 是一个有n 个顶点。直径为2 的图，若，s2 k ，则 ( 1 ) b k ( g ) = 椰一c ( ( 严) + c ( ( 产) 一l 珏，屯i ( g ) = 坼一c ( g 。) + c ( g 。) j ，若g c 的路覆 盖数为c ( g 。) ( 2 ) ； ( 2 ) 岛，k ( g ) = n ，若e ；c 为哈密顿图 1 3 本文的主要工作 本文首先引入了图的另一概念一一图的r 一组路覆盖，相应的得到了图的另一个不变量 一一r 一组路覆盖数利用这一不变量，首先确定了当d - 2 _ 2 时图g 的屹l ( g ) 与其补图的 ( d 一1 ) 一组路覆盖数之间的关系，并给出了求二部图的k 1 一数的多项式时间算法其次，对 于直径为2 的图g ，解决了g c 中不存在哈密顿l 铂一方路时确定b ，一数的问题，得到了 ，k c g ) 与g c 的嗟卜组路覆盖之间的关系利用上述结论，可以很容易地得到一些比较复 杂的图，如：j 白口，j 厶口甄，j xj 等的l o ，砂一标号数在第四五章中，根据一般 图g 的补图的哈密顿r 一方圈的情况，确立了磕1 ( g ) 与1 ( g ) 之间的关系及直径为2 的图 g 的 ，k ( g ) 与毛， ( g ) 之间的关系 文中未加说明的符号以及未加定义的概念参见【1 6 】 第二章图g 的坛1 ( g ) 与g p q 一1 ( g 。) 本章给出了交中用到的圈的相关知识及一些推论，并弓l 入了图的一个新的不变量一一 r - 组路覆盖数，讨论了它的一些性质其次证明了图g 的a ：l 1 ( g ) 与g p c d 一1 ( g c ) 之间的关 系 2 1r 一方路覆盖与r 一组路覆盖 本文中出现的图无特别说明。均指有限简单图所有标号都从0 开始 首先，介绍文中用到的图的一些概念和结论 令g = 司是个不定向的图，顶点集是矿( g ) ，边集是e ( g ) 两个点”v ( g ) 称为相郐的，如果e c g ) 一个顶点t 称为的邻点，如果t 与口相邻对于任意 的点集s y ，l sj 为顶点集s 的基数g 旧为g 中的由s 导出的子图，即一边集为 昱( s ) = u v e e l 扛口s ) 的g 的子图( s ，e ( 毋) 定义2 i 1 设r ，r 1 是个整数，若图g 的顶点集为v = 口1 ，地，) ，边集为e = l l 忙- j l r ) ，则称g 为含有n 个顶点的r 一方路，记为器 值得注意的是，根据上述定义，完全图j 矗( n r ) 是一条7 - - 方路 图g 的路覆盖是指能够覆盖住g 所有顶点的点不交的路的集合相似的，可以定义图 g 的一方路覆盖 定义2 1 2 对于图g ( k 昱) ，其顶点集v = v l ，t 1 2 ，) c = x l ，j ，2 ，局) 是y 的一 个划分，且有：对于每个f ，i f d ，由置导出的图g 的子图，g l 磁】，包含一条r 一方路， 则称c 为图g 的r 一方路覆盖定义c r ( g ) 为图g 的r 一方路覆盖的基数当c r ( g ) = 1 时， 称图g 有一条哈密顿r 一方路 定义2 1 。3 对于图g 及正整数d ，d 2 ，c = c 1 ( g ) ，c k ( g ) 为围g 的d 一组路覆盖，须 满足下列三个条件， ( t i ) 每个q ( g ) = 爿，砭，砭 都是g 的一方路覆盖。1s i 出 ( t 2 ) 令c d g ) = 碍，砭，砭，c o l ( g ) = 爿“，乌“，蹦) ，1 s i d 一1 ，则对 于每个je l ，2 ，钳1 ) ，必然存在某个( 1 s q ) ，使得y ( 只+ 1 ) y ( 砭) ； ( t 3 ) 沿路科，碍，呓给g 的顶点一个顺序tt 口1 ，也，) 则任意一条t 一方路 碍，1 j q ，1 t sd 的顶点序列必然是 v l ，t j 2 ， 的一个子序列 。 7 定义2 1 4 对于雷g 及正整数d 。d 2 ，图g 的所有d - 组路覆盖c = q ( g ) ，c 0 ( g ) ) 中最小的dc i 称为图g 的d 一组路覆盖数，记为g p c d ( g ) ，其中q ；i g ( g ) i ，i ：1 2 ，d i = i 若图g 的一个d 一组路覆盖c ； a ( g ) ，c d ( g i 满足量乌：g p c d ( g ) ，则称c 为图g 的最优d 一组路覆盖，c 中1 一方路覆盖的顶点序列称为图害的最优顶点序 从上述定义中，可以看到c l c 2 s sc d 图g 有一条哈密顿d 一方路当且仅当g 有个d 一组路覆盖c = a ( g ) ，q ( g ) ) 使得 c 1 = c 2 = 勺= 1 令硝是目的顶点数，是巧的最后个顶点，1s s d ，lsj c f 令x = 。一，l s j sc i 一1 ) ，则我们有x 1 x 2g x 8 若顶点u 属于x “，但不属于 ，l tsd 一1 。称口是c 的“+ 1 ) 一破点特别的，x 1 中的点称为c 的1 一破点令皿 为c 中i 一破点的个数，即掣的基数很容易得到如下引理t 引理2 1 1 c = a ( g ) ，c i ( g ) 是图g 的一个d 一组路覆盖，则d i = c 1 一l ，d i = 盘一c 一1 2 s i sd 且d = 龟一1 2 2 砭1 ( g ) 与g p c d 一1 ( g c ) 引理2 2 1 g 是有n 个顶点的圈，c = a ( g ) ，q l ( g ) ) 是伊的一个( d 1 ) 一纽路覆 盖，皿为c 的 一破点的个数，则心1 ( g ) n l + 皿( d 一 ) 证明t 令c = t o ( g c ) ，1 l sd - 1 是酽的个( d - 1 ) 一组路覆盖，则q l ( g c ) = 马，只) 是g c 的( d 一1 ) 一方路覆盖令a 是b 的顶点个数，是( d 1 ) 一方路b 的第j 个顶 点，l l c x 是c 的一破点集，1s s d 一1 则对于每个 ，1 l c i 都存在唯一 的，l 岛sd 一1 ，使得蕞x h 考虑如下映射，：v + i - ! ，( 弓) = ( p l + d 一向) + j l f = 1 奎查奎兰堡圭兰堡丝茎 9 在上面定义的标号中，用到的最小标号是0 。最大的为 c - i m a x ( f ) = ( a + d 一缸) + p c l l = i c - - i = p l + + p c 一1 + 似一向) c l l 筝l ；n 一1 + ( d h ) 墨 = n 一1 + d i ( d i ) t = 1 函数，给所有顶点的标号都不相同，对于距离为2 的点，它们的标号相差至少为1 下 面证明对于图g 中任意两个相邻的顶点。，f 。有 ，( 。) 一，( 彩 d 设z f e ( g ) ，考虑下列两种情况t c a s e i ：若z 与，在同一条( d 1 ) 一方路最上，1 sc 因为铆e ( g ) ，则，在只中必然不相邻，所以d ( z ，口) 2d ( 在最上) 根据上述标 号方式，必然有i f ( x ) 一，( ) 1 2 d c a s ei i ：若$ 只。弓，l j ，1 i ，j c 不妨设f j 的情况类似) 考虑图g 的( d 1 ) 一方路只，弓对于任意的， k s j - 1 ，令z m 是晟的最后 个顶点必然存在某个k ，1 k sd 一1 ，使得是“一破点令m 2 名蓉1 k ，则由 y 假) u uv ( p j ) 导出的g c 的子图必然包含在c - i ( g 。) 的某条( m i ) - 方路p ”_ 1 中 由于z 与p 在g c 中不相邻，我们有d ( ，”) m ( 在尸”一1 上) 根据，的定义，可以得到 i ，( z ) 一，( ) 1 2 m + u i ) ( d 一，n ) = d + 0 一 一1 ) ( d m ) d 因此，是图g 的一个上，( d ，1 ) 一标号 引理得证 - 定理2 2 2 设g 是度为f l 的图，d 偿2 j 是一个整敷，则有屹l ( g ) ；t l d + g p c d 一( g 9 d - l 证明；令c = q ( 伊) ，1 tsd 一1 是伊的一个最优啦一1 ) 一组路覆盖，则盘= f = 1 g p c d 一1 ( g ) 令c o = 1 ，则有z ed i ( d 一 ) = ( c i c l 1 ) ( d i ) _ 1 措扛1 ；q ( d i ) 一臼一a ( d i ) 曷 “ ；e i ( d 一 一d + f + 1 ) + c 扣l ( d d + 1 ) 一( d 1 ) 矗 ；e 盘一d + 1 i = l d - 1 因此n d + g p c d 一1 ( g c ) = n 一1 + 皿 一i ) 由引理2 2 1 我们只需证明a 2 1 ( g ) = 1 d - 1 n 一1 + e d i ( d 一 ) 我们可以很容易得到k 1 ( g ) = n 一1 当且仅当g c 有哈密顿( d 一1 ) 一方路则当g c 有 哈密顿( d 1 ) 一方路时，定理成立 下面我们证明伊不舍有哈密顿( d 1 ) 一方路的情况假设定理不成立，令，是g 的一 个( d 1 ) 一标号，它的最大标号小于t l d + g p 吼一l ( g c ) 由于g 。不含有哈密顿( d 一1 ) 一 方路，则k 令a 是由，得到的标号集合，有l a l = t l ，且a 是 o ，l ，耐的真子集 若( 0 ，1 ，k ) 中某个连续的子序列b j + 1 ，z ) ，有j 一1 ，f + 1 a ，j , i + l ，l 簪a ， 我们称这个子序列为，的个跳跃若这个跳跃含有i 个元素，我们称它为t 一跳跃由于 k l ，必定含有若干个跳跃令9 j 为，中j 一跳跃的个数，则 o ，l ，耐中没有被，用到 的标号的个数是譬；西我们可以用如下方式构造俨的一条( d 1 ) 一组路覆盖，c ，( 伊) = q ( g c ) ，1 i d 1 ) 对于 o 1 耐中的每个 ，若i 被，用过，则- 1 。( i ) 是g 的一 个顶点；若i 没有被，用过，则令- 1 ( i ) ；口可以看到序列s = ( y - 1 ( o ) ，f - 1 ( 1 ) ，i - 1 ( ) ) 包含了g 的所有顶点和若干个# 显然：每个极大连续的# 子序列都是，的一个跳跃在 s 中，对于每个j ，1 j d 一1 ，所有极大连续的。且至少包含了d j 个元素的# 子序列 将s 分成若干个部分，g ，品，删去序列s 中所有的，我们得到g 的个顶点序列 目，砭，焉( 依s ，岛，s 毛) 注意，标号相差至多为d 一1 的任意两个顶点在g 中必 然是不相邻的，因此在g c 是相邻的不难发现上述序列中的每个群都对应了伊中的一条 j 一方路，其中l js d - l ，1s t c j ，利用这种方式，我f 门可以得到g c 的一条( d 一1 ) - 组 路覆盖，c ，( g c ) = 辟，砖，磁) ， 砰，曙，呓 ， 平1 ，碍一，磁- 一1 。 ) 令q 为 c