（运筹学与控制论专业论文）关于赋权图中重圈的一个范型定理.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 设g = ( ve ；甜) 为赋权图，定义g 中点u 的权度蟛( 口) 为g 中与口相 关联的所有边的权和，图g 中圈的权值定义为圈中所有边的权和范更华 7 中证明了下述众所周知的结论：设g 是n 阶2 一连通图，c 是满足3 c 兰几 的一个整数如果对任意的u ，v y ( g ) ， d ( u ， ) = 2 = = 竹t n z d ( u ) ，d ( 钉) ) 三c 2 那么g 中存在哈密尔顿圈或者存在一个长度至少为c 的圈b e d r o s s i a n 等 人 1 和z h a n g 等人 1 2 中分别将上述范定理进行了推广本文将范定理更 进一步推广为： 假设g 是满足下述条件的2 一连通赋权图， ( 1 ) 对g 中每一个与k i ，3 同构的导出子图丁，丁中所有边的权都相等； ( 2 ) 对g 中每一个与k i ，3 + e 同构的导出子图t ，丁中所有边的权都相等 ( 3 ) 对g 中每一个与k i ，3 或者与k i ，3 + e 同构的导出子图丁， m i n m a x d 苫( x ) ，d 若( 9 ) ：d ( z ，y ) = 2 ，z ，y y ( t ) ) c 2 那么，g 中存在哈密尔顿圈或者存在一个权值至少为c 的圈 此外，我们还证明了该定理中的条件( 1 ) 和( 2 ) 是不能被减弱为条件( 1 ) 或条件( 2 ) 的 关键词：拟正规赋权图；重路；哈密尔顿圈；权度 硕士学位论文 m a s t e r st h e s i s a b s t r a c t s u p p o s et h a tg = ( ve ； ) i saw e i g h t e dg r a p h ，d e f i n et h ew e i g h t e d d e g r e ed 器( ) o fav e r t e x 口i ng a st h es u n lo ft h ew e i g h t so ft h ee d g e si n c i d e n t w i t hu ，a n dt h ew e i g h to fac y c l ei sd e f i n e da st h es u mo ft h ew e i g h t so fi t s e d g e s t h ef o l l o w i n gt h e o r e m i saw e l l k n o w nr e s u l to ff a n g e n g h u a 7 = l e t gb ea2 - c o n n e c t e dg r a p ho nnv e r t i c e sa n d3 c 札，i f d ( v ，“) = 2 辛m a x d ( v ) ，d ( “) 2e 2 f o re a c hp a i ro fv e r t i c e sva n d “i ng ，t h e ngc o n t a i n se i t h e rah a m i l t o n c y c l e o rac y c l eo fl e n g t ha tl e a s tc b e d r o s s i a ne t “ 1 】a n dz h a n ge t a l 1 2 】h a v e r e s p e c t i v e l yg i v e nt w og e n e r a l i z a t i o n so ff a n st h e o r e m i nt h i sp a p e r ，w eg i v e af u r t h e rg e n e r a l i z a t i o no ff a n 8t h e o r e ma sf o l l o w s ： l e tgb ea2 - c o n n e c t e dw e i g h t e dg r a p hw h i c hs a t i s f i e st h ef o l l o w i n gc o n d i t i o n s ( 1 ) f o re v e r yi n d u c e ds n b g r a p ht o fg i s o m o r p h i ct ok 1 ，3 ，a l lt h ee d g e so ft h a v et h es a m ew e i g h t ； ( 2 ) f o re v e r yi n d u c e ds u b g r a p ht o fg i s o m o r p h i ct ok 1 ，3 + e ，a l lt h ee d g e so f th a v et h es a m ew e i g h t ； ( 3 ) f o re v e r yi n d u c e ds u b g r a p ht o fg i s o m o r p h i ct ok 1 ，3 o rk 1 ，3 + e ， r ，n r n 。z d 苫( z ) ，d 。u , i ) ：d ( x ，y ) = 2 ，。，y v ( 丁) ) 2e 2 t h e ngc o n t a i n se i t h e rah a m i l t o nc y c l eo rac y c l eo f w e i g h ta tl e a s tc i na d d i t i o n ，w ea l s op r o v et h a tt h ec o n d i t i o n s ( 1 ) a n d ( 2 ) o ft h ea b o v e t h e o r e mc a nn o tb ew e a k e n e dt oc o n d i t i o n ( 1 ) o r c o n d i t i o n ( 2 ) 1 1 硕士学位论文 m a s t e r st h e s i s k e y w o r d s ：s e m i n o r m a lw e i g h t e dg r a p h ：h e a v i e s tl o n g e s tp a t h h a m i l t o n i a nc y c l e ；w e i g h t e dd e 掣 e e 1 1 1 硕士学位论文 m a s t e rst i e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：石菜日期：a 岁年占月i t 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名：今璨导师签名：嘲匆煌 日期：a 一岁年月，日日期：力6 年6 月f f 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定享受相关权益。回童论塞握童卮进度! 旦坐生；旦二生；旦三生 筮壶! 作者签名：会莱 日期：毒殍6 月，f 日 导师签名枷锨 日期：例扩年g 月日 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景和现状 第一节引言 由关于十二面体的一个数学游戏而起源的哈密尔顿图问题( 1 s 5 6 ) 经历了 一百多年，于上世纪五十年代后，吸引了大批图论专家的兴趣，对它的研究从 此步入了繁荣时期d i r a c ( 1 9 5 2 ) 给出哈密尔顿图的一个充分条件：设g 是 最小次为d 的n 阶图，其中6 n 2 ，n23 ，则g 含有晗密尔顿圈之后， 许多关于哈密尔顿图性质的经典定理陆续被证明图中最长圈的长度是图论 研究的中心问题之一，在此期间，有关图申长圈存在性的绪论也取得了重大进 展 设g 是一个几个顶点的2 一连通图，c 是满足3 csn 的一个整数， 如果下列四个条件中的任意一个成立，则g 包含一个长度不小于c 的圈 ( 1 ) d i r a z 6 】对于g 每一个顶点u ，d ( v ) c 2 ： ( 2 ) b e r m o n d 2 】如果d ( v ) 22 ，那么必有d ( v ) + d ( u ) c ； ( 3 ) p d s a 1 l 】对于任意满足l j ( c 一1 ) 2 的j ，必有i ：d ( u ) j j j l ； ( 4 ) b o n d y 3 如果d j j ，d k ( j ) ，那么必有吗+ d k c f 注：g 是一个n 个顶点的2 连通图，对于g 的每一个顶点w 其度记 为d ( u ) ，将g 的顶点的度排列成如下的度序列：d 茎d 2 d 。，这里d 表示上述度序列的第i 项，) 接着，b o n d y 和f a n 等人开始逐渐将d i r a c ，e r d 6 s 和g a l l i a 等人的一些 有关长圈存在性的经典定理推广到赋权图中 12 定义 硕士学位论文 m a s t e r st h e s i s 本文仅考虑简单图，文中未加定义的概念和符号参见f 4 j 设g 是一个 图，我们用y 和e 分别表示g 的顶点集和边集对g 中每条边e 赋予一个 非负实数叫( e ) ，称为e 的权，并称g 一( e ；w ) 为赋权图如果w 满足 ( 1 - 1 ) 对g 中任何导出路x y z ，都有w ( z y ) = ( z ) ； ( 1 2 ) 对g 中每一个三角形，其三条边的权或者都相等或者都不相等； 则称g 为正规赋权图 易见如果g = ( ke ； t 3 ) 是正规赋权图，那么 图1图2 ( 1 - 3 ) 对g 中每一个与k 1 ，s ( 如图1 ) 同构的导出子图丁，t 中所有边的 权都相等 ( 1 4 ) 对g 中每一个与k 1 3 + e ( 如图2 ) 同构的导出子图t ，t 中所有 边的权都相等 称满足( 1 - 3 ) 和( 1 4 ) 的赋权图为拟正规赋权图显然，所有的正规赋权图都 是拟正规赋权图 设g = ( ke ；j ) 为赋权图，是g 的子图，定义日的权为 铷( 口) = w ( e ) e e e ( h ) 对任意”v ( g ) ，分别用n c ( v ) 和d g ( v ) 表示口在g 中的邻点集和邻点数 2 硕士学位论文 m a s t e r st h e s i s 定义u 在g 中的权度为 皑( ”) 一训( “”) g ( ) 在不引起混淆的情况下，我们将( ) ，d g ( ”) 和昭( ”) 分别简记为n ( v ) d ( v ) 和d ”( u ) 设p = v i ? 3 2 v 。是g 中的一条路，我们总是假定尸的方向为从观到 仇，定义p 上顶点的偏序关系如下：v i ! 口，当且仅当isj 如果，v v ( p ) 并且“w ，那么我们用f l u ，v 1 表示p 上从u 到v 子路，并用尸一 v ，“ 表示 尸 u ， 的反向路设z ，y v ( g ) ，如果x ，y 在g 的同一个连通分支中，则称 g 中连接z 和y 的最短的路的长度为z 与y 之间的距离，记为d a ( x ，g ) ；否 则，定义d gx ，y ) = 。如果p 是g 中最长路，并且对g 中任何最长路q 都有w ( p ) 叫( 0 ) ，则称p 为g 中的重路 1 3 已知结论 下面是一个众所周知的结论 定理1 ( f a n 7 ) 设g 是n 阶2 一连通图，c 是满足3 c 冬n 的一个整数 如果对任意的“，口v ( g ) ， d ( 乱，口) = 2 辛m a x d ( u ) ，d ( ) ) c 2 那么，g 中存在哈密尔顿圈或者存在一个长度至少为c 的圈 接下来的两个定理分别是上述范定理的推广 定理2 ( b e d r o s s i a ne ta l 1 ) 设g 是2 一连通图，如果对g 中每一个与k 1 3 3 硕士学位论文 m a s t e r st h e s i s 或者k 13 + e 同构的导出子图丁都有 r a i n m a x d r ( x ) ，( f g ( 可) ) ：d ( x ，y ) = 2 ，z ，9 v ( t ) ) c 2 那么，g 中存在哈密尔顿圈或者存在一个长度至少为c 的圈 定理3 ( z h a n ge l ：a 】f 1 2 ) 设g 是2 一连通正规赋权图，如果对任意的u ，口 v ( g ) ： d ( u u ) = 2 = 争竹l 口茹 d 誊( u ) ，d 苫( 口) ) c 2 那么，g 中存在哈密尔顿圈或者存在一个权值至少为c 的圈 事实上，定理2 将定理1 的条件减弱而得到同样的结论，定理3 将定理 1 推广到赋权图中下面我们考虑是否能将定理2 推广到赋权图中? 1 4 主要结论 本文的主要目的是将定理2 推广到赋权图中，我们得到了下述定理 定理4 设g 是2 一连通拟正规赋权图，如果对g 中每个与k 1 ，3 或者1 3 + e 同构的导出子图丁都有 r a i n m a x d 吕( z ) ，d 誊( ) ) ：d ( x ，y ) = 2 z ，y y ( 丁) ) c 2 那么，g 中存在哈密尔顿圈或者存在一个权值至少为c 的圈 由于正规赋权图是拟正规赋权图，所以定理4 是定理1 3 的推广 4 硕士学位论文 m a s t e r st h e s i s 第二节结构引理 为了证明定理4 ，我们需要下面两个引理 2 1 引理1 引理l 设g 是连通图，p 是g 中最长路如果g ( p ) 】是哈密尔顿图 则g 也是哈密尔顿图 证明用反证法设e 是g ( p ) 中的哈密尔顿圈，但g 不是哈密尔顿图， 则v ( c ) v ( g ) ，因为g 是连通图，所以存在z v ( g ) ，y v ( a ) v ( c ) 使 x y e ( g ) 易见c + z 中存在一条比p 更长的路，与j d 的最长性矛盾! 口 2 2 引理2 引理2 设g 是2 一连通非哈密尔顿赋权图，p ：= 札o u l u 2 是g 中的一 条重路，则g 中存在圈g 满足伽( g ) 皑( 牡o ) + 蟛( 嘶) 证明根据重路的定义，我们有n ( u o ) un ( u ，) v ( p ) 因为g 不是哈密尔 顿图，由引理1 知e l y ( p ) 不是哈密尔顿图，所以下述论断成立 论断1 对任意的i 1 ，2 ，p ) ，如果u ( o ) ，那么一1 隹( 哗) 口 论断2对任意的i 1 ，2 ，p 一1 ) ，如果蛳( u o ) ，则叫( “，) 伽( 让o n 。) ；如果u i ( 札p ) 则w ( i t q + 1 ) 叫( “。“p ) 论断2 的证明设u i ( o ) 则路p + = ，“ 一lq i 一2 “o “，脚与j p 的长度 相同根据p 的选择，我们有w ( p ) 2 w ( p + ) ，从而w ( u 一“。) 三”( u o “。) 同 5 硕士学位论文 m a s t e r st h e s i s 理可证论断的后半部分 口 为了证明引理2 ，我们需要下述概念设p ：= p u o ，“p 是g 中一条路， p ：= r b ，y i ：1 冬i5m ) 是g 中内部点不交的路的集合，如果对任何 i = l 2 ，m 都有v ( r ) nv ( p ) = ，y i ，并且 2 2 0 = 3 7 1 x 2 饥兰2 2 3 9 2 x 4 _ _ y m - 2 三z m _ 一1 一 硕士学位论文 m a s t e r 7 st h e s i s 因此，引理2 为真 8 口 硕士学位论文 m a s t e r st h e s i s 第三节主要结论的证明 为了证明定理4 ，我们先证明下面一个引理 31 引理3 引理3 设g 是2 _ 连通拟正规赋权图，如果g 不是哈密尔顿图，并且对g 中每一个与k 1 , 3 或者l ，3 + e 同构的导出子图丁都有 饥i n 眦z d 答( z ) ，d 誊( ) ) ：d e ，y ) = 2 ，z ，y v ( 丁) ) c 2 假设”是g 的某一条重路的端点那么，存在一条其中一个端点为”的重 路，使得该熏路的另一个端点的权度4 2 证明 假设不存在一条其中一个端点为”，另一个端点的权度c 2 的重 路令尸= u ， 。( = ) 是g 中的一条重路根据p 的选择，我们 有n ( v 。) v ( p ) 令k ( f ) = m a x i ：v 1 v 。e ( g ) ) 由于g 是2 一连通 的，口t 除了和。z 相连接之外，至少还和p 上的其他一个顶点相连接由 于p 是非哈密尔顿图g 的一条最长路，则g 不包含长度为p 的圈于是 k ( p ) 满足3 k ( p ) p 在所有其中一个端点为v 的重路中选择一条重路 p = 曲v 2 使得k ( p ) 尽可能地大，令k = ( 尸) 由于g 是2 一连通的，g 一讥中存在一条路q ：= q v 。，仇】连接v ( p v l ，v l 。一， ) 与i ，( p k + l j w ，】) ，其中s 七 七十1 则7 3 1 巩，y k 7 3 k 扎讥仉e ( g ) 根据k 的最大 1 0 硕士学位论文 m a s t e r 7 st h e s i s 性，? j 1 y k + l e ( g ) ，v l u f 隹e ( g ) 于是 g l ，砚，v k + l ，v t j 竺k 1 ，3 或k 1 ，3 + e 由g 的拟正则性，我们有w ( v k 仇) = w ( v l v k ) = 叫1 另一方面，因为 ( u k ) = w 2 叫( 耽) ，所以g 讪扎v ，v k ，仇芏甄，3 + e 根据t 的最大性知u s 。州甓 e ( g ) ，因此v k 仇+ l e ( g ) 从而，g 【 仇+ 1 ，y k ，u s 叻 皇k 1 ，3 + e 该结论蕴 涵着训( 叻 1 ) = w ( v 。+ 1 ) 与论断1 2 矛盾i 口 现在我们有5 = k 一1 和t = k + 1 ，于是口k 一1 口k 十l e ( g ) 则 是一条最长路因此，我们有( 仇) cv ( j d ) 根据g 的2 一连通性，g 一讥+ t 中存在一条路q ：= q 8 ，m 连接v ( p h ，口k ) 与矿( j d 陬+ 2 ) ，其中s k + 1 m 注意到f = k + 1 根据t 的最大性，我们有8 = k 因为n ( v k ) c v ( 尸) ，所以v k v 。e ( g ) 根据k 和s 的选择，我们有7 3 1 u m ，v s v 。隹e ( g ) ，于 是g 【 。v k ，v 。， 1 ) 望k 1 ，3 + e 这蕴涵着u ) ( v l v 。+ 】) = ( + 1 ) ，与论断1 2 矛盾! 这样我们就完成了情形1 的证明 情形2 口。，u s + l ，- t - ， k g | v g ( u 1 ) 选择v l y 。，v 。扎，巩) g ( 口i ) 使得f 尽可能地大显然，s 2 并且，对于满足f 2 和岳n ( v 1 ) n ) 的最小整数由 于 ( 1 ) nn ( u f ) ，我们有j f + 2 而且，显然j 墨七+ 1 那么， f + 2 jsk + 1 硕士学位论文 m a s t e r st h e s i s 如果f + 2sj k ，则v l v j e ( g ) 根据隹n ( v 1 ) n ( ) ，我们有 功功譬e ( g ) 那么，g 【 铆，y j l ，v l 型k i 3 十e 如果j = k + 1 ，则v l v j 芒e ( g ) 那么 g ( 钆，啦l ，v j ，v l 1 竺k 1 ，3 或k 1 3 + e 由于d ”( u 1 ) c 2 ，我什 有d ”( ! ) 2c 2 口 我们假设不存在一条其中一个端点为( = ”) ，另一个端点的权度c 2 的重路因而，根据论断2 1 ，我们有下面的结论 论断2 2g 中不存在端点分别为叻和的重路 口 论断2 3w ( v l v l + 1 ) ( 1 ”f + 1 ) 论断2 3 的证明假设w ( y i u m ) = w ( u l y + 1 ) ，则讪一1 v l v l + i y l + 2 唧是 一条重路，与论断2 2 矛盾! 口 令w 1 = w ( v l v l + 1 ) 和w 2 = w ( v l v l + 1 ) 论断2 4n ( v t + 1 ) 口1 ，如 n ( v 1 ) nn ( v t ) 论断2 4 的证明由于w ( v l v l + 1 ) w ( v l v l + 1 ) g 创，地+ 1 ，7 3 1 ，饥) k 1 ，3 或k 1 ，3 + e 因而，对于任意的 ( 钆+ 1 ) 忱，叻) 都有v u l e ( c ) 和y v l 三( g ) 口 12 硕士学位论文 m a s t e r st h e s i s 论断2 5 七f + 1 论断2 5 的证明假设女= 2 + l ，则根据论断2 4 ，叻吼。1 e ( g ) 这与的 最大性矛盾! 口 论断2 6 矶+ 1 v k e ( g ) 特别地，后l + 3 论断2 6 的证明用反证法假设 v l + l v k z ( a ) 根据论断2 3 和g 的拟正则性知 因此， g 【 甜七， f + 1 ，甜2 ，v l 】喾k 1 ，3 或k 1 ，3 + e ( 2 6 1 ) v l v k e ( g ) ( 2 6 2 ) 同理，根据论断2 3 和 1 ”+ 1 譬e ( g ) ，我们有 a v l ，铆+ 1 ，地，v k + 1 ) 】掌k 1 , 3 或k 1 ，3 + e 因为 l 耽隹z ( a ) 和v l v k + 1 e ( g ) ，所以 1 3 ( 2 6 3 ) j | 巩 而因 吧 粤 删 叭 = 叫 有 们甜 我| l d 和 ，= 良d 王 姗讯 硕士学位论文 m a s t e r st h e s i s f k + 1 e ( c )( 2 6 4 ) 根据( 2 6 2 ) 和( 2 6 4 ) ，我们有s 7 2 1 ，v k ：v l ，? 2 k + 1 ) 】皇k 1 ，3 + e ，因而w ( v k ? 2 1 ) = ( + 1 7 2 1 ) = “d j ( v l ? 2 k ) = 叫】由于钆一l v l e ( g ) w ( 7 2 1 7 2 k 十1 ) = l 和w ( 7 2 1 7 2 1 + 1 ) = w 2 ， 因此 g 甜j 一1 ，v 1 口f 十1 ，口+ 1 ) 芒k 1 ，3 或k 1 ，3 + e ( 2 6 5 ) ( 2 6 6 ) 由于w ( v l v l + 1 ) = 叫1 和w ( ? 2 1 v l + 1 ) = 2 ，c , ( 7 2 1 1 ，v l + 1 ，口t ，v z 薯k 1 ，3 + e 根据 f 2 65 ) ，我们有 口l 讪一1 e ( g )( 2 6 7 ) 根据( 2 6 4 ) ，( 2 6 6 ) 和( 2 6 7 ) 我们有a v 1 饥一1 ，v l ，v k + 1 些k 1 ，3 十e ，因而 w ( v l 一1 f ) = w ( v l 一1 7 2 k + 1 ) = w ( v l ? 2 k 一1 ) = ? 2 3 1 于是，v l v l + 1 ? ) k v l v 2 v i t 讥+ i r k + 2 是一条重路，与论断2 2 矛 盾! 口 1 4 k 喾 +kk g 有我 毗隋卜撕 m 趵 可6 w 和和 u 2= 每，2 h “u 啦矗 叭 据于根由 硕士学位论文 m a s t e r st h e s i s 论断2 7 如果? ) l v k e ( g ) ，则 v i v 1 l ! + 1 i 七一1 ne ( c ) ：0 论断2 7 的证明用反证法假设计e ( g ) ，并且存在i 满足1 + 1s i e l 和计十i 口( 6 t ) 选取8 l ，l 使 ( 2 7 - 1 ) f + 1 s 1 七 l ，v s a ”幻e ( g ) ； ( 2 7 2 ) 在满足( 2 7 - 1 ) 的前提下，“尽可能地大； ( 2 - 7 3 ) 在满足( 2 7 1 ) ，( 2 - 7 - 2 ) 的前提下，s 】尽可能地大 注意到u s ，仉1 + - ，v k 垦( u ，) 类似于情形1 ，我们可以证明 井且8 1 = 七一l ，f 1 = k + l - 因为g 【 口l ，u r + l ，饥) 掣k 1 ，3 或k 1 ，3 + e ， ( + 1 ) ：叫v l v k ) ，根据( + ) 式，我们得到叫( k + ) 叫( 嘞一1 v k ) 因此g f 十。，巩扎巩，一，) ? 掣，f 1 。毒e 由。1 的最大性知巩一1 巩+ 2ge ( g ) ，从而魄讥+ 2 f ( g ) 但此时，妄们有 g ! ”t + 2 ，坝，一1 ，口1 兰局，3 + e ，由g 的拟正则性得叫( u l v k ) ：”( 讥一1 巩) ，与 论断2 8 对于任意满足，+ 2 i k 的数i ，都有研吼e ( g ) 论断2 8 的证明根据论断2 4 ，我们有钆研+ 2 e ( g ) 假设存在满足z + 3 i k 、哩爹一个地，使得吡她ge ( g ) 令r = m i n i ：f + 3 i 七，研聋 e ( g ) ) ，则r f + 3 ，并且 1 u ! ( 坼一1 ) ( u ，) 1 5 ( 2 8 1 ) 硕士学位论文 m a s t e r st h e s i s 论断2 8 17 3 l + i v ，一l e ( g ) 论断2 8 1 的证明用反证法假设 v l + l v ，一1 z ( v ) ( 2 8 1 1 1 因为y l + l q + 2 e ( g ) ，所以r 1 + 3 根据r 的选择，我们有r l + 4 并且 我们断言 f + 1 7 3 r 隹e ( a ) ( 2 8 1 | 2 ) ( 2 8 1 r 3 ) 否则，? j r n ( v t + 1 ) v l ，v l ，根据论断2 4 我们有? 3 r 7 3 1 e ( g ) ，与( 2 8 1 ) 矛 盾! 根据( 2 8 1 1 ) 和( 2 8 1 3 ) ，我们有re v , + 1 ， l ，珥v r ) 兰k 1 3 + e ，从而， t ) ( 3 1 y r 一1 ) = w ( ? 3 1 7 3 r ) = 叫( 坼一l v ，) = f ! 1 3 ( v l v l + 1 ) = 叫1 另一方面，根据( 2 8 1 ) 我们有g 饥，v r - 1 ，坼，v l 】竺k 1 ，3 + e 这蕴涵着? 3 ) ( 7 3 1 v ，一1 ) = ( 坼一i 坼) = l 但w ( 7 3 1 7 3 r 1 ) = w l 和叫( q 叻+ 1 ) = w 2 表明g 钆+ l ，讪，珥一2 ，v r - 1 喾l ，3 + e 根据( 2 8 1 1 ) ，( 2 8 ，1 2 ) 和( 2 8 1 ) ，我们有 v l + l v ，一2 e f g ) 接下来，我们断言 l r _ 2 珥e ( c ) 1 6 f 2 ，8 14 1 f 28 1 5 1 假设y r - 2 v r e ( g ) ，根据( 2 8 1 1 ) ：( 2 8 1 3 ) 和( 2 8 1 4 ) ，我们有 g 讪+ l ，y r - 2 ，v r - l ，珥) 型k i ，3 + e 而且，根据( 9 8 1 ) ，( 2 8 1 2 ) ，( 2 8 1 3 ) 和( 2 8 1 4 ) 我们有 g 坼，? r - 2 ，”f + l ，v l 竺k 1 ，3 + e 前者蕴涵着w ( v l + l 蜥一j ) = 叫( 珥一l 嘶) = w l ，后者蕴涵着w ( v l + l v r 一2 ) = w ( v l v i + i ) = w 2 ，矛盾i 所以，v r - 2 v ，岳e ( g ) 由于w ( v l v ，一1 ) = w 1 w 2 = t u ( f i + 1 ) ，贝u 那么，我们有 和 g 【伽“v l ，钆+ 】1y r 一1 ) 芒k i ，3 或k 1 ，3 + e q 一1 t n + 1 e ( g ) 钆一1 y r 一1 e ( g ) ( 2 8 1 6 ) ( 2 8 1 7 ) 现在我们考虑一l 珥e ( 6 ) 和地一1 y r 譬e ( c ) 两种情况 如果耽1 ，- e ( g ) 、根据( 2 , 8 ，u ( 2 81 。3 ) 和( 2 8 1 ，6 ) ，我们有 g 坼，u 2 1 ，讪，v l + l 】兰k 1 ，3 十e 这表明 ( u h 讪) = ( 砷一l 阱) 那么，讪”m v r - l v l y 2 研一1 珥+ 】是 一条重路，与论断2 2 矛盾! 硕士学位论文 m a s l e r s1 t h e s i s 如果叻一l v ，隹e ( g ) ，根据( 2 8 1 ) 和( 2 8 1 7 ) ，我们有 g 计，阱一1 v l ，q 1 ) 兰k 1 ，3 + e 这表明u , ( v z l v l ) = w ( v l l 阱一1 ) 那么，v l v ! + 1 一1 研一l v l 一2 l 脚蜥+ 是一条重路，与论断2 2 矛盾! 论断2 8 1 证毕口 下面我们将继续论断2 8 的证明 根据z 和r 的选取，我们有 功砷+ 】e ( g ) ，v l v r 一1 e f g ) ，地畔e ( g ) f 2 8 2 ) 因为w ( v l v l + 1 ) = w l ，w ( ? ) l v l + 1 ) = 叫2 ，所以 且 g 饥，钟+ 1 ，矶，? j r 一1 薯k 1 ，3 十e g m ，”h 1 ，钆，坼 j 喾1 ( 1 ，3h - e 前者和( 2 8 2 ) 及论断2 8 ，l 一起蕴涵着 v t v r l e ( c ) 后者和( 2 81 ) 及( 2 8 2 ) 一起蕴涵着 v l + 1 珥譬e ( g ) 1 8 ( 2 8 3 ) ( 2 8 4 ) 硕士学位论文 m a s t e r st h e $ i s 现在，根据( 2 82 ) 和( 2 8 3 ) ，我们有g k ， ，“v l ， ，) 1 篁l ，3 + e ，因而 ( 们v r 一1 ) = w ( v l v r ) = 甜( 珥一1 珥) = w 2 注意到口l ( ”f + 1 ) n ( 口，) ，令i 是使得i f 和v i ( 廿m ) n ( 嘶) 成立的最大整数因为q 隹( 珥) ，所以i f 。由i 的选取知+ 1 譬n ( v z + 1 ) n n ( v ，) 那么，根据( 2 8 4 ) ，我们有 g f h 1 ，v i 功+ 】，协) 竺k i ，3 或局，3 + e 进而w ( v i v i + 1 ) = 叫( 地坼) 又因为 ( 阱一l 阱) = t i ) ( v l v ，1 ) ，所以 是g 中一条以为终点的重路，于是该重路的另外一个端点v l + ，满足( 十，) c 2 同理，因为制( 坼一l 讪) = w ( v l v l + 1 ) 和t d ( v l v ，) = ( 坼一1 v ，) ，所以 也是g 中一条以为终点的重路，于是该重路的另外一个端点v l + i 亦满足 d ”( v l + 1 ) c 2 则 由于d ”( + 1 ) c 2 ，d w ( v l 。1 ) c 2 和 g ( 佻，v i + 1 ，铆+ 1 ，v j 竺k t ，3 或k 1 ，3 十e v i + l v l + l e ( g )( 2 8 5 ) 那么，g 【 仇 h 1 v l + l ，珥) 型k 耶+ e 又由于耽+ 】萑n ( v l + 1 ) n ( 蜥) 故 1 9 硕士学位论文 m a s t e r st h e s i s 十1 珥e ( g )( 2 8 6 ) 图4 我们已经证明了d t m ( v t ) c 2 和护( 地+ 1 ) c 2 该结论和i f 一起蕴 涵着l 2 根据( 9 ) 和论断2 4 ，我们有 现砷e ( g ) 接下来，我们断言 硕士学住论文 m a s t e r st h e s i s v 2 u k 十l e ( g ) 假设v 2 ”+ l e ( g ) 根据论断2 7 和论断2 8 ，我们有 u f - 1 u k + 1 e ( a ) 根据论断2 9 ，我们有 v l v k + 1 茌e ( c ) f 1 2 1 ( 1 3 ) f 1 4 1 根据( 9 ) 和( 1 3 ) ，我们有g 【 u + 1 ， 2 ，v l ，”) 釜k 1 ，3 十e 根据( 9 ) ，( 儿) ，( 1 3 ) 和( 1 4 ) ，我们有g 。+ l ，v 2 ，v i ，v l + 1 ) 型k 1 ，3 + e 前者蕴涵着t - c ( v 2 v k + 1 ) = w ( v 1 饥+ 1 ) = 叫1 ，后者蕴涵着? d j ( v 2 v k 十1 ) = w ( u i u i + 1 ) = w 2 ，矛盾! 故( 1 2 ) 为真。 根据( 1 0 ) 和( 1 2 ) ，我们有a v k + 1 ，v k ，v 2 ，饥皇k 1 ，3 + e 根据( 7 ) ，( 1 0 ) ，( 1 1 ) ( 1 2 ) 和( 1 4 ) ，我们有g 【 女+ 1 ，y k ，耽， 2 ) 】掣k 1 ，3 + e 这表明 和 叫( 2 ) = w ( v 2 t ，k ) = ( v l v k ) = 叫( 仉 + 1 ) = 3 叫( y 2 v 1 ) = t u ( y l v k ) = w ( v k v k + 1 ) = w 3 硕士学位论文 m a s t e r st h e s i s 图5 该结论和( 3 ) 及甜渤一i v , ) = w 3 一起蕴涵营 是g 中一条以为终点的重路。于是，该重路的另外一个端点v l 一1 满足 d ”( v t 一，) 2 = is | ，从而g 不是1 - t o u g h 图，故g 是非哈密尔顿图如果我们将g 中边v 4 v s ，u 5 v 8 ，v 6 t ) 9 和v 7 v 9 赋予权值1 ，并将g 的其他边赋予权值3 ，那么g 满足条件( 1 4 ) 但不满足条件( 1 3 ) ，使得定理4 条件成立的最大常数c = 2 0 ， g 中最重圈v 2 u 4 v 5 v 3 v 7 口6 v 2 的权值为1 8 c 这表明定理4 中的条件“g 是 2 9 硕士学位论文 m a s t e r st h e s i s 拟正规赋权图”不能被( 1 4 ) 代替 总之，定理4 中的条件“g 是拟正规赋权图”既不能被( i - 3 ) 也不能被 ( 1 4 ) 代替 硕士学位论文 m a s t e r s1 - h e s i s 第五节后记 在定理4 中我们考虑的图为2 一连通图那么，对于更高连通度的图，定 理4 中的拟正规条件是否能去掉是一个十分有趣的问题事实上，z h a n g 等 人在 1 2 中已提出下述猜想 猜想5 ( z h a n g e ta l 1 2 ) 设g 是3 一连通赋权图，如果对任意的t ，钉v ( g ) d ( “，口) = 2 = 孛”l z d 若( ) ，d 苫( ) ) 之c 2 那么，g 中存在哈密尔顿圈或者存在一个权值至少为c 的圈 上述猜想用本文鲍方法并不能得到解决耍解决该猜想，还需全新的工具 和方法今后，我们将对有关此方面的问题进行更深入地探讨 3 1 硕士学位论文 m i a s t e r lst h e s i s 参考文献 1 j b e d r o s s i a np c h e ng ，a n d s c h e l pr h a g e n e r a l i z a t i o no ff a n sc o n d i t i o n f o rh a m i l t o n i d t y , p a n c y c l i d t y , a n dh a m i l t o n i a n c o n n e c t e d n e s s ：d i s c r e t em a t h 1 9 9 3 ，11 5 ：3 9 5 0 2 b e r m o n djc ，o nh a m i l t o n i a nw a l k s ，i n p r o c f i f t hb r i t i s hc o m b i n a - t o r i a lc o n f e r e n c e ，a b e r d e e n ，1 9 7 5 ，u t i l i t a sm a t h ( 1 9 7 6 ) ，4 1 5 1 f 3 】b o n d y ja l a r g ec y c l e si ng r a p h s d i s c r e t em a t h 1 ( 1 9 7 1 ) 1 2 1 1 3 2 【4 】b o n d yja ，m u r