（应用数学专业论文）二部竞赛图中圈的一些结果和问题.pdf

中北大学学位论文 摘要 本文主要进行二部竞赛图h 舢性质的研究在王建中【4 】提出了二部竞赛图为 琢血t o n 图的一个新充分条件及李桂荣在文【6 9 】提出二部竞赛圈为哈密顿图的一个充分条件 等前人所研究的主要结果的基础上，得到了一系列的h a m i l t o n ：部竞赛图的充分条件，还 对一类几乎正则二部竞赛图进行研究，找出它的路和田所具有的性质 第一章 概述图论研究的历史，提出本文的所做的工作 第二章 我们介绍了论文中涉及的一些基本的图论概念和术语 第三章 我们改进了前人的定理，具体讨论了一个二部竞赛图，当其满足特定条件时，是 h a m i l t o n i a n 并推出一些推论 第四章 我们研究了一类特殊的几乎正则二部竞赛图并得到关于这类图所包含路的一些结论 关键词：二部竞赛图；强连通；正则：几乎正则 第1 页 中北大学学位论文 a b s t r a c t i nt h i sp a p e r t h eh a m i l t o n i a nq u a l i t i e si nb i p a r t i t et o u r n a m e n ta s t u d i e d o nt h e b a s i so ft w on e ws u f f i c i e n tc o n d i t i o n sb r o u g h tu pb yw a n gj i a u - z h o n g 4 t h e tb i p a r t i t et o u r - n a m e n tw o u l db ed i r e c t e dh a m i l t o n i a ng r a p ha n das u f f i c i e n ta n de s s e n t i a lc o n d i t i o nb r o u g h t u pb ya na s s o c i a t ep r o f e s s o rl ig u i - r o n g x u ( 6 9 jt h a tb i p a r t i t e t o u r n a m e n tw o u l db ed i r e c t e d h a m i l t o n i a ng r a p ha n dr e s u l t so fo t h e rf o r f a t h e r s ，t h es u f f i c i e n tc o n d i t i o n sa b o u tb i p a r t i t e t o u r n a m e n tw i t hd i r e c t e dh a m i l t o n i a ng r a p ha l es h o w n i na d d i t i o n ，w et r yt of i n da n d p r o v es o m ec h a r a c t e r so nt h ep a t h sa n dc y c l e si na h n o s tr e g l l l a rb i p a r t i t et o u r n a m e n t ，s o m e t h i st h e s i sc o l l $ i s t so f4c h a p t e r s i t h e 缸tc h a p t e r ，w ew i l li n t r o d u c et h eb a c k g r o u n d 勰t h eb a s i cc o n c e p t s ，a n dm a i nr e s u l t so b t a i n e di nt h i st h e s i si sl i v e n i nt h es e c o n dc h a p t e r ，t h et e r m i n o l o g ya n dn o t a t i o n so ng r a p ht h e o r ya l ei n t r o d u c e d i nt h et h i r dc h a p t e r ，h a m i l t o np r o b l e m sa l ed i s c u s s e d w ep r o v eas u 伍c i e n tc o n d i t i o n f o rh a m i l t o n i a nc y c l e si nb i p a r t i t et o t t r n a m e n t s ，w h i c ha l eh s t e da sf o l l o v 们s ：i fa nn n b i p a r t i t et o u r n a m e n tts a t i s f i e st h ec o n d i t i o n s ：( i ) w 2 ) ，i flql + ir = 疗一1 ； ( i i ) w ( n 一3 ) ，i ffqf + lrf 行一1 ；t h e nt i sh a m i l t o n i a n ，e x c e p tf o rt h r e ee x c e p t i o n a l g r a p h s i nt h el a s tc h a p t e r w ef i n da n dp r o v es o m ec h a r a c t e r so nt h ep a t h sa n dc y c l e si n 第1 i 页 中北大学学位论文 a l m o s tr e g u l a rb i p a r t i t et o u r n a m e n t w h i c ha r el i s t e da 8f o l l o w s ：i fa nn na l m o s tr e g u l a r b i p a r t i t et o u r n a m e n tts a t i s f i e s 癖( t ) + 砧( t ，) = nf o re v e r ya r ct 口a ，t h e nt h a st h e 南 b y p a s sp r o p e r t y f o r 后= 3 ，5 ，7 ，佗一5 ，绍一1 ，u n l e s s i t s i s o m o r p h i c t oo e t eo f t h e g r a p h s f ( k 一1 ，七一1 ，七，七) ， 1 ， w em a i n l ys t u d yt h et r a c e a b i l i t yo fq t u m i - e l a w - f i e eg r a p h s k e yw o r d s ：b i p a r t i t et o u r n a m e n t ；s t r o n g ；r e g u l a r ；a l m o s tr e g u l a r 第m 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：日期； 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包 括：学校有权保管、并向有关部门送交学位论文的原件与复印件； 学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复 制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容 ( 保密学位论文在解密后遵守此规定) 。 签名：塑垒丝：日期：兰塑：至：! 导师签名： 鲥牛一 日期：丝晕篁兰2 中北大学学位论文 第一章引言 图论作为数学的一个分支，已有二百多年的历史。特别是在计算机的出现和摆动下。有 关图的理论有了迅速的发展，其应用也日益广泛。现在已经成为研究系统工程、管理工程、 计算机科学、通讯与网络理论、自动控制、运筹学以至社会科学等的一种重要的数学工具 图论的应用之所以如此广泛，在于它可作为分析处理多种问题的一种较为理想的数学模型， 它的算法又可借助计算机实现。因而图论与计算机相结合为图论的研究和应用开辟了广阔 的前景。 随着时代的发展，越来越多的科研工作者投入到基础学科的研究中来。图论，由于其 广泛的应用背景，近半个世纪以来一直是一个非常热门的研究颁域。图论可分为无向图和 有向图。无向图的研究已相当深入，结果也非常丰硕。上世纪7 0 年代以来，随着生产中许多 实际问题的提出，人们更多地转向予对有向图的研究。到目前为止，关于有向图的文献已 有3 0 0 0 多篇，它们不仅包含丰富的理论，也有许多重要的算法和应用。图论目前已成为研究 工程、管理、计算机、运筹学及网络通信等的重要和理想的工具。 在图论研究中，图中的圈结构是图的结构特征的一个重要部分。例如图的h m a i l t o n 圈， e l l l e r 迹，图的最长圈、最短圈和泛豳性，有向图中的有向圈，无固定向等研究内容以及图中 的圈与图的其它参数之间的关系一直是图论中的热门主题。在这些方面，有向图的研究显 得更为复杂，得到的结果和无向图相比，也要明显薄弱。 对于有向图的研究，多数文献集中于研究一类较特殊的有向图一多部竞赛图( 竞赛图的 推广) 。多韶竞赛图的路和圈一直是研究的焦点。于是多帮竞赛图趵h a m i l t o n 性也就自然地威 为一个研究重点，同时它也是一个较难的课题。1 9 6 6 年，m o o n i 正明了强连通竞赛图是顶点泛 圈的，这成为研究竞赛图的一个突破。m o o n 的 2 0 著作包含了n 一部竞赛图的一些最初的结 果。1 9 7 6 年，b o n d yl 研首先对多部竞赛图中的圈进行了研究。之后，g o d d a r d ，v o l k m a n ni o 司， g u of 5 6 】等人亦获得了若干该方面的结果。1 9 8 1 年，b e i n e k e1 3 1 】得到了关于二部竞赛图中路 和圈的一些结果。之后的几年里，二部竞赛图领域迅速的发展起来。 有限图的h a m i l t o n 圈问题因1 9 世纪爱尔兰数学家w i l l i a m r o w a nh a m i l t o n 而得名，它 可以看作是e i d e r 环游问题的一个延续，但是到目前为止h a m i l t o n 匿的菲平凡的充分必要条 件上没有找到，它是图论中尚未解决的主要问题之一。一个多世纪以来，人们从不同的角度 对这个问题进行研究得到了很多判断h a m i l t o n 圉的充分条件，例如著名的o r e 定理、f a n - 型 第1 页 中北大学学位论文 条件。对于有向图h a m i l t o n 眭的研究以及特殊图类的h a m i l t o n 生的研究，也是图论界一个比 较热门的问题，并且也取得了许多优秀的成果。竞赛图是一类非常有用的有向图，对于它 的h a m i c o n 性的研究有着十分重要的意义。 考察图中顶点的度是研究图的h a m i l t o n 眭的一个重要方法。设有向图d = ( k a ) 和口 y ( d ) 。我们分别用矿扣) 和d - ( v ) 表示在d 中的出度和入度。有向图的非芷则度i ( d ) = 。，：) i 矿( z ) 一d 一( ) i ，( 可能$ 。) ，若j ( d ) = 0 ，称d 是正则的- 若j ( d ) 1 r 称d 是几乎 正则的。y e o 首先对正则的多部竞赛图进行了研究并得到正则的多部竞赛图是h a m i l t o r d a n ， 此外，y 幻还定义了有向图的局部非正则度旬( d ) ；。m e 矿a ( x d ) i d + ( z ) 一d - ( z ) i ) 系如下面( d ) = m a x m a x ( d + ( x ) ，d - ( $ ) ) 一m i n ( d + ( y ) ，d 一妇) ) ：甄v ( d ) 和全局非正则度显然，三者关 i t ( d ) i ( d ) i g ( d ) 对于n 一部( n 5 ) 竞赛图d ，文献【5 8 】证明了若站( d ) s1 ，d 是h a m i l t o n i a n 。文献【6 7 l 证明 了几乎正则的竹一部27 ) 竞赛图是h a m i l t o n i 蛆。 1 9 8 9 年，r t t a g g k v 4 删y m 柚姻湖d b 在文【3 1 1 中首先给出h a m i l t o n 二部竞赛图的一个 等价命题。t ( 竹，竹) 是h 卸m t o n 当且仅当t ( n ，n ) 是强连通的，且它含有一个2 - 因子此定理 有很重要的理论意义，但寻求t ( n ，n ) 的一个2 _ 因子非常困难，因此寻求h a m i l t o n - - 部竞赛 图的些简明判别条件是有意义的问题。 如果t ( n ，n ) 满足条件：伽岳e 号d + ( + d - ( ) 则称t ( n ，竹) 满足0 ( k ) 条件。如 果t ( n ，n ) 满足条件：珊e 辱d + ( v ) + d - ( 口) k 贝l j y l s t ( n ，哟满足w ( ) 条件。在此基础上，我 们得到了一系列的h a m i l t o n - - - 部竟赛图的充分条件，1 9 9 2 年，王建中t 4 1 得到了如果t ( n ，n ) 满足m 一1 ) 条件贝l j t ( n ，n ) ；是h a m i l t o n 除非r ( n ，n ) 掣t ( 4 笋，警，孚，咛) 2 i t ( n ，n ) 垒 t ( 2 ，警，2 ，孚) 。1 9 9 3 年李桂荣在文【6 9 】中得到了如果t ( 仉n ) 满2 = w 伽一2 ) 条件，贝l j t ( n ，n ) 是h a m i l t o n 除非t ( n ，n ) 望t ( 1 + 2 ，；， 一f 一2 ，n 1 ) 或r ，n ) 掣t ( 2 + 1 ，z ，n f l ，仙一1 ) 我们将进一步考虑如果r ( 竹，n ) 满足一3 ) 条件，r ，乱) 是h 卸埘t o n 时的情况，着重刻 画t ( n ，仃) 不满足h a m i l t o n 时的图族。1 9 9 6 年王建中在文【2 8 0 中得到了如果t 0 ，q ) 满足d ( n ) 条件，则t ( p ，q ) 中包含一个圈长至少为2 m i n n + l ，p ，口) 的圈，除非n 是偶数r t 同构与 图君( ，如，衫2 ) 之一，2 0 d 4 年，v o l k m a a n1 6 6 】给出了几乎正则二部竞赛图中每条弧均包 含在条h a m i l t o n i v a 路中等价命题。 本文一方面在前人得到的一系列h 锄n t o n 二部竞赛图的充分条件的基础上进一步弱化 条件着重刻画出在一3 ) 条件下不满足h a m i t o n 眭的- ：部竞赛图的i 虱族以及在o 一3 ) 第2 页 中北大学学位论文 条件下二部竞赛图的h a m i l t o n 性，并将其推广到多部竞赛图，对其条件进行改进，这部分内 容将在第三章详细讨论。 另一方面对一类几乎正则二部竞赛图进行研究，找出它的路和圈所具有的性质，这部 分将在第四章中讨论。 1 1 本文主要的工作 本文共分四章，从内容上讲，主要是由二部分组成。第一部分为二部竞赛图的l 王| 珊n t o n 性 质的研究。第二部分为关于一类二部竞赛图中路与圈的研究 在第二章，我们介绍了一些关于二部竞赛图的概念。 在第三章中，我们改进了前人的定理，证明了对与一个二部竞赛图，当其满足特定条件 时，是h a m i l t o n 图并推出一些推论。 在第四章中，我们研究了一类特殊的几乎正则二部竞赛图并得到关于这类图所包含路 的一些结论。 第3 页 中北大学学位论文 第二章有关二部竞赛图的预备知识 2 1 基本概念 一个图g 是指一个有序三元组( y ( g ) ，e ( g ) ，皿g ) ，其中y ( g ) 是非空的顶点集，e ( g ) 是 边集，而是关联函数，它使g 的每条边对应于g 的无序顶点对。若e 是一条边，而t ，口是 使皿o ( e ) = 伽的顶点，则称e 连接“和口，顶点胡铂口称为e 的端点。 条边的端点称为与这条边关联，与同一条边关联的两个顶点称为相邻的，与同一顶 点关联的两条边也称为相邻的。端点重合为一点的边称为环。两条边若有相同的端点，则这 两条边称为重边。 图日，如果矿( 日) y ( g ) ，e ( 日) e ( g ) ，并且皿日是皿g 在e ( 日) 上的限制则称日是g 的 子图。当日g ，日g 时，称日是g 的真子图。如y ( 日) = y ( g ) ，则称日是g 的生成子 图。g l 和岛是g 的子图，若g l 和g 2 没有公共顶点，则称它们是不相交的。若g l 和g 2 没有公 共边，则称它们是边不重的。 图g 的一条途径是指一个有限非空序列w = r o e l y l e , 2 v 2 它的项交替地为顶点和边， 使得1 i k ，边矗的端点是仇一1 和仇，v k , t - 蜀j 称为w 的起点和终点而”l 一1 称 为的内部顶点，称为的长。 若途径的边o l ，e 2 ，互不相同，则w 称为迹。 若途径的顶点 1 ，v 2 ，饥互不相同，则称为路。 图g 的两个顶点t ，口问如果存在( t ，口) 路，则称铭和v 连通的，图g 的顶点集y 有一分类：k ， k ，k 使得两顶点钍和 是连通的，当且仅当它们属于同子集k ，则由k 中顶点以及 边( 取g 中这些顶点问拥有的边) ，组成的子图，记为g 陬】，则g 陬】，g 【吲，g 【吲称为g 纳 分支。 若g 只有一个分支，则称g 是连通的，否则g 是不连通的。若一条闲迹的起点和内部顶 点互不相同，则称它为圈，长为后的圈称为后圈。当为奇数时，则圈是奇圈：当j c 为偶数时， 则七圈是偶圈。在图g 中，最短圈的长度称为g 的圈长。 本文涉及的图都是有向简单图，图论的基本概念和记号可参考【3 】。在本节中，将介绍文 中将要频繁使用的些定义和符号。一个图，如果它既没有环也没有重边，则该图称为简单 图。 第4 页 中北大学学位论文 设g 是一个图，而n = i y ( g ) i 称为图g 的阶。圈g 中的圈d 称为极大圈，如果不存在g 中 的圈，使得矿( ) ) y ( g ) 。 另外为了方便起见，在不引起混淆的情形下，有时用图的子图的相同记号来表示其顶 点集 对于g 的子图或子集w 和u ，令胍，( w ) = n ( w ) nu 设日是连通图g 的子图，而 毛) n ( h ) y ( 点砷，z h y 表示其内点全部在日中的最长 的仁，们路 囤g 的顶点 的度：是指g 中与。关联的边的数目，记：如( 口) ，用6 ( g ) ，( g ) 分别表示g 的 顶点最小度和最大度。有向图d 的最小出度( 最小入度) 为 扩( 研= r a i n 姑：z y ( d ) ，( 6 一( d ) = r a i n 蝠( 功：z y ( d ) ) d 的最小度为 码= m i n 酷，蛄) 类似的，我们可以定义d 的最大出度+ ( d ) 、最大入度一( d ) 和d 8 9 1 大度。 o ( d ) = n l a x a + ( d ) ，一( d ) 称s 为g 的一个独立集，如果s 是y ( g ) 的一个子集，且s 中任意两个顶点在g 中均不相 邻 设有向图d 为简单有向图。如果它的任一顶点的出度和入度都等于某一非负整数k 。则 称为k 一度正则有向图。称有向图d 是严格有向图如果它没有环，并且任何两条弧都不具有 相同的方向和相同的端点。 称岛，岛，最为集合s 的一个划分，如果对于所有的1 t j t ，s n 岛= 口且u 名1 & = s 设d 为一个有向图，称d 是强连通的，如果对于d 中每一对不同的顶点卫和! ，d 中均存 在一条( 吲) 一途径和( 玑每) 一途径。有向图的非正则度j ( d ) = 。罂鼢) i d + 缸) 一矿( ) i ) ( 可 髓= 们。若i ( d ) = 0 ，称d 是正刚的。若z ( d ) 1 ，称d 是几乎正则的 设t ( x ，e ) 为一个p x 口阶二部竞赛图，( x ，y ) 是t p ，口) 的个划分，令ixl _ p ，iy i = g 。我们分别用醇( t ，) 和蝣( 口) 表示口在t 中的出度和入度。 我们进一步引入定义，设移y ( 刃，s 矿( d ，我们定义 n i ( ) = 札s i t n ，a ( t ) ) ；时( 口) = t s i 口钍a ( d 第5 页 中北大学学位论文 令 啊( s ) = u 屿( u ) ； s 商扣) = i 瞄0 ) f ； 瞄( 研= u 瞄扣) v e s 露0 ) = f j | v ；( ”) | | 若日为r 的一个子图，我们分剐用、售( ) ， 嘻( 口) 以及t 一日代替云日) ( t ，) ，卉柳( ) 以 及t i v ( 刃一y ( 日) 】。令e = m t j 2 t 乜。口l 为t 中胄臼一个圈，m 2 。令t 为一个非。正整数，我 们引入定义 j 略0 ) = q g i 地一t 恬扣) ) 以及 舫( 口) = 如cj 铀蝣) 对于所有z 五，9 m ，若噩cx ，mcy k x y a ( t ) ，则我们将其写为蜀辛h 反 之亦然。如果噩= z ) ，那么我们可改为霉= h 。对于，v y ( 刃，t 一磙明坼( 由= 峰( t ，) 且孵= 蝣( 功， 第6 页 中北大学学位论文 第三章二部竞赛图h a m i l t o n 性质的主要结果 本章主要进行二部竞赛图h a m i l t o n 性质的研究。 众所周知，图的哈密尔顿性问题一直是图论中的一个十分重要且又十分话跃的研究课 题。国内外每年都有大量的研究论文涉及图的哈密尔顿性问题。本论文利用二部竞赛图的 度条件研究其哈密尔顿性，得到了系列的结果，改进或推广了不少相关的已知结果，对本领 域的研究起到了积极的推动作用。 h a n d i l t o n 图问题有着悠久的历史，许多研究者在理论和应用上已取得了很多有价值的 研究成果在本节中，我们先简要的叙述一下h a m i l t o n 图的概念和相关的定理。 3 1 预备知识 包含d 的所有顶点的圈称为d 的h a m i l t o n 圈。称有向图d 是h a m i l t o n i a n ，若d 包含一 个h a m i l t o n 圈。路p 称为有向图d 的h a m i l t o n 路，如果v ( p ) = y ( d ) ，称这个图是h a m i l t o n 图。 不含h a m i l t o n 圈的图称为非h 彻m t o n 图。判断一个给定的图是否是h a m i l t o n 图的问题称为 h a m i l t o n 问题。 设t ( 竹，礼1 为住n 的二部竞赛图， 如果t ( 行，n ) 满足条件：删簪e 辛d + ( + d - ( w ) 则称t ( n ，付) 满足0 ( ) 条件； 如果t ( n ，n ) 满足条件： u e 号d + ( “) + d - ( ) 七则称t ( n ，n ) 满足w ( 七) 条件。 设( x ，y ) 是t ( 钍，嚣) 的一个偶划分，并设x = x l u 拖，y = k u 蚝且五n 磁= ，m n 酶= ，令l 五i = k ，k = z 引入定义：只：蜀辛m 兮恐辛蚝辛咒；岛：y 2 兮五= k ；马：v 矾k 有d 毛饥) sl ；p 4 ：v 耽y 2 ，有嚷) 1 ；p 5 ：协2 而有磕) s 嚷( z 2 ) ；r ：h 或吃( 玑) = o 或吒臼1 ) 删n 慨( z 2 ) ，z 2 吒( 讥) 。 对整数1 ，2 是具有只的二部竞赛图，并置： 雪( k ，z ，n 一七，仃一1 ) = t ( 礼，哟i t ( n ，竹) 具有只， ；2 ，3 ，4 ，5 ； p ( 老， ，n 一囊n j ) = t ( n ，哟i t ( 竹，哪) 具有只，i ；2 ，3 ，5 ，6 下面给出本章主要用到的引理。 第7 员 中北大学学位论文 3 2 引理 为了后面的知识的应用有如下引理： ； 理3 2 1 及尼，托) 不含2 _ 因子，剐可将箕点集y ( z 均划分为四个子集p ，9 ，矗幕塔 使得p x ，冗= x p ，这里q = 孵( p ) 且i p l l q l 。 证明；设t 不含2 - 因子，则由p r o p 0 8 i t i o n3 1 1 6 ( b ) 傍e e 【9 】，p 1 4 4 可知存在尸x 使 得j p j j 瞄( p ) j 3 3 相关结论 到目前为止h a 蛹i t o n 圈的非平凡的充分必要条件尚不知道。现在讨论图g 是h a 删i o n 图 的充分条件；由于一个图是h a m t o n 图当且仅当它的基础简单图是h 锄m t o n 图，所以只要 讨论简单图就够了。本节我们先给出一些已证明了相关结果。 定理3 3 1 7 1 】每个竞赛图都包含一条h a m i l t o n 一路。 定理3 3 2 【5 7 】设d 是一个，l 一部竞赛图，h ，为d 的部集，k ( d ) 之爰麓 i k i 则d 是h a m i l t o n i m a 。 定理3 3 3 【6 7 】几乎正则竹一部27 ) 竞赛图是i - i a m i l t o n i a a r 定理3 3 4 【5 7 12 一部竞赛图是h a l i l 伽n j a n 当且仅当它是强连通的，并且有一个圈园 子。 定理3 3 5 【7 0 】正则的多部竞赛图是h a m i l t o n i a n 。 定理3 ，3 6 f 3 l lz 协，住) 是h a n 虹托o i a n 当且仅当? 似挖) 是强连通的，且它含有一个二 因子。 此定理有很重要的理论意义，但寻求t ( n ，竹) 的一个2 一因子非常困难，因此寻求h a m i l t o n 二部竞赛图的一些简明判别条件是有意义的问题， 在研究图的哈密尔顿问题中，一些关于顶点度的充分条件起了很重要的作用。 定理3 3 7 如果t ( n ，n ) 满足0 一2 ) 条件n25 ，则t ( n ，n ) 是h a m n t o n 除非t ( 竹，n ) 于( n f ，l + l ， ，佗一l 1 ) 。 定理3 3 8 【7 2 】如果t ，满足w m 一1 ) ，那么r ，牡) 是h 锄1 i i 如n 除非t 同构与 t ( 掣，孚，孚，孚) 凯为奇数或者t ( 2 ，譬，警) 。 第8 页 中北大学学位论文 定理3 3 9 【o o 如果t ( m 哟n2 6 满足 伽e ( t ) 荨0 ) + 砖( 口) n 一2 ， 贝i j t ( n ，n ) 是h 眦i l t o n 除非t 同构与丁( f + 2 ，z ，n z 一2 ，n j ) 墨尹sl 暑，或者r ( t l ，礼) p ( j + l ，z ，n 一1 1 ，n 1 ) 学2 学。 3 4主要结果和证明 本节，我们沿着定理3 3 8 和3 3 9 的结论，将定理3 3 9 作了一些改进并进一步推广， 得到以下定理。 定理3 4 1 若t 为n n 的二部竞赛图且n21 2 。此外，还满足 ( i ) w ( 一2 ) ，若i q i 十i r i = n 一1 ； ( i i ) w ( n 一3 ) ，若i q i + i r i 竹一1 ； 则t 是h a m i l t o n i a n ，除非t ( n ，哟型t ( 1 + 3 ，2 ，n z 一3 ，竹一z ) ，亚尹；，或t ( 码扎) r ( 1 + 2 ，2 ，n z 一2 j 仃一z ) ，孚zs 墨笋，或t 扣，n ) p u + 1 ，z ，n z 一1 ，n z ) 警f 学。 证明定理3 4 1 设纠菏足条件，则只需证明下面两个论断即可。 论断1 若n2 1 2 ，t 是强连通的。 用反证法，设t 的强连通分支为a ，岛，c k ( m2 2 ) 。假定l j 时，总有x ( a ) 一 y ( g ) ，y ( g ) 一x c c ，) ，断言l y ( q ) i 4 ，若不然，因臼是强连通的，必有i y ( 口) i = 1 。不 妨设a = 如 cx ，则如卜一y ，期对任意的鲈y 均有珊e ，由定理假设及瘁( z ) = 0 得 靠( z ) + d ；= ( 掣) = 苟( | ，) 忭一3 ( 1 ) 令墨：( y ) ，恐= x 蜀，则由( 1 ) 知i x l i n 一3 ，由$ 磁便知1 l 恐i s3 。此外 有 n 2 = 砧( f ) + d ；( 。) y e y $ = 衅( ) + 苗( 茁) + 妨( z ) y 6 yo 五1 z 2 n ( 住一3 ) + 礼f 砀i + ( z 1 ) ， 2 x 1 此式蕴含 醇o ，) s n ( 3 一i 为i ) ( 2 ) 第9 页 中j b 大学学位论文 令苟( z o ) = 删n 簖0 1 ) l 善噩 ，则由( 2 ) 和l x i i n 一3 ，1 l x 2 i 3 得 ( 住一3 ) 薛( z o ) 茹( 霉) n ， ：e 为 有 苟 。) 【南】- 1 1 2 ) ( 3 ) ( 1 ) 蕴含( 们3 。z 令y x o e 和( 1 ) ，( 3 ) 以及定理假设得 4 喀( ) + 瞄( z o ) n 一3 ， 求得n 7 ，这是不可能的。因此iai 芝4 成立。类似的，ic ki 4 。 现在，牟( 口) s 譬。, - l 较u x ( a ) 使得( “) 孕，若存在移y ( c - m ) 使 得d ；= ( 。) 1 掣，则有。 晦( u ) + 筇( 。) 堕掣剑； ( 4 ) 又由假设知删e ( 巧有 每( 让) + d ；= ( 口) n 一3 ( 5 ) 联合( 4 ) ( 5 ) 得n 6 与竹1 2 矛盾。因此设对与任意的口y ( c k ) 均有砖( 口) 掣。则可断 言：存在铆x ( c 使苟) 砌掣+ n 掣= m _ 4 + a l t 即得( a 一见) 2 0 ，显然不成立，从而可得 簖( 妨+ 蜥) 0 ， 即存在q q 使r l g e ，则 n 一2 d 子( r 1 ) + d ；( g ) = l q i d 古( r 1 ) + d ；( r 1 ) + i r i d ；( 口) 第1 2 页 中北大学学位论文 即d 古( r 1 ) + ( q ) 略( r 1 ) + 1 。类似与( 2 2 ) ，有 呓) 略h ) ，靠( 力喀h ) ( 1 5 ) 若对某个r l r 有呓( r 1 ) = 0 ，则蛄( r 1 ) n ，那么b 中包含通过伽的从4 到轨+ 2 的每一个偶长圈 证明：当2 m n + 1 ，令集合 m = 畅( u ) n 醇舡新删( t ，) 那么 k 圣，否则屯( ”) 2 砧( 铭) ，因两行= 奶( 口) + 菇( ”) d s ( u ) + 呓( ”) ，矛盾- 进而不 失一般性，我们假设”l n m ，这暗示”l t a 且口t 一2 ，l “a 。那么，我们发现 c = l u u 口鼽一2 m 十4 t 1 2 n 一2 ，衅5 - 地n 口1 是一个包含伽长为2 m 的圈。 引理4 2 2 令口= 。i 忱锄观为二部竞赛图t 中一条最长圈且p = u o u l 为t c 中的一条路 ( i ) 如果t 是强连通的，那么r g 中无圈【5 】， ( i i ) 【2 1 如果略( u o ) 0 ，砧( t 。) 0 ，那么 f y c f ：耄：) + ：鬈 ：二：舅磊萋；： ( i i i ) 托) n 舫) = ( 1 t s m ， m + 沩偶数) ， ( 如) 如果m 为奇数，则苫1 ( 蛳) 兮苫1 ( u 。) 。 ( 口) 如果m 2 且为偶数，则畅1 ( t 1 0 ) 号言2 ( t 。) 证明 ( “0 ( 反证法) 。若仇 匹( t o ) n 扩( t 。) ，1 t m ，也就是说仇t o ，“m 蛾+ t a ( ，则我们会得到一个圈 比c 长，故矛盾。 p u 仉t e 0 ，m t k + t ue 弘f + 1 ，q + 口，吨“一1 ) 第1 7 页 中北大学学位论文 ( 妇) ( 反证法) 。假定存在两点地 字1 ( t 0 ) ，吩舫1 ( ) ，且叼地a ( 刃。则我们 有吨一l u o ，m v j + l a ( t ) 。不失一