（运筹学与控制论专业论文）图中有关x圈（路）的一些结果.pdf

摘要 设g = ( v e ) 为n 个点的三连通图，令x v ( g ) c 为g 中的圈，如果对 于g 中任意的圈c 都有l xnv ( c ) i l xnv ( c 引，则称圈g 为x 一最长圈我 们用乜( g ) 表示图g 的独立数，n ( x ) 表示g x 】的独立数当k q ( x ) 时g k ( x ) 表示x 中能组成独立集的k 个点的度和( 在g 中) 最小值；当 n f x ) 时 令0 k ( x ) = a ( n n ( x ) ) 设x v ( a ) ，p 为图g 中的路，如果x y ( 尸) ，则 称p y g x - 路如果n 为正整数且有礼= 坠i n i 且l n i 2 ( 1si ) ，其中m ( 1 is ) 均为整数，则称( “l ，n 2 ，n k ) 为n 的一个k 一分解 在 4 中邹园提出如下结论：g 为n 个点的三连通图，g 为g 中的最长圈， r = c c ，如果口4 ( g ) n + 6 ，那z , a 嗣中任一连通分支日都满足t v ( h ) 2 我们可以对条件中的吼( g ) 进行改动，即取v ( a ) 的一个子集x ，将0 4 ( g ) 改进 为0 4 ( x ) ，同时对结论作进一步的讨论得到本文的第一个结论：g 为个点的 三连通图，xc o _ v ( g ) ，c 为一个x 一最长圈，如果a 4 ( x ) n + 6 ，那么对于g e 的 任一连通分支日，有i v ( h ) nx 2 ，而且恰含两个x 中的点的连通分支不会 含x 外的点易见此结论为 4 】中邹园结论的推广 在 8 中e n o m o t o 等人提出：g 为n 个点的连通图，如果有盯3 ( g ) ”或q f g ) 2 ，则g 有哈密尔顿路或g 中的最长圈均为强控制图我们对此结论 的一部分进行改进，得到本文第二个结论：g 为n 个点的连通图，xcy ( g ) ，如 果a ( x ) s2 ，那么g 有x 一路可见本文第二个结论推广了e n o m o t o 的定理的部 分结论 在 6 】中陈耀俊等人给出结论：g 为n 个点的连通图，如果0 - 3 ( g ) ( 3 n 一 5 ) 2 ，那么g 有哈密尔顿路，对其进行改进得到本文的第三个结论：g 为n 个点 的连通图，x v ( g ) ，如果0 3 ( x ) ( 3 n 一5 ) 2 ，那么g 有x 一路此结论为陈耀 俊等人结论的推广 同样，在7 中r o b e r tj a h a n s s o n 给出：g 为n 个点的连通图，给定7 , 的 个k 一分解( n l ，r 1 2 ，n ) 且m ( 1si ) 均为奇数，如果g 有路p 使得协， v ( g ) _ 【，( 尸) 在p ：都没有相继的邻点r d e ( v ) 【n i 2 j + 【n 2 2 j + + l n 2 j ， 那么g 有点数分别为1 1 , 1 ，n 2 ，n 的点不交的路改进此结论可得本文的第 四个结论：g 为n 个点的连通图，x ( g ) ，i x i = 8 ，( 8 1 ，s 2 ，s k ) ；h s 的一 个七一分解且黾( 1 i ) 均为奇数，设g 有路p 使得对任意x x v ( p ) 都 摘要 有l n p ( x ) nx i l s l 2 j - 4 - l s 2 2 j + + 【s k 2 j 且z 在p 上不会有相继邻点都 在x 中，那么g 有点不交的路p l ，马，最使i 只n x i = s 。( z = 1 ，2 ，七) 易 见r o b e r tj a h a n s s o n 的结论为本文的第四个结论的推论 在最后一章，我们提出了一些在今后研究中可以思考的问题 关键词：三连通图；x 一圈；x 一路；x 一最长圈；x 一最长路；x 一控制 圈；x 一控制路；x 一可圈图；度和：k 一分解；吼( x ) a b s t r a c t l e tg = ( ve ) b ea3 - - c o n n e c t e dg r a p ho nnv e r t i c e sa n dx y ( g ) ac y c l eco f gi sx l o n g e s ti fi xny ( g ) l f xnv ( c ? ) if o re v e r yc y c l ec 7o f g b ya ( g ) w e d e n o t et h ei n d e p e n d e n c en u m b e ro fg ，b yo 啤) t h ei n d e p e n d e n c en u m b e ro fg x a n db ya k ( x 1t h em i n i m u md e g r e es u m ( i na o f a n ykp a i r w i s en o n a d j a c e n tv e r t i c e s o f xw h e nk q ( x ) ，f o rk a ( x ) ，w es e t 盯k ( x ) = k ( n a ( x ) ) ap a t hpo f gi s c a l l e da x p a t h i f x c _ v ( p ) ( n t ，t l 2 ，n ) i sc a l l e d a k - p a r t i t i o n o f n i f n = 坠l z i a n d n i 2 ( 1 i 七) ，w h e r e n i ( 1 i 尼) a r ea l l i n t e g e r s i n 【4 】，y u a nz o ug i v e st h ef o l l o w i n gc o n c l u s i o n ：gi sa3 - c o n n e c t e dg r a p ho n n v e r t i c e s ，ci sal o n g e s tc y c l eo f g ，r = g c i f o - 4 ( g ) n + 6 ，t h e nf o re v e r yc o m p o n e n t h o f g fr 】，1 v ( h ) ls2 w ec h a n g e 以( g ) i n t h ec o n d i t i o n ，t h a ti s ，l e tx v ( g ) ， w ec h a n g e 吼( g ) t o 吼( x ) ，t h e nw ec a ng e ta ne x t e n s i o no f t h ec o n c l u s i o no f y u a n z o u ：gi sa3 - c o n n e c t e dg r a p ho nnv e r t i c e s ，x y ( g ) ，ci sax l o n g e s tc y c l eo fg ， r = o c i f 口4 ( x ) n + 6 ，t h e nf o re v e r yc o m p o n e n tho f e r r l ，j v ( h ) nx i 2 a n de v e r yc o m p o n e n tw h i c hc o n t a i n st w ov e r t i c e si nxc a nn o tc o n t a i n sv e r t i c e si n v ( g ) x t h i s i st h ef i r s tc o n c l u s i o no ft h i sp a p e r i n 8 】，e n o m o t og i v e st h a tgi sac o n n e c t e dg r a p ho nnv e r t i c e s i fa 3 ( g ) 三n o r ( g ) s2 ，t h e ngh a sah a m i l t o np a t ho re v e r yl o n g e s tc y c l eo fg i ss t r o n g l y d o m i n a t i n g w ei m p r o v ep a r to f t h i sc o n c l u s i o n ，t h e nw eg e tt h es e c o n dc o n c l u s i o n o f t h i sp a p e r ：gi sac o n n e c t e dg r a p ho nnv e r t i c e s ，x v ( g ) i f a ( x ) 2 ，t h e ng h a sa x p a t h i n 6 】，y a o j u nc h e ng i v e st h a tg i sac o n n e c t e dg r a p ho nnv e r t i c e s ，i fc r 3 ( g ) f 3 n 一5 ) 2 t h e n g h a sa h a m i l t o n p a t h w e c a n i m p r o v e t h i sc o n c l u s i o n t o g e t t h e t h i r d c o n c l u s i o n ：g i sac o n n e c t e d g r a p h o n n v e r t i c e s ，x v ( g ) i f o - 3 ( x ) ( 3 n 5 ) 2 ， t h e ngh a sa x p a t h o b v i o u s l y , t h i sc o n c l u s i o ni sa ne x t e n s i o no ft h ec o n c l u s i o no f y a n j u nc h e n s i m i l a r l y , i n 7 】，r o b e r tj a h a n s s o ng i v e st h a tl e tg b eac o n n e c t e dg r a p hw i t hn v e r t i c e sa n d ( n l ，t l 2 ，n k ) i s a k - p a r t i t i o n o f n ，w h e r e a l l ”a r e o d d p o s i t i v e i n t e g e r s s u p p o s e f u r t h e r m o r et h a tgc o n t a i n sa p a t hps u c ht h a te v e r yv e r t e xv e v ( g ) v ( p ) h a s n ot w oc o n s e c u t i v en e i g h b o r so i lpa n ds a t i s f i e sd p ( v ) l n l 2 j + l n 2 2 j + a b s t r a c t 【, 2 k 2 j ，t h e n g c o n t a i n s v e r t e x d i s j o i n t p a t h s o f o r d e r s7 7 , 1 ，札k w ec a n i m p r o v e t h i s c o n c l u s i o nt og e tt h ef o u r t hc o n c l u s i o n ：gi sac o n n e c t e dg r a p hw i t hn v e r t i c e s ，x v ( g ) ，i x t 2 s ，( 8 1 ，8 2 ，s k ) i sak - p a r t i t i o no f s ，w h e r ea l l8 ia r eo d dp o s i t i v ei n t e g e r s s u p p o s ef u r t h e r m o r et h a tgc o n t a i n sap a t hps u c ht h a te v e r yv e r t e xx x v ( p ) h a sn ot w oc o n s e c u t i v en e i g h b o r si nxo npa n ds a t i s f i e sl p ( ) nx i 【s 1 2 j + l s 2 2 j + + 1 2 j ，t h e ng c o n t a i n sv e r t e xd i s j o i n tp a t h sp 1 ，p 2 ，最s u c ht h a t 只n x i = s i ( i = 1 ，2 ，尼) w ec a ns e e t h ec o n c l u s i o no f r o b e r tj a h a n s s o n i sa c o r o l l a r yo f t h i sc o n c l u s i o n i nt h el a s tc h a p t e r , w eg i v es o m ep r o b l e m sf o rd e e p e r s t u d y k e yw o r d s ：3 - c o n n e c t e dg r a p h ；x c y c l e ；x - p a t h ；x l o n g e s tc y c l e ；x - l o n g e s t p a t h ；x _ d o m i n a t i n gc y c l e ；x _ d o m i n a t i n gp a t h ；x - c y c l a b l eg r a p h ；d e g r e es u m ；k - p a r t i t i o n ；o k ( x ) 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表 或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名 日期 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版： 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标 题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名 日期 刖舌 在图论中，有以下经典的结论，即 定理l ( d i r a e 2 ) a 3 b n ( n 3 ) 个点的图且6 n 2 ，则g 为啥密尔顿图 定理2 ( v c h v 丘t a la n de r d 洳1 1 4 1 ) g 为至少三个点的网i t a ( a ) k ( g ) ， 则g 为哈密尔顿图 如果将以上定理中的条件进行如下改i j f 取y ( g ) 的一个子集置将关于 图g 的条件换成类似的关于图g 【吲的条件，可得到更好的结论以下两个定 理即依此方法对上述定理作出改动得到的更，“泛的结论 定理3 ( b b o l l o b a n dg b r i g h t w e h 1 0 l ，s h i l l l l ) g 为n 个点的二连通图 且x y ( g ) ，如果6 ( x ) 礼2 ，那么g 为x 一可圈图 定理4 ( h a j ob r o e r s r n a , h a ouj i a n p i nl i , f e n gt i a n ，h e n kj a n v e l d m a n 1 3 ) g 为二连通图g x y ( g ) ，如果o ( x ) sk ( x ) 那么g 为x 一可 圈图 当定理3 中的x 取y ( g ) 时，得到的结论即定理1 ；当定理4 中 的x 取矿( g ) 时，得到的结论即定理2 ，所以可以说定理3 ，4 分别为定理l ，2 的推论 至此，我们不禁要闯：是否每一个定理都可通过类似方法加以改进? 然而，答案是否定的例如 定理5 ( d b a u e r , h j b r o e r s m a ，i l l ia n dh j v e l d m a n l l 5 1 ) g 为n 个点的 二连通图g a a ( c ) n + k ( g ) ，则g 为哈密尔顿图 由上述方法，我们自然想到是否可将其改进为 ( 1 ) g 为佗个点的二连通图，x v ( a ) 且( x ) 仃+ k ( g ) ，则g 为x 一可 圈图 然而，结论( 1 ) 结论并不成立，n a i ob r o e r s m a 等人给出下述更弱结 论( 2 ) 的反例 ( 2 ) g 为7 1 , 个点的二连通罔，x v ( g ) r a 3 ( x ) n + 6 ( g ) 则g 为x 一可圈 图 反例：有完全二部图玩，+ 1 ( 4 ) ，加上一点 ，使 恰好与凰k + 1 中每 部中的一个点相邻，记得到的新图为g ，取x 为k k k + 1 中较大的一鄢，显 然g 没有x 一圈，但印) = 3 k 2 k + 4 = ( g ) i + 6 ( g k ) 由此可知，并不是每个定理都可将条件中的y ( g ) 改为x v ( a ) 加以 改进，而是要通过严格的证明不断加以改进，定理6 可改进为 定理6 ( h a j ob r o e r s m a , h a ol i , j i a n p i nl i , f e n gt i a n ，h e n kj a n v e l d m a n 1 3 ) g 为n 个点的二连通图且x y ( g ) ，如果观( g ) n + m m k ( x ) ，j ( x ) ，那么g 为x 一可圈图 我们可以用此方法来对其他论文进行改进，看看能否得到更好的结论 定理7 ( - 刍g n l 4 1 ) g 为n 个点的三连通图，c 为g 中的最长圈，r = g a 如 果吼( g ) 礼+ 6 ，那么g 【r 】中任一连通分支日都满足i v ( h ) i 2 本文第一个结论定理a 的第一个结论即对定理7 的推广 定理ag 为n 个点的三连通图，x y ( g ) ，c 为一个x 一最长圈，如 果a 4 ( x ) n + 6 那么对于g c 的任一连通分支日，有i v ( h ) nx i 2 ，而 且恰含两个x 中的点的连通分支不会含x 外的点 我们可以试着对其它定理进行改进 定理8 ( e n o m o t o ，h ，k a n e k o ，t u z a ，z s 1 8 1 ) g 为n 个点的连通图，如果 有( g ) n 或a ( g ) 2 ，则g 有哈密尔顿路或g 中的最长圈均为强控制圈 本文的第二个结论定理b 即对定理8 的部分结论的推广 定理bg 为n 个点的连通图，x y ( g ) ，如果a ( x ) 2 ，那么g 有x 一路 定理9 ( y a o j u nc h e n ，f e n gt i a n ，a n db i n gw e i1 6 1 ) g 为n 个点的连通图， 如果a 3 ( g ) ( 3 n 一5 ) 2 ，那么g 有哈密尔顿路 本文的第三个结论定理c 即对定理9 的推广 定理cg 3 n 个点的连通图，x y ( g ) ，如果a 3 ( x ) ( 3 n 一5 ) 2 ，那 么g 有x 一路 同样，有 前占 定理1 0 ( r o b e r t j a h a n s s o n 7 ) g 为n 个点的连通图，( n l ，n 2 ，n k ) 为扎的 一个k 一分解目t n i ( 1 i ) 均为奇数，如果g 有路p 使得协 y ( g ) y ( p ) 在p 上都没有相继的邻点j l d p ( v ) 【n l 2 j - 4 - 【n 2 2 j + + 【n k 2 j ，那么g 有点数分别为n 1 ，n 2 ，n k 的点不交的路 本文的第四个结论定理d 即对定理1 0 的推广 定理dg 为n 个点的连通图，x y ( g ) ，f x f = 岛( 8 1 ，s 2 ，船) 为s 的一 个k 一分解且矗( 1 i ) 均为奇数设g 有路p 使得对任意z x y ( p ) 都 有i n p ( x ) nx f2 卜i 2 j + 【s 2 2 j + + 【s k 2 j 且z 在p 上不会有相继邻点都 在x 中，那么g 有点不交的路p l ，岛，r 使1 只n x f = & 0 = 1 ，2 ，) 定理l l ( o r e1 3 1 ) g 为n ( n 3 ) 个点的图，如果对任意“， y ( g ) ，u u 隹 e ( g ) 都有d ( u ) + d ( v ) 2 则g 为哈密尔顿图 本文的第五个结论定理e 即对定理1 1 的推广 定t $ e g 为n 个点的二连通单图，x v ( c ) n l x i 3 ，如果对任 意z 1 ，z 2 x r z l z 2 隹e ( g ) 都有d ( x 1 ) + d ( x 2 ) 则g 为x 一可圈图 易见当定理e 中的x 取y ( g ) 时，得到的结论即定理1 1 筑l 尊一此定义 第1 章一些定义 本文讨论的图都是无向的简单图，未定义的术语和记号参见1 1 1 定义1 图g = ( y ( g ) ，e ( g ) ，忆一) ，其中y ( g ) 为非空点集，e ( g ) 为 与y ( g ) 无关的边集，荜l g 为联系g 中的边和一对无序顶点的关联函数 定义2 一条边的端点称作与此边相关联，与同一条边相关联的两点称 为相邻的点 定义3 环即具有同一端点的边，重边即两个相邻顶点之间不止一条 边简单图即无环无重边的图 定义4 图g = ( y ( g ) ，e ( g ) ，c a ) ，如果v ( a ) = x u y 且x n y = 0 ，g 中 任意一条边的两个端点一个在x 中一个在y 中，则称g 为二部图 定义5 对于二部图g = ( y ( g ) ，e ( g ) ，妒g ) ，v ( a ) = x u y 且x n y = o ， 如果x 中的每个点都与y 中的所有点相邻，则称g 为完全二部图 定义6 图g 中点 的度d g ( ) 即图g 中与点口相关联的边数，6 ( g ) 为图g 中 点度最小值，( g ) 为图g 中点度最大值 定义7n o ( z ) 表示点z 在图g 中的邻点的集合，简记作( o ) 如果j 4 和b 为矿( g ) 的子集，则n s ( x ) = n ( x ) nb ，n ( a ) = u 。a ( z ) ，b ( a ) ；n ( a ) n b ，且有d ( x ) = i ( o ) i ，d s ( z ) = i n b ( z ) i ， 定义8 圈g 中x y ( g ) ，g x 称为图g 的导出子图，其顶点集为x ， 边集为g 中两端点均在x 中的所有边的集合且保持在g 中的关联关系 定义9 图g 中，s 为v ( a ) 的子集，如果s 中任意两点在g 中都不相邻， 则称s 为独立集；如果对于g 的任一独立集s ，都有i s f i s i ，则称s 为g 的 最大独立集q ( g ) 为图g 中最大的独立集中的点数，简称独立数：当x v ( g ) 时a ( x ) 表示g x 1 的独立数 定义1 0 图g 中的点割y 7 即y 7 v ( g ) f l a v 7 不连通七一点割即k 个元 素的点割图g 的连通度k ( g ) 为图g 中的所有k 一点割中k 的最小值当x y ( g ) 时，k ( x ) 表示a i x l 的连通度 定义l l 当k o ( x ) 时吼( x ) 表示x 中能组成独立集的k 个点的度和 ( 在g 中) 最小值；当k o 伍) 时令吼( x ) = 七( 佗一n ( ) ) 鼐i 荜一“定义 在定义9 中，当x = v ( g ) 时，盯忧) = 盯( g ) 关于用口k ( g ) ( , t k ( x ) ) 的条 件推出g 有哈密尔顿圈( x 一圈) 的结论很多，详见参考文献1 4 1 1 1 3 1 1 1 5 1 1 2 0 1 定义1 2 图g 中的路即有限非空序列p = v o e l v l e 2 v 2 e k v k ，其中地为不 同的点( o i ) ，为不同的边( 1si 女) ，1 3 i 的端点为咙一1 和口p 设u ，v y ( g ) ，图g 中的( 让， ) 路即以u 为起点以 为终点的路 定义1 3 图g 中的迹即有限非空序列p = r o e l v l e 2 v 2 e k v k ，其中8 i 为不 同的边，e i 的端点为也一l 和吨( 1 i ) l 图g 中的圈c 即起点和中问点不同 的闭迹 定义1 4g 为图g 中的圈，用矽表示给定圈e 一个方向如果y ( e ) ， 则”+ 表示。沿万方向的第一个后继点，口一表示 沿召方向的第一个前继 点：”+ 2 = 扣+ ) + ，口- 2 = ( v - ) 一；依次类推 ”，f 另有畦( z ) = + i u r ( z ) 定义1 5c 为图g 中的圈，u 刁 表示c h 沿c 给定的方向从札到u 相继的 点集，也可看为g 的子图： 虿札表示c 上沿c 给定方向的反方向从u 到u 相继 的点集，也可看为g 的子图 定义1 6 设x y ( g ) ，p 为图g 中的路，如果x y ( p ) ，则称p 为x 一路 定义1 7 设x 矿( g ) ，c 为图g 中的圈，如果x y ( e ) ，则称c 为x 一圈 定义1 8 设x y ( g ) ，如果图g 有x 一圈，则称图g 为x 一可圈的 由定义1 8 可知，当其中x = y ( g ) 时，x 一圈即为哈密尔顿圈，故有很多 关于x 一圈的结论，详见参考文献1 1 0 1 1 1 1 h 1 2 l i l 3 i l l 6 l i l 7 l l l 8 j 定义1 9 设x 矿( g ) ，p 为图g 中的路，如果对于g 中任意的路p ，都 有j xny ( p ) j i xny ( p ，) | ，则称p 为x 一最长路 定义2 0c 为图g 中的圈，如果对于g 中任意的圈都有i v ( c ) l i v ( c ) l ，则称c 为最长圈；设x y ( g ) ，c 为图g 中的圈，如果对于g 中 任意的圈都有i xny ( c ) l 1 xnv ( c ，) l ，则称c 为x 一最长圈 如果对圈c 外的x 中的点作进一步讨论，可得如下定义： 定义2 l 设x v ( g ) c 为图g 中的圈，如果x y ( c ) 中的点的邻点都 落在c 上，则称e 为x 一控制圈 定义2 2e 为图g 中的圉，如果g c 中的点均为孤立点，则称e 为强控制 圈 关于控制圈和强控制圈有很多结论，详见参考文献f 1 9 儿2 0 i 【2 2 j 【2 3 l f 2 4 i 毵1 督一“定义 定义2 3g 为罔g 中的圈，设x y ( g ) ，则m ( e ) 表示g y ( c ) 中与至少 一个x 中的点相关联的边的集合 定义2 4 ( n l , 礼2 ，n ) 称为n 的一个一分解即n = 叁l 啦且啦2 ( 1 i 七) ，其中m ( 1 i 七) 均为整数 定义2 5c 为图g 中的圈，p 为图g 中的路，如果尸和圈c 的交点仅为p 的 两个端点，则称尸为e 一旁路 定义2 6 图g 中的任意两条路如果只可能在端点相交，则称它们为内不 交的 定义2 7 地口为图g 中的两点，如果g 中有路连接屿f 两点，则称u 两点 连通将y ( g ) 分为，使得u ， 两点连通当且仅当u ，口在同一个集 合k 中，图g 的子图g m 】，g v 2 ，a v 。l 称为图g 的连通分支u ( g ) 表示g 的 连通分支的个数，简称连通分支数 第2 章主要结论及证明 2 1 定理a 结论及证明 定理ag 为几个点的三连通图，x y ( g ) ，g 为一个x 一最长圈，如 果c r 4 ( x ) n + 6 ，那么对于冗= g c 的任一连通分支日，有i v ( h ) n x l 2 ，而 且恰含两个x 中的点的连通分支不会含x 外的点 证明 首先证明引理，以下总假设g 为扎个点的三连通图 引理e 为图g 中的x 一最长圈，r = g a p 为e 一旁路且y ( p ) n v ( c ) = z l ，砘) ，设p 的方向为从z l 到砘且( y ( p ) y ( c ) ) n x o 则有 ( 1 ) z c z f n x 0 ，z 手c 。f n x o ； 故可设l 为z 否虿上第一个x 中的点，她为+ - u - 4 z f 上第一个x 中的点， s = 伽1 ，w - ，z 2 ，则又有 ( 2 ) t ) l ，蚴) 为独立集；设u l ( y ( 尸) y ( c ) ) nx ，则 札l ，加2 也为独立集； ( 3 ) 凡( w 1 ) n g r ( w 2 ) = n n ( u 1 ) n g a ( 蚍) = o ； ( 4 ) 当i ( y ( p ) y ( e ) ) n x l 2 时有g s ( 她) n ；( 叫1 ) = s ( 伽2 ) n i 2 ( 埘1 ) = ；( 叫2 ) n ；2 ( 1 ) = o 证明：( 1 ) 如果z 产刁虿n x = o ，则存在圈 c l 。2 , 1 p z 2 c z l 因为( y ( p ) y ( c ) ) n x d 且z 产虿n x = o ，故l v ( a ) n x i l v ( c ) n x | - 这与c 为x 一最长圈矛盾，故z - c 虿n x d 同理可知才c z ? n x o ( 2 ) ( 1 ) 如果叫l w 2 e ( g ) ，则存在圈 a ：枷1 苔砘z l 苓埘2 t j 1 因为( y ( p ) y ( c ) ) n x o 且z 方加f n x = o ，z 手苔呀n x = o ，故i y ( a ) n x l i v ( c ) nx 1 这与c 为x 一最长圈矛盾，故 叫l ，叫2 为独立集 铺2 章 娶纪论及h f 州 ( 2 ) 如果u l w 2 e ( g ) ，则存在圈 _-_ q = z l c z 2 p u l w 2 c z l 因为才召埘i n x = o ，故c 比c l 至少多一个x 中的点“l ，这与c 为x 一最长圈 矛盾，故 让l ，叫2 ) 为独立集 ( 3 ) ( 1 ) 设v l 冗( 1 ) n r ( 叫2 ) 则有圈 g = 钾l - d 钇, - p z l 孑研1 因为( y ( p ) y ( c ) ) n x o r z + - 新n x = d ，4 d 峨- n x ：o 故i y ( a ) n x i i v ( c ) nx 1 这与c 为x 一最长圈矛盾，i 坟n r ( w 1 ) n r ( 伽2 ) = 0 ( 2 ) 设也( u 1 ) n ( t 也) ，则有圈# q ：勿札1 t 1 2 2 苔沈 因为才才t 町nx ：谊敌q 比a 至少多一个x 中的点“1 ，这与e 为x 一最长圈 矛盾，故g 兄( u 1 ) nn r ( w 2 ) = o ( 4 ) ( 1 ) 设u l n s ( w 2 ) n ；1 ) ，则有圈 a = z 1 z 2 苓口 伽1 方口1 叫2 方z 1 因为( y ( p ) y ( g ) ) n x o l t z 才如fn x = d ，才苔町n x ：o 故 矿( a ) n x 1 i v ( c ) nx i 与g 为x 一最长圈矛盾，故 k ( 如2 ) n i ( w 1 ) = o ( 2 ) 设屹船( 她) n i 2 ( 叫1 ) ，则有圈 q = z l 忽孑口；- 1 - c v 2 w 2 - c z l 因为j ( y ( p ) y ( c ) ) n x i22 且z 产苔i n x = d ，z + - 方w 彳n x ：o 故l v ( c ) n x l i v ( c ) nx f 与g 为x 一最长幽矛盾，故| ) v s ( 她) n v i 2 1 ) = 0 ( 3 ) i v 3 i ( w 2 ) n 蟾2 ( 叫1 ) ，则有圈 g = z l - - _ + 2 + u - - u 32 叫l - d v + w 2 - d z l 钯2 章1 要封论硬证明 因为( y ( p ) y ( c ) ) n x 0 且z 刁埘f n x = o ，才d in x = o 故l v ( c 3 ) n x i i v ( c ) nx i 与c 为x 一最长豳矛盾，故；( 叫2 ) n ；2 1 ) = o 由上证明知引理成立 下面我们来完成定理a 的证明 先证明第一个结论 反证法：假设g 中的任意一个x 一最长圈都不满足结论，则设c 为g 中 的一个x 一最长闽j i m ( c ) 最小，f f 0 为c 外一个分支且i v ( h o ) nx i 3 设z l ，。2 ，z 3 v ( h o ) n x n x z j ( i j ，i ，j = 1 ，2 ，3 ) ，设凰中( z l ，z 2 ) 一路 为p 1 ，( x 2 ，x 3 ) 一路为 2 ，( z l ，x 3 ) 一路为b 由于g 为三连通图，故可知存在u 1 n c ( x 1 ) ，l j 2 n c ( x 2 ) ，蜘n o ( z 3 ) 且地吩，( i j ，i ，j = 1 ，2 ，3 ) 不失一般 性，可适当选择v l , v 2 ，蜘，使u 2 + - 。- - + 均中无z 1 的邻点，取v l 为z 1 在呀苓地中第 一个邻点 设”。为” 夸呵中第一个x 中的点；w 2 为” 才呵中第一个x 中的 点；w 3 为时才 f 中第一个x 中的点 令s l = l ，t c j ， 2 ； = 她，伽手，v 3 - s 3 = 蜘，叫手，v 1 ) ， 可知n o ( x , ) 岛u t j 2 ，v 3 ，简记m ( 屿) = 毫( 嘶) ( i ，j = 1 ，2 ，3 ) ，n 3 ( z 1 ) = n s s ( x 1 ) d a c 为x 一最长圈可知对于v u 口 c l ，v v 时e 地，v 伽时c w 3 ， 都有w 2 u ，w 3 1 t ，w i ，w 3 y ，w l w ，i i ) 2 w 隹e ( g ) 由引理( 3 ) 知在s l 中町2 ( 础- ) ”1 ) ，n 7 ( 蚴) ，1 ( ”2 ) 两两不交， 在s 2 中啊2 ( t ，2 ) 砚 ，f 1 ) ，2 ( 叫3 ) 两两不交， 在岛中坷2 ( 蚴) 地) ，f ( ”2 ) ，3 ( 叫1 ) 两两不交， 另外，时( z 1 ) 叫，w 2 ，w 3 - 与- 2 ( 均) ”3 ) ， ( 叫2 ) ， b 1 ) 两两不交，证 明如下： ( 1 ) 如果( 9 ( z 1 ) 础t ，w 2 ，w 3 ) n ( 铲( 蚴) u 3 ) ) o ， 设u l ( 寸( z 1 ) l ，w 2 ，叻) ) n ( i 2 ( 叫3 ) 珊 ) ，则有圈 c 。= u t z 。磊z 。”。苓u ：2 w 。苔札f 当j f l ，u z n x l i v ( c ) n x l ，与e 为x 一最长豳矛盾；当i “l ， ) n x l = 2 时，因为z l ，x 3 x ， 故c 1 的存在与m ( c ) 最小矛盾，故 ( z 1 ) n 婀2 ( 删3 ) u 3 ) = o ( 2 ) 如果( 寸( z 1 ) 埘- ，w 2 ，奶) ) n 盯( 她) d 设地( 尊( z 1 ) 叫l ， 2 ，w 3 ) n 町( 她) ，则有圈 c 2 = “i z l p 。, x 2 啦6 u - 您+ 叼u - + 也- - 因为z l ，z 2 x 且时苓叫in x = d ，故l v ( c 2 ) n x l i v ( c ) n x l 与c 为x 一最 长圈矛盾，故时( z 1 ) n 蚜( w 2 ) = o ( 3 ) 如果( 口( z 1 ) 叫l ，w 2 ，蜘) ) nn 3 ( w 1 ) d ， 设u 3 ( ( z 1 ) 叫1 ，w 2 ，w 3 ) n 、，3 扣1 ) ，则有圈 4 - - 一 q = 町2 ：1 1 ) 1c u 3 w le i 因为 d 叫f n x = o ，故1 y ( 岛) n x i i v ( c ) n x l 与c 为x 一最长圈矛盾， 放时( z i ) n 3 ( 1 ) = o 由引理( 1 ) ( 2 ) 可知在r e e ，r ( t j 1 ) ，r ( 她) ，n r ( 蚴) ， k ( z 1 ) ， z 1 ) 两两不交 简记d i ( w j ) = d s , ( ) ，( t ，j = 1 ，2 ，3 ) 则n = l y ( g ) f = f 矿( e ) f + f 冗i i 韪l + i s j i + i s j l + i r i f f 2 扣1 ) 1 ) u f ( 蚴) un i ( w 2 ) j + i i 2 ( 叫2 ) u 2 u i ( 伽1 ) u j ( 蚴) j + i 盯2 ) 姐) u 坷( w 2 ) u 3 ( 埘1 ) u ( 时( z 1 ) 叫l ，w 2 ，纰 ) j + i ( 1 ) u r ( 她) un r ( w s ) u ( z 1 ) u 扛l i = i f 2 ( 伽1 ) 1 ) 1 + l f ( m 3 ) i + i n i ( w 2 ) i + l f 2 ( 叫2 ) 口2 i + 1 f ( 叫1 ) i + l v j ( 叫3 ) i + j v f 2 ( 叫3 ) 口3 ) j + l ，吁( 叫2 ) j + j n 3 ( 钾1 ) i + j ( 哼 1 ) l ，伽2 ，叫3 ) ) j + i r ( 1 ) i + i n n ( w 2 ) i + i r ( 加3 ) l + l r ( z 1 ) 1 + i z 1 l d l ( w 1 ) 一1 + d l ( w 3 ) + d l ( w 2 ) + d j ( 忱) 一1 + , 2 ( 础1 ) + 如( z 如) 靴2 亭 要封论股证州 + 如( 叫1 ) 一1 + 如( w 2 ) + d 3 ( 伽1 ) + d c ( z 1 ) 一3 + d r ( w 1 ) + a a ( w 2 ) + d r ( w 3 ) + d r ( x 1 ) + 1 = d ( w 1 ) + d ( w 2 ) + d ( w 3 ) + d ( x 1 ) 一5 即d ( w x ) + d ( w 2 ) + d ( w 3 ) + d ( x 1 ) 行+ 5 由引理及上述证明知， 叫l ，w 2 ，w 3 ，x 1 ) 为x 中的独立集，故有 礼+ 5 d ( w 1 ) + d ( w 2 ) + d ( w 3 ) + d ( x 1 ) a 4 ( x ) n + 6 此矛盾说明定理a 的第一个结论成立。 下面证明定理的第二个结论，即恰含两个x 中的点的