（应用数学专业论文）赋权图中存在重圈的附加条件.pdf

摘要 摘要 本论文主要研究了赋权图中的路和圈的问题. 赋权图是指每条边都有一个非 负实数对应的图. 这个实数称为这条边的权 一条路 ( 圈) 的权是指其边的权的 和. 一个顶点v 的赋权度d ( v ) 是指与这个顶点 关联的所有边的权的 和， 在论文的第一章里， 我们介绍了一些基本的图论概念和术语， 本论文的研究 内容及其研究进展，以及在论文中我们所得到的主要结果. 在第二章里，我们证明了:假设 g是一个满足以下条件的 2 连通赋权图: ( 1 ) 任意三个相互独立的顶点的赋权度和至少为7 1 1 ;( 2 ) 在g的每个导出爪和 导出 修 正爪中， 所有 边的 权 都相等. 则口或者包 含一 个权至少为2 m / 3 的 圈， 或者包含一个 h a m i l t o n圈. 这个结果推广了z h a n g , b r o e r s m a 和l i 关于赋权 图中重圈存在性的一个定理. 在第三章里， 我们证明了: 假设g是一个满足k 2 的k 连通赋权图. 如果 “满足以下条件:( 1 ) 任意k 十1 个相互独立的 顶点的赋权度和至 少为。;( 2 ) 在 g的每个导出爪、导出修正爪和导出 已 中，所有边的权都相等.则 “或者 包含一个权至少为2 m / ( k +1 ) 的圈， 或者包含一个h a m i l t o n 圈. 这个结果推广 了e n o m o t o , f u j i s a w a 和o t a 的关于k 连通赋权图中 重圈 存在性的一个定理. e n o m o t o , f u j i s a w a和 o t a 给出了满足下列条件的连通图所具有的性质: ( 1 ) 对每个顶点: e n ( x ) n n 勿 ) ， 当d ( x , y ) 二2 时， 有二 ( x z ) =w ( y z ) ;( 2 ) 在g的每个三角形t中。 或者t的所有边的权都相同， 或者t的所有边的权 都不同 在第四章里， 我们用类似于e n o m o t o , f u j i s a w a 和o t2 的 方法， 给出了 满足第三章中 所得定理的条件( 2 ) 的连通图所具有的 性质. 并分别利用这些性质 给出了z h a n g , b r o e r s m a 和l i 的关于赋权图中的重圈存在性的一个定理及第三 章中所得出的定理的简单证明. 在第五章中， 我们对赋权图中的路和圈提出了一些可以 进一步研究的问题. 关键词: 赋权图，重 ( 路) 圈，赋权度 ( 和) ，导出爪 ( 修正爪。 几 ) ab s t r a c t abs t r a c t t h i s t h e s i s d e a l s w i t h t h e t o p i c o f p a t h s a n d c y c l e s i n w e i g h t e d g r a p h s . h e r e a w e i g h t e d g r a p h i s a o n e i n w h i c h e a c h e d g e i s a s s i g n e d a n o n - n e g a t i v e n u m b e r , c a l l e d t h e w e i g h t o f t h e e d g e . t h e w e ig h t. o f a p a t h ( c y c l e ) i s t h e s u m o f t h e w e i g h t s o f i t s e d g e s . t h e w e i g h t e d d e g r e e d l ( l7 ) o f a v e r t e x v i s t h e s u m o f t h e w e i g h t s o f t h e e d g e s i n c i d e n t w it h t h e v e r t e x . i n t h e fi r s t c h a p t e r , a f t e r i n t r o d u c i n g s o m e b a s i c t e r m i n o l o g y a n d n o t a t i o n s w e g i v e a b r i e f o v e r v i e w t o t h e ma i n r e s u l t s o f t h e t h e s i s . i n c h a p t e r 2 , w e g e t t h e f o l l o w i n g r e s u l t : s u p p o s e g is a 2 - c o n n e c t e d w e i g h t e d g r a p h w h i c h s a t i s fi e s t h e f o l l o w i n g c o n d i t i o n s : ( 1 ) t h e w e i g h t e d d e - g r e e s u m o f a n y t h r e e p a i r w i s e n o n a d j a c e n t v e r t i c e s i s a t l e a s t m ; ( 2 ) f o r e a c h i n d u c e d c l a w a n d e a c h i n d u c e d mo d i fi e d c l a w o f g , a l l o f i t s e d g e s h a v e t h e s a m e w e i g h t . t h e n g c o n t a i n s e i t h e r a h a mil t o n c y c l e o r a c y c l e o f w e i g h t a t l e a s t 2 m / 3 . t h i s g e n e r a l i z e s a n e a r l y r e s u l t o f z h a n g , b r o e r s m a a n d l i o n t h e e x i s t e n c e o f h e a v y c y c l e s i n w e i g h t e d g r a p h s . i n c h a p t e r 3 , w e p r o v e t h a t : s u p p o s e g i s a k - c o n n e c t e d w e i g h t e d g r a p h w h i c h s a t i s fi e s t h e f o l l o w i n g c o n d i t i o n s : ( 1 ) t h e w e i g h t e d d e g r e e s u m o f a n y k +1 p a i r w i s e n o n a d j a c e n t v e r t i c e s i s a t l e a s t 二 ; ( 2 ) i n e a c h i n d u c e d c l a w , e a c h i n d u c e d m o d i fi e d c l a w a n d e a c h i n d u c e d p , o f g , a l l e d g e s h a v e t h e s a m e w e i g h t . t h e n g c o n t a i n s e i t h e r a h a m i l t o n c y c l e o r a c y c l e o f w e i g h t a t l e a s t 2 m / ( k + 1 ) t h i s g e n e r a l i z e s a r e s u l t o f e n o m o t o , f u j i s a w a a n d o t a o n t h e e x i s t e n c e o f h e a v y c y c l e s i n k - c o n n e c t e d w e i g h t e d g r a p h s . e n o m o t o , f u j i s a w a a n d o t a o b t a i n e d s o m e p r o p e r t i e s o f t h e c o n n e c t e d w e i g h t e d g r a p h s w h i c h s a t i s fi e s t h e f o l l o w i n g c o n d i t i o n s : ( 1 ) 。 ， ( : : ) 二、 ( ， : 、 f o r e v e r y v e r t e x z n ( x ) n n ( y ) w i t h d ( x , y ) =2 ; ( 2 ) i n e v e r y t r i a n g l e t o f g , e i t h e r a l l e d g e s o f t h a v e d i ff e r e n t w e i g h ts o r a l l e d g e s o f t h a v e t h e s a m e w e i g h t . i n c h a p t e r 4 , w e o b t a i n s o m e p r o p e r t i e s o f t h e c o n n e c t e d w e i g h t e d g r a p h s w h ic h s a t is f i e s t h e c o n d i t i o n ( 2 ) o f t h e t h e o r e m w e g e t i n c h a p t e r 3 . wi t h t h e s e p r o p - c r t ie s , w e g i v e a s i m p l e r p r o o f o f a t h e o r e m o f z h a n g e t a l . a n d t h e t h e o r e m w e g e t i n c h a p t e r 3 we c o n c l u d e t h e t h e s i s w i t h c h a p t e r 5 b y p r o p o s i n g s o me p r o b l e m s f o r f u r t h e r r e s e a r c h o n t h e p a t h s a n d c y c l e s i n w e i g h t e d g r a p h s . i v ke y w o r d s : w e i g h t e d g r a p h , h e a v y p a t h ( c y c l e ) , w e ig h t e d d e g r e e ( s u m ) i n d u c e d c l a w ( m o d i fi e d c l a w , 几) 第一章绪论 第一章绪论 1 . 1 引言 众所周知， 路和圈是图论中最重要的研究内容之一 在路和圈的研究中， h a m i l t o n问 题以及与其密切相关的最长 路和最长圈间 题， 一直是图论研究中的 热点. 这些问题都是n p完全的， 所以人们对它们的研究主要集中在给出图中存 在h a m i l t o n 圈或长的路和圈的充 分条件. 自 从1 9 5 2 年d i r a c 1 2 给出图中 存在 h a m i l t o n圈以及长的路和圈的最小度条件之后， 人们相继研究了d i r a c, 结果各 种不同形式的推广， 如度和条件， 邻域并条件和邻域交条件等， 取得了非常丰富 和深刻的研究成果. 赋权图 是指每条边都有一个非负实数对应的图. 在图中 存在长路和长圈的研 究中， 几乎所有的研究工作都是针对非赋权图进行的. 直到上世纪八十年代末， 著名的图论专家b o n d y 和f a n 开始考虑一般赋权图中 存在长的 以 下用“ 重的” 以表示与非赋权图的区别) 路和圈的条件. 此后， 这方面的研究工作受到越来越 多的关注，取得了一定的研究成果，但是还有许多重要的间题没有解决. 研究赋权图中的路和圈， 具有非常重要的理论意义. 首先， 将路和圈的研究 扩展到赋权图 上， 研究的对象变得非常一般， 因为非赋权图可以看成每条边的权 均为1 的赋权图， 而在一般的赋权图中我们只要求它的边的权非负即可 所以， 关于赋权图中 路和圈的结论不是非赋权图中 相应结论的简单推广。 而是从研究 对 象到研究结论都有本质上的不同. 其次， 关于非赋权图中路和圈的一些结论往往 无法直接简单地推广到赋权图上，所以对赋权图中路和圈的研究有时会伴随着 新结论的诞生. 第三， 即使关于非赋权图中路和圈的一些结论可以推广到赋权图 上， 有时候用原来的方法根本无法证明这些新的结论， 必须引入新的方法， 而这 些新方法又适用于解决非赋权图中的一些问题， 由 此可能导出非赋权图中路和圈 的一些新结论. 第四， 关于赋权图中路和圈的一些问题， 与图论中的一些重要猜 想有关， 所以 对赋权图中的路和圈 进行研究， 将为这些猜想提供重要的依据. 本论文研究了赋权图在一些附加条件下的最重圈问题， 给出了在一些附加条 件下赋权图中 最重圈的权的一些估计， 讨论了在一些附加条件下的赋权图所具有 的性质， 推广了关于非赋权图中最长圈的长度和赋权图中的最重圈的权的一些结 果. 在本章的 第二节中， 我们介绍了论文中 所用到的一些图 论概念和术语. 在第 三、 四 节中 我们给出了赋权图中的 最重圈问 题的 研究进展和论文中所得到的主 要 1 第一章绪论 第一章绪论 1 . 1 引言 众所周知， 路和圈是图论中最重要的研究内容之一 在路和圈的研究中， h a m i l t o n问 题以及与其密切相关的最长 路和最长圈间 题， 一直是图论研究中的 热点. 这些问题都是n p完全的， 所以人们对它们的研究主要集中在给出图中存 在h a m i l t o n 圈或长的路和圈的充 分条件. 自 从1 9 5 2 年d i r a c 1 2 给出图中 存在 h a m i l t o n圈以及长的路和圈的最小度条件之后， 人们相继研究了d i r a c, 结果各 种不同形式的推广， 如度和条件， 邻域并条件和邻域交条件等， 取得了非常丰富 和深刻的研究成果. 赋权图 是指每条边都有一个非负实数对应的图. 在图中 存在长路和长圈的研 究中， 几乎所有的研究工作都是针对非赋权图进行的. 直到上世纪八十年代末， 著名的图论专家b o n d y 和f a n 开始考虑一般赋权图中 存在长的 以 下用“ 重的” 以表示与非赋权图的区别) 路和圈的条件. 此后， 这方面的研究工作受到越来越 多的关注，取得了一定的研究成果，但是还有许多重要的间题没有解决. 研究赋权图中的路和圈， 具有非常重要的理论意义. 首先， 将路和圈的研究 扩展到赋权图 上， 研究的对象变得非常一般， 因为非赋权图可以看成每条边的权 均为1 的赋权图， 而在一般的赋权图中我们只要求它的边的权非负即可 所以， 关于赋权图中 路和圈的结论不是非赋权图中 相应结论的简单推广。 而是从研究 对 象到研究结论都有本质上的不同. 其次， 关于非赋权图中路和圈的一些结论往往 无法直接简单地推广到赋权图上，所以对赋权图中路和圈的研究有时会伴随着 新结论的诞生. 第三， 即使关于非赋权图中路和圈的一些结论可以推广到赋权图 上， 有时候用原来的方法根本无法证明这些新的结论， 必须引入新的方法， 而这 些新方法又适用于解决非赋权图中的一些问题， 由 此可能导出非赋权图中路和圈 的一些新结论. 第四， 关于赋权图中路和圈的一些问题， 与图论中的一些重要猜 想有关， 所以 对赋权图中的路和圈 进行研究， 将为这些猜想提供重要的依据. 本论文研究了赋权图在一些附加条件下的最重圈问题， 给出了在一些附加条 件下赋权图中 最重圈的权的一些估计， 讨论了在一些附加条件下的赋权图所具有 的性质， 推广了关于非赋权图中最长圈的长度和赋权图中的最重圈的权的一些结 果. 在本章的 第二节中， 我们介绍了论文中 所用到的一些图 论概念和术语. 在第 三、 四 节中 我们给出了赋权图中的 最重圈问 题的 研究进展和论文中所得到的主 要 1 第一章 绪论 研究成果. 1 . 2 基本概念与术语 本论文只 研究有限简单图 文中未加说明的图 论术语见文献 ! 川 . 设g=( 拭e ) 是一个简单图. 如果 g的每条边e 都与一个非负实数 、 ( 。 ) 对应， 则这个图称为一个赋权图， 这个非负实数二 ( 。 ) 称为边c 的 权. 对c的一 个子图h， 分别用v ( h ) 和e ( h ) 表示 h的顶点集和边集h的权定义为 w ( h ) =、 ( 。 ) e e e( h) 某类子图中权最大的又叫最重的， 也称为最优的 所以最重圈也就是指赋权图的 所有圈中 各边权之和最大的圈. 对图g的一个顶点。 ， 用n h ( 动表示h中 与 二 相关联的顶点的集合. h 中顶点 二的赋权度定义为 d fi ( v ) 一艺 二 ( v h ) h c nh ( v ) 在不引起混淆时， 我们分别用n ( v ) 和d 0 ( v ) 表示n c ( v ) 和d g ( v ) . 一个非赋权图可以 看作图中每条边。 的权为， ( e ) 二1 的赋权图.因此， 在 一个非赋权图中， 对每个顶点v 有d ( v ) = d ( v ) ， 并且一个子图的权就是它的 边数. 一条( x , y ) 一 路是一条连接两个顶点x 和y 的路. 对于给定顶点: ， 一条( x z , 功 一 路 是指一 条过给定顶点: 的( x , 功 一 路. 对于 给定 顶点 集z， 一 条( x , z , 功 - 路是指一条包含给定顶点集z中 所有点的( x , 功 一 路. 用武 x , 功表示两个顶点: 和y 之间的距离， 即最短( x , y ) 一 路的长度. 以: 为终点的 路叫。 一 路， 其中边数 最多的叫 最长的。 一 路. 如果。 和。 是路尸上的两个顶点， 则p u , 川表示尸上 从。 到。 的一部分. 过给定顶点x的圈称为一个x 一 圈. 设v为一个顶点集， 则包含y中所有顶 点的圈称为一个y 一 圈 长为k 的圈称为k m, 3 圈常称为三角 形 用c ( g ) 表 示g中最长圈的长， 即c的周长. 包含g的每个顶点的圈称为h a m i l t o n 圈. 一个图若包含h a m i l t o n 圈， 则称这个图为h a m il t o n 图. g的一个最大独立集中 顶点的数目 用a ( g ) 表示. 如果g不是完全图， 则 对一个正实数 k d对于g的每个项点v都 成立，则对于任意给定的顶点;，g或者包含一个长至少为2 d 的y - 圈，或者 包含一个 h a m i l t o n圈. 定 理1 .4 . ( l o c k e (2 6 ) 设g是一 个2 连通图 ， d 是一个整 数. 如果对g中 每一 个顶 点。 都有d ( 的d ， 则对g中 任意两 个顶点x , y ，g或者包 含一 个长 度至少为2 d 的( x , y ) 一 圈 ， 或 者包 含一 个h a m i l t o n圈 定理 1 . 5 . ( e g a v a 等( 1 3 ) 设g是一 个k 连通图 ， d 是一 个整 数. 如果对g中 每 一 个顶 .点。 都有试 司d , 则对g中 任意一个满足 【 xi =k 的顶点子集x，g或者包 含一个长 度至少为 2 d的 x一 圈，或者包 含一个 ha m i l t o n圈 定理 1 . 3 和定理1 .4 分别给出了2 连通非赋权图中存在经过任意一个给定顶 点和任意两个给定顶点的长圈的最小度条件. 定理 1 . 5 给出了k 连通非赋权图中 3 互 1 .3贼权图中圈的研究进展 值， 用o x ( g ) 表示任意k 个独立顶点的赋权度和的最小值. 如果g是完全图， 则， k ( g ) 和二 戮 g ) 都定义为二. 我们称图k i ,3 为一个爪( c l a w ) ， 把对一 个三角形的某个顶点连一 条悬挂边 所得的图称为一个修正爪 ( m o d i fi e d c l a 叫 1 .3 赋权图中圈的研究进展 由于人们对赋权图中重圈存在性的研究基本上都是在已 有的非赋权图中长 圈存在性的有关结果上进行的。 所以我们先给出非赋权图中长圈存在性的一些结 论 定理 1 . 1 . ( e r d o s 和g a l l a i ( 1 7 1 ) 设 g是一个有 。个顶点和 。 条边的 2 边连通图那么 g包含一个长度至少为 2 c / ( 。 一1 ) 的圈 . 定理 1 . 2 . ( d i r a .c 1 2 ) 设 c是一个 2连通cn , d是一个整数.如果 d ( v ) d 对于 g的每个项点 。 都 成立，则g或者包 含一个长至少为2 d 的圈， 或者包 含一 个 h a m i l t o n圈 ， 定理 1 .2 给出了非赋权图中存在长圈的最小度条件. 在最小度条件下， 定理 1 . 2已经被依次推广如下. 定理 1 . 3 . ( g r 6 t s c h e l 2 4 ) 设 g是一个 2 连通图，d是一个整数.如果d ( v ) d对于g的每个项点v都 成立，则对于任意给定的顶点;，g或者包含一个长至少为2 d 的y - 圈，或者 包含一个 h a m i l t o n圈. 定 理1 .4 . ( l o c k e (2 6 ) 设g是一 个2 连通图 ， d 是一个整 数. 如果对g中 每一 个顶 点。 都有d ( 的d ， 则对g中 任意两 个顶点x , y ，g或者包 含一 个长 度至少为2 d 的( x , y ) 一 圈 ， 或 者包 含一 个h a m i l t o n圈 定理 1 . 5 . ( e g a v a 等( 1 3 ) 设g是一 个k 连通图 ， d 是一 个整 数. 如果对g中 每 一 个顶 .点。 都有试 司d , 则对g中 任意一个满足 【 xi =k 的顶点子集x，g或者包 含一个长 度至少为 2 d的 x一 圈，或者包 含一个 ha m i l t o n圈 定理 1 . 3 和定理1 .4 分别给出了2 连通非赋权图中存在经过任意一个给定顶 点和任意两个给定顶点的长圈的最小度条件. 定理 1 . 5 给出了k 连通非赋权图中 3 第一章 绪论 存在经过任意 k 个给定顶点的长圈的最小度条件 另一方面， b e r m o n d , l i n i a l 和 p o s a 各自 独立地给出了 d i r a c 结果的如下 推广: 定理1 . 6 . ( b e r m o n d 2 ) ( l i n i a l 2 5 ) ( p o s a 2 8 ) 设 g是一个 2连通图.如果对 g中每一对不相邵顶.点 都有 o z ( c ) 全、，则 g 或者包 含一个长至少为 s 的圈，或者包 含一 个 h a m i l t o n圈. 定理 1 .6 将d i r a c 结果中的最小度条件减弱为度和条件， 从而推广了d i r a c 结果 . 在文献 1 4 中 ，e n o m o t 。 给出了2 连 通 非 赋权图中 存 在经过任意一 个给 定顶点的长圈的度和条件，从而推广了定理 1 .6 ， 也推广了定理 1 .3 ， 定理 1 . 7 . ( e n o m o t o 1 4 ) 设g是一 个2 连通图，y 是g中一 个顶a. 则g或者包 含一 个长至少为。 2 ( 必 的j - 圈 ， 或者包 含一 个h a m i l t o n圈 . 在文献 5 中，b o n d y 将2 连通非赋权图中 存在长圈的。 2 ( g ) 型度和条件 减弱为。 3 ( g ) 型度和条件， 从而推广了定理1 . 6 定理1 . 8 . ( b o n d y 5 ) 设g是一 个满足0 3 ( g ) 二( m n + 2 ) 的2 连通图. 则g或者包 含一个长至 少 为2 m / 3 的圈 ， 或 者包 含一 个h a m i l t o n圈 在文献国 中，b o n d y 还猜想在没有条件二n +2 的 情况下， 定 理1 .8 可 以推广到 k 连通图中， 猜想 1 . 1 . ( b o n d y 5 ) 设g是一个满足 ,7 k + , ( g ) m的k 连通图， 共中k 2 .则g或者包含一个 长至少 为2 m / ( k + 1 ) 的圈 ， 或 者包 含一 个.h a m i l t o n圈 在文献 1 9 中，f o u r n i e r 和f r a i s s e 证明了 上述猜想是正确的. 定理 1 . 9 . ( f o u r n i e r 和f r a i s s e 1 9 ) ) 设g是一个满足q k 十 1 ( g ) 。的k 连通图， 其中2 _ c / 2 . 则g或者包 含一个长至少为 c 的圈，或者包 含一个 ha mi l t 。 二圈 以上我们给出了非赋权图中长圈存在性的一些结论. 对赋权图中的圈， 研究 的主要内容是: 考察对于那些在非赋权图中成立的关于存在长圈的结论， 在赋权 图中是否有类似的结论成立 已 有的研究工作主要包括两个方面: 一方面是将非 赋权图中的一些结论直接推广到赋权图中; 另一方面是在增加一些附加条件的基 础上给出非赋权图中圈的一些结论的赋权推广. 在文献 9 中，b o n d y 和f a n 将d i r a c 结果直接推广到赋权图中. 定理 1 . 1 2 . ( b o n d y 和f a n 9 ) 设g是一个2 连通的赋权图，d 是一个非负实数. 如果d w ( 司d 对于g的每 个顶点。都成立，则g或者包 含一个权至少为2 d 的圈，或者g的每个最重圈 为 ha mi l t o n圈. 定理 1 . 1 2 给出了赋权图中存在重圈的最小度条件，在最小度条件下，定理 1 . 1 2 又被依次推广如下: 定理 1 . 1 3 . ( z h a n g 等 (3 0 1 ) 设g是一个2 连通赋权图，d 是一个非负实数. 知果d ( 司全d 对于g的 每个 顶卢 、 ?， 都成立，则对于任意给定的顶点7f , ( i 或者包 含一个权至少为2 d的y - 圈，或者 g的每个最重圈为ha m i l t o n圈. 定 理 1 . 1 4 . ( f u j i s a w a 等! 2 3 ) 设 g是一个 2 连通碱权图， d是一个非负实数.如果对 g中每一个顶点 v都 有 d - ( 司全d,则对 g中任意两个项点:y, g或者包 含一个权至少为2 d的 恤: 们一 圈，或者 g中每一个最重圈都为i l a mi l t 二 圈 定理 1 . 1 5 . ( f u j i s a w a 2 1 ) 设 g是一个 3连通赋权图， d是一个非负实数，知果对 g中每一个项点 ”都 有d ( v ) d ， 则对g中任意三个项点y l , y 2 , y 3 ，g或者包 含一 个权至少为2 d 的勿1 , :4 2 , y 3 卜圈，或者 g中每一个最重圈都为h a m i l t o n圈. 定理 1 . 1 3 和定理1 . 1 4 分别给出了2 连通赋权图中存在经过任意一个给定顶 点和任意两个给定顶点的重圈的最小度条件.定理 1 . 1 5 给出了3 连通赋权图中 5 第一章 绪论 存在经过任意3 个给定顶点的重圈的最小度条件， 定理 1 . 1 4 和定理1 . 1 5 分别是 定理 1 . 5 当k 二2 和k =3 时的赋权推广. 与非赋 权图中 存在长圈的度和条件对应， 在赋权图中， 有下述关于赋权图中 存在重圈的度和条件，它们分别是定理 1 -6 和定理 1 . 7 在赋权图中的直接推广， 定理1 . 1 6 . ( b o n d y 等 7 ) 设g是一 个满足 0 2 ( g ) _ s 的2 连通赋权图.则g或者包 含一个权至少为s 的圈 ， 或 者包 含一 个h a m i l t o n圈 . 定 理 1 . 1 7 . ( f u j i s a w a 等 2 3 ) 设 g是一个 2 连通从权图，y是g中一个项点.则g或者包含一个权至少为 0 2 ( g ) 的y - m ， 或者包 含一个h a m i l t o n a . 在 文献4 0 中 ，z h a n g 和l i 将非 赋 权图中 的 结论与其 在赋权图中 推广 所 得 结论结合起来，得到一个更强的结论. 定理 1 . 1 8 . ( z h a n g 和l i 4 0 1 ) 设 g 是一个 2连通斌权图 如果对于 g 的每一对不相邻的顶查 、 二和 v，有 武 司十d ( v ) 。 和d w ( a ) + d ( v ) s .则g或者包 含一 个长至少为c ， 权至少 为、 的圈，或者包含一个 ha m i l t o n圈. 以上给出的都是非赋权图中关于长圈存在性的一些定理在赋权图中的直接 推广. 但是从已有的研究结果和研究经验看， 把非赋权图中关于最长圈的结果推 广到赋权图中， 不是一件容易的事. 重要的是要考虑选择什么样的问题作为推广 的对象，并不是所有的问题都可以得到自 然的推广 在 文献3 1 中 ，z h a n g 等 人 考虑了 能否将图中 存在长圈 的著名的f a n 定 理 推广到赋权图中，提出了以下问题: 问题 1 . 1设g是一个使得m a x d 对， d w c 们id ( 二 ， 幼=2 c / 2 的2 连通赋权 图，是否g或者为 h a mi l t o n图，或者包含一个权至少为 c 的圈? 同时，ma n g 等人通过例子指出问 题的 答案是否定的， 并给出了如图1 所 示的2 连通赋权图. 在这个图里， 给边 u 2 v 3 赋权1 ， 给边v 9 v 6 和v 7 v 9 赋权7 ， 给所有其它边赋权 5 . 则很容易得知 7 n a 7 1 f d 0 幻， d ( 幼ld ( x , 的二2 2 2 . 但 所得赋权图既不是 h a m i l t o n图，且图中最重圈的权为 4 0 . 1 . 3碱权图中圈的研究进展 所以， 如果想把 f a n 定理推广到赋权图中， 必须添加一些附加的条件. 但是 所加的这些条件既要符合非赋权图的情况， 又不能太多太强， 否则所得到的结果 就没有太大的意义 通过添加以下两个条件: c l : 对每个顶点z e n ( x ) f l n ( y ) ， 当d ( 二 ， ， ) =2 时， 有二 ( x z ) =，二 ( y z ) ; c 2 :在c 的每个三角形 t中， 或者t的所有边的权都相同，或者t的所有边 的权都不同. z h a n g 等人把f a n 定理推广到了赋权图中， 给出了以下定理: 定理 1 . 1 9 . ( z h a n g 等 (3 1 ) 设 g是 2 连通赋权图.满足条 件 。 1 和c 2 且满足ma-d(-), d l ( y ) ld ( x , y ) = 2 1 s / 2 .则g或者包 含一个权至少为s 的圈，或者包 含一个h a m i l t o n m i . 同时，作者还强调在此定理中，条件 c l 和 c 2 是缺一不可的.并用图 l 加 以说明: 如果象问 题 1 . 1 的反例那样给图1 赋权， 那么所得赋权图满足定理 1 . 1 9 中的条件。 a x d ( x ) , d ( y ) id ( x , y ) =2 1 4 4 / 2 及c l ， 但不满足。 2 ; 另一方 面，如果给边 v 4 v 。 和v 8 v 9 赋权 2，给边 v 5 v 。 和7 1 7 218 赋权 2 . 5 ，给所有其它边 赋权5 . 则在所得赋权图中有二 。 d - ( 幻, d - ( 功同二 ， 训=2 1 1 7 . 所得图 满足 定理 1 . 1 9 的条件- a x d ( x ) , d w ( y ) id ( x , y ) =2 1 3 4 / 2 和c 2 ， 但不满足c l ， 所得赋权图既不是 h a mil t o n图，且图中最重圈的权为 3 0.这个图也是问题的 一个反例. 由于定理1 . 1 1 是将f a n 定理的 条件减弱得到的， 所以由上面的讨论可知要将 定理1 . 1 1 推广到赋权图中， 也必须添加一些附加条件. 在文献 2 0 中，f u j i s a w a 给出了赋权图中所谓的爪条件: c c l :对处于 g中的一个导出爪或者一个导出修正爪中的每一对不相邻顶点 7 和y 都有m a x d ( 二 ) ， d - ( y ) ) s / 2 ; c c 2 :在 g的每个导出爪和导出修正爪中，所有边的权都相等. 第一章 绪论 利用以上两个条件，f u j i s a w a 将定理 1 . 1 1 推广到赋权图中，得到下述定31. 定理 1 . 2 0 . ( f u j i s a w a 2 0 ) 设 g是一个满足爪条件 。 c l 和c c 2的2 连通从权图.则 g或者包含一个权至少 为、 的圈 ， 或者包 含一 个 h a m i l t o n圈 需要说明的 是， 如果一个图满足定理1 . 1 9 中的 条件。 a x d - ( 劝、 d . ( 的id ( x , 功 =2 习2 ， 则一定满足条件c c l ; 并且 ， 如果一个图满足定理 1 . 1 9 中的条件 c l 和c 2 ，则一定满足条件c c 2 .因此， 定理 1 .2 0 的条件减弱了定理 1 . 1 9 的条 件， 是定理1 . 1 9 在赋权图中的进一 步推广.同时，f u j i s a w a 进一步指出， 定理 1 . 2 0中条件 。 c 2 不能去掉，并用图1 和图2 加以说明: 在图1 和图2 中， 定义w ( v 4 v s ) =w ( v 5 v 5 ) =w ( ) 7 7 )8 ) = w ( v s v 9 ) =4 ， 并且 给所有其它边赋权 5 ，令 s =3 8 .则图2 对应的赋权图满足 c c l ，并且对每个 导出修正爪，所有边的权都相等 但是， 所得赋权图既不是 h a m i l t o n图， 且图 中最重圈的权为 3 6 ， 类似的，图1 所对应的赋权图满足 c c l ， 并且对每个 导出 爪， 所有边的权都相等. 但是， 所得赋权图既不是h a m i l t o n 图， 且图中 最 重圈的权为3 6 s 一个很自 然的问题是能否将定理 1 . 9 直接推广到赋权图中， 所以 有下面的问 题 问 题1 . 2 . 令g是 一 个满 足。 券 i ( g ) ? 二的k- 连 通 碱 权图 ， 其中2 二换成当 d ( x , y , z ) = 2 时， 有d - ( x ) + d ( y ) +d ( z ) _。，则有如下结论成立: 定理 1 . 2 2 . ( 高敬振和姜学波 3 6 ) 设 g是2 连通从权图.满足条 件 。 1 和c 2 且当d ( x , y , 幼=2 时， 有d w ( 功+ d - 勿 ) + d , ( 约 m . ，则g或者包 含一 个权至少为2 tn / 3 的圈，或者包 含一个 ha mi l t o n圈 在文献 1 5 中，e n o m o t o , f u j i s a w a . 和o t a 给出了 满足条件 。 1 和c 2 的 连 通赋权图所具有的 性质 并证明了在添加附加条件d和。 2 的情况下，问题 1 .2 对任意k 2 是正确的. 实际上， 根据文献 1 5 中e n o m o t o , f u j i s a w a 和o t a 给 出的满足条件c l 和c 2 的 连通赋权图有任意两点的距离至多为2 的性质， 还可 得出定理 1 . 2 2 与定理 1 .2 1 是一样的， 定理 1 . 2 2 实质上并没有推广定理 1 . 2 1 . 定理 1 .2 3 . ( e n o m o t o 等 1 5 ) 设 g是一个满足 k 2的 k连通贼权图.如果 g满足条件 c 1和 c 2且满足 (7 k i ( g ) m+ 则g或 者包 含一 个权至少 为2 m / ( k + 1 ) 的圈 ， 或者包 含一个 ha ri l l o n圈. 定理1 . 2 1 , 1 .2 2 和1 .2 3 都是在添加附加 条件。 1 和c 2 的 情况下， 定理1 .9 在 赋权图中的推广 与f a n 条件的推广不同的是: 一方面， 还没有发现这些条件是 必须的; 另一方面， 如果没有这些附加条件的话，又 无法给出已 有结论的赋权推 广. 1 . 4 本文的主要结果 本文在绪论中介绍了论文中所用到的一些图论概念和术语， 叙述了图