（应用数学专业论文）有向图的可迹性与泛连通性点对.pdf

摘要 本文分为两章对局部内( 外) 半完全有向图及其扩张有向图的可迹性和 竞赛图及扩张竞赛图中的泛连通性点对这两个方面分别作了讨论 第一章里我们研究了局部内( 外) 半完全有向图及扩张的局部内( 外) 半 完全有向图的可迹性问题1 1 节介绍了与内容相关的概念和引理，1 2 节 证明了对于连通的n 阶局部内半完全有向图d ，若它中任意不相邻的受控 点对 z ，g ) ，满足d ( z ) ? - t ，d ( y ) 礼一1 ，或d ( x ) 礼一l ，d ( y ) 扎，则d 是可迹 的同时还证明了对n 阶连通的局部内半完全有向图d 中的任意不相邻的 受控点对 z ，) ，若m i n d + ( 。) + d - ( ) ，d - ( 。) + d + ( g ) ) 扎一1 ，则d 可迹然 后，利用逆图的性质我们把这两个结论推广到连通的局部外半完全有向图 中1 3 节研究了n 阶连通的扩张局部内半完全有向图_ d 的可迹性我们 证明了对于d 中任意不相邻的受控点对 z ，) 和d 中任意不相邻的控制点 对 “， ) ，如果d ( x ) n ，d ( y ) 扎一1 ，或d ( x ) n 一1 ，d ( y ) 扎，且d ( “) n l ， d ( v ) 佗一1 ，则d 是可迹的同时我们将此结论推广到了连通的扩张局部 外半完全有向图中 第二章研究了竞赛图和扩张竞赛图中的泛连通性点对首节给出了与 内容相关的基本概念和相关结论2 2 节证明了阶为n 的连通的但非强连 通的竞赛图t 中存在两点u 使得 钍，”) 是t 的泛连通性点对，并且给出 了寻找这个点对的一个好算法同时我们还得到若d 是可传递的竞赛图， 则在d 中存在唯一的泛连通性点对2 3 节给出了扩张竞赛图中存在泛连 通性点对的两个充分条件，并且证明了若d 是可传递的多部竞赛图，且不 是竞赛图，则d 中无泛连通性点对 关键词：h a m i l t o n 路；h a m i l t o n 圈；扩张有向图；局部内( 外) 半完全有向 图；竞赛图；泛连通性点对 中图分类号：0 1 5 7 5 a b s t r a c t t h i sp a p e ra r ec o m p o s e do ft w oc h a p t e r s ，i nw h i c hw es t u d yt h eh a m i l t o n i a np a t h s i nl o c a l l yi n ( o u t ) - s e m i c o m p l e t ed i g r a p h sa n de x t e n d e dl o c a l l yi n ( o u t ) - - s e m i c o m ，p l e t e d i g r a p h s ，a n dw ea l s os t u d yp a n p a t h i c a lv e r t i c e s p a i ri nt o u r n a m e n t sa n de x t e n d e d t o u r n a m e n t s i nt h ef i r s tc h a p t e r ，h a m i l t o np a t hp r o b l e m sa r ed i s c u s s e d s o m ed e f i n i t i o n sa n d r e l a t i v er e s u l t sa r eg i v e ni ns e c t i o n11 i ns e c t i o n1 2 t w os u f f i c i e n tc o n d i t i o n sf o rt h e e x i s t e n c eo fah a m i l t o n i a np a t hi nal o c a l l yi n - s e m i c o m p l e t ed i g r a p ha r ed e s c r i b e d ， w h i c ha r el i s t e da sf o l l o w ：( i ) l e tdb eac o n n e c t e dl o c a l l yi n s e m i c o m p l e t ed i g r a p h o fo r d e rn 2 s u p p o s et h a tf o re v e r yd o m i n a t e dp a i ro fn o n a d j a c e n tv e r t i c e s ) ， e i t h e rd ( 甸礼a n dd ( y ) n 一1 ，o rd ( x ) 2n 一1a n dd ( y ) n ，t h e ndi st r a c e a b l e ( i i ) l e td b eac o n n e c t e dl o c a l l yi n s e m i c o m p l e t ed i g r a p ho fo r d e r 2 s u p p o s et h a t ds a t i s f i e sm i n d + ( z ) + d ( ) ，d 一( z ) + d + ( ) ) n - 1f o re v e r yd o m i n a t e dp a i ro f n o n a d j a c e n tv e r t i c e s 托) t h e nd i st r a c e a b l e u s e dt h ep r o p e r t yo f t h er e v e r s ed i g r a p h s ， t w os i m i l a rr e s u l t sa r eo b t a i n e df o rl o c a l l yo u t - s e m i c o m p l e t ed i g r a p h s i ns e c t i o n1 3 ， w es h o was u f f i c i e n tc o n d i t i o nf o ra ne x t e n d e dl o c a l l yi n - s e m i c o m p l e t ed i g r a p ht ob e t r a c e a b l e ，t h er e s u l ti st h a tl e tdb eac o n n e c t e de x t e n d e dl o c a l l yi n s e m i e o m p l e t e d i g r a p ho fo r d e rn 2 i fe i t h e rd ( x ) na n dd ( v ) 札一1o rd ( x ) 礼一1a n d d ( y ) n ，a n dd ( ) n l ，d ( v ) 扎一1f o re v e r yd o m i n a t e dp a i ro fn o n a d j a c e n t v e r t i c e s z ，) a n de v e r yd o m i n a t i n gp a i ro fn o n a d j a c e n tv e r t i c e s “， ) ，t h e nd i s t r a c e a b l e m o r e o v e r ，t h e r ei sas i m i l a rr e s u l ti ne x t e n d e dl o c a l l yo u t - s e m i c o m p l e t e d i g r a p h s i nt h es e c o n dc h a p t e r ，p a n p a t h i c a lv e r t i c e s - p a i r si nt o u r n a m e n t sa n dp a n p a t h i c a l v e r t i c e s p a i r si ne x t e n d e dt o u r n a m e n t sa r ed i s c u s s e d i ns e c t i o n2 2 w ep r o v et h a t e v e r ye n o n e c t e db u tn o ts t r o n g l yc n o n e c t e dt o u r n a m e n tc o n t a i n sap a i ro fv e r t i c e s ( “，口) s u c ht h a t “ ) a r ep a n p a t h i c a lv e r t i c e s p a i r s ，a n dg i v eap o l y n o m i a la l g o r i t h m t of i n dt h o s et w ov e r t i c e s a n o t h e rr e s u l tt h a te v e r yt r a n s i t i v et o u r n a m e n tc o n t a i n s o n l yap a i ro fp a n p a t h i c a lv e r t i c e si sp r e s e n t e di nt h i ss e c t i o n t w os u f f i c i e n tc o n d i t i o n sf o ra ne x t e n d e dt o u r n a m e n tt oh a v ep a n p a t h i c a lv e r t i c e s p a i r sa r ef o r m u l a t e di n s e c t i o n2 3 f u r t h e r m o r e ，w ep r o v et h a ti fdb eat r a n s i t i v ee x t e n d e dt o u r n a m e n tb u t n o tt o u r n a m e n t ，t h e ndd o e sn o tc o n t a i np a n p a t h i e a lv e r t i c e s p a i r s k e y w o r d s ：h a m i l t o np a t h ；h a m i l t o nc y c l e ；e x t e n d e dd i g r a p h ；l o c a l l yi n ( o u t ) s e m i c o m p l e t ed i g r a p h ；t o u r n a m e n t ；p a n p a t h i c a lv e r t i c e s p a i r 引言 引言 图论作为离散数学的一个重要分支，已有两百多年的历史由于其广泛的应用背 景，近半个世纪以来，越来越多的科研工作者投入到了该领域的研究中特别是在计 算机的出现和推动下，有关图的理论有了更加迅速的发展图论现在已经成为研究系 统工程、管理工程、计算机科学、通讯与网络理论、自动控制、运筹学以至社会科学 等诸多学科的一种重要数学工具图论的应用之所以如此广泛，在于它可作为分析处 理多种具体离散结构问题的一种较为理想的数学模型，由于它的算法又可借助计算机 实现，因而图论与计算机相结合为图论的研究和应用开辟了广阔的前景 本文只对有限图进行研究有限图分为有向图和无向图无向图的研究已相当深 入，结果也非常丰硕无向图中的h a m i l t o n 图问题是一个非常热门的课题，它是1 8 5 6 年h a m i l t o n 在给他的朋友g r a v e s 写信中提到的但是到目前为止h a m i l t o n 图的非 平凡充要条件还没有找到，它是图论中尚未解决的主要问题之一上世纪7 0 年代以 来，随着生产中许多实际问题的提出，人们更多地转向于对有向图的研究同时，有 向图中的h a m i l t o n 路问题也就成为很大一部分学者热衷于讨论的课题 竞赛图是一类非常有用的有向图，它的路和圈的问题一直是研究的焦点 1 9 9 0 年，j b a n g j e n s e n 1 1 提出了竞赛图的一些非常有趣的推广图类一局部半完全有向 图、局部内半完全有向图、局部外半完全有向图其中，局部内半完全有向图与局部外 半完全有向图的交集是局部半完全有向图它们的路和圈也是有向图研究的重要的问 题有向图d 是可迹的当且仅当d 中有一条h a m i l t o n 路1 9 9 0 年，b a n g j e n s e n 1 】 证明了局部半完全有向图d 可迹当且仅当d 连通对于局部内( 外) 半完全有向图 的可迹性，1 9 9 3 年，j b a n g - j e n s e n 和gg u t i n n 从分支的角度作了一些研究，但 很少有人从度的角度的来刻画它的可迹性本文在这方面做了一些探讨1 9 9 4 年， j b a n g - j e n s e n 和g ，g u t i n 3 1 证明了强连通的且含有一个圈因子的扩张局部半完全有 向图d 是h a m i l t o n 图文 4 】把这个结论推广到了扩张的局部内( 外) 半完全有向 图中，即强连通的且含有一个圈因子的扩张局部内( 外) 半完全有向图d 是h a m i l t o n 图同时，j b a n g j e n s e n 和g g u t i n 3 】还证明了连通的扩张局部半完全有向图d 若 含有一个1 一路一圈因子，则d 可迹但此定理不能推广到扩张的局部内( 外) 半完 全有向图中于是g r e g o r yg u t i n 和j o r g e nb a n g - j e n s e n 5 1 提出如何刻画扩张的局部 内半完全有向图可迹性的问题本文证明了扩张的局部内( 外) 半完全有向图可迹的 个充分条件 本文还对竞赛图和扩张竞赛图中的泛连通性点对做了一些研究1 9 3 4 年， r d d e 删指出每个竞赛图都包含一条h a m i l t o n 路1 9 6 6 年，m o o n 7 l 给出了强 连通的竞赛图是点泛圈的，自然其也是h a m i l t o n 图2 0 0 0 年，姚天行【8 】证明了强 2 有向图的可迹性与泛连通性点对 连通的竞赛图中存在一点是外弧泛圈的显然，从f 8 1 我们可以推出阶为n 的强连通 的竞赛图t 中存在点对 u ，u ) ，使在丁】中有长为2 ，3 ，一，n 一1 的( u ，u ) 一路在此基 础上，我们自然会想到竞赛图r 满足什么条件时，在t 中存在两点n ， ，使得t 中 有长为1 ，2 ，一，n 一1 的( u ，u ) 一路该问题将在2 2 节中被讨论，并且我们在2 3 节 把该问题推广到了扩张竞赛图中 另外，本文还给出许多与主要结论相关的定义与引理，这部分内容也是研究有向 图可迹性和竞赛图的一些性质的一个较为全面的资料 局部内汐一半完全有向图的可迹性 第一章局部内( 外) 半完全有向图的可迹性 l _ 1 预备知识 本文所讨论的图均为有向图( 无环和重弧) ，为了方便读者的阅读，我们先给出一 些相关的术语和记号，文中未定义的术语和记号参见文献f 4 l 定义1 1 1 设 是有向图d 中的一点，若u 仇( “j u ) 是d 中的弧，则由所有饥( v j ) 构成的点集称为点u 的外( 内) 邻集我们分别用古( u ) 和i ( ) 表示d 中点v 的 外邻集和内邻集，简记为+ ( ) 与一( ) ，并且d + ( ) = i n + ( ) h d 一( ”) = l n 一( w ) | 若有向图_ d 中的任意两点间至少有一条弧，则称_ d 是半完全有向图 定义1 1 2 把无向图g 的每条边( 嚣，) 用弧z g 或弧y z 或弧叫和妒代替所 得到的有向图d 称为无向图g 的双重定向图其中无向图g 称为有向图d 的基础 图，记为u g ( d ) d 连通当且仅当u g ( d ) 连通对于d 中任两个不同的点z 与y ， 在d 中若有( z ，) 一路，并且有( y ，岱) 一路，则称d 是强连通的 定义1 1 3 若有向图d 中任意一点。的内( 外) 邻集中所有点的导出子图均是半 完全有向图，则称d 是局部内( 外) 半完全有向图若有向图d 既是局部内半完全有 向图，又是局部外半完全有向图，则称d 是局部半完全有向图 定义1 1 4 若对于有向图d 中任意两条内部不相交且有公共终点y 的路p q ，在 d 中存在路月使得v ( r ) = v ( p ) u v ( q ) ，且r 的终点是y ，始点是路p 或0 的始 点，则称有向图d 是内路可合并的 定义1 1 - 5 设，y 为有向图d 中的两个不同点，若如，y 被z 控制，即z x ，z y e ) ，记为z x ，z y ，则 ，) 称为受控点对；若 。，) 控制点z ，即x z ，y z e ( d ) ，记为。一z ，y z ，则 茁，订称为控制点对 定义1 1 6 设p = l u 2 是d 中一条的路，q = v l v 2 仇是d v ( p ) 中 的另一条路，如果存在t l ，2 ，t 一1 ) ，使地一m ，一坎+ 1 】则称路p 可插入 到路q 中；若存在l = i l i 2 i 3 i ) ，则d i ，d ，叫称为d 的强连通分支无圈序 定义1 1 8 有向图d 的强分支有向图是通过收缩d 的强连通分支及在收缩过 程中删去重弧而得到的，记为s c ( d ) ，即若d l ，d 。，皿是d 的强连通分支，则 3 4 有向图的可迹性与泛连通性点对 v ( s c ( d ) ) = u - ，。2 ，饥) ，a ( s c ( d ) ) = ( u ，：( v ( d 。) ，y ( d 5 ) ) d 0 ) 定义1 19 强分支有向图s c ( d ) 中入度( 出度) 为零的点所对应的d 的强分支 称为d 的初始( 终止) 强连通分支，其它强分支称为d 的中间强连通分支 定义1 1 1 0 设d ( k 4 ) 是n 阶有向图( 其中v = u l ， 0 2 ，一， ) ，g 1 ，g o ，一，g 。 是顶点互不相交的有向图若一个有向图d 7 ，它的顶点集为v ( c 1 ) uv ( c 2 ) u u v ( a 。) ，弧集为( u 坠1 a ( g ，) ) u g i g j ：肌y ( g ，) ，西y ( c j ) ，扯a ( d ) ) ，则称d 7 为g 1 ，g 2 ，g 二在_ d 下的合成图，记作d i e l ，g 2 ，一，g 。1 定义1 1 1 1 设r 是n 阶局部内( 外) 半完全有向图，若有向图d = r i h l ，岛，日。 ( 其中甄是空图) ，使得v ( d ) = y ( 凰) u y ( h 2 ) u 矿( e 。) ，a ( d ) = h l h j ：h l y ( 甄) ，h j y ( 屿) ，v i v j a ( r ) ) ，则称d 是扩张的局部内( 外) 半完全有向图且称 凰，日2 ，f k 为d 的n 个部集，同一部集中的点称为相似点 另外，包含有向图d 的每个顶点的路称为h a m i l t o n 路若有向图d 有h a m i l t o n 路，则称d 是可迹的包含有向图d 的每个顶点的圈称为h a m i l t o n 圈若有向图 d 有h a m i l t o n 瓯则称d 是哈图将d 中每条弧的方向都颠倒过来所得到的有向 图d 称为d 的逆图设d 】是d 的子图，点z 在_ d 1 的度记为d d 。( o ) 对于任意的有向图d ，判断d 中是否存在h a m i l t o n 路和h a m i l t o n 圈是困难 的本文主要研究局部内( 外) 半完全有向图和扩张的局部内( 外) 半完全有向图的可 迹性在此，我们首先给出这两个图类是h a m i l t o n 图或可迹的一些已有结果 定理1 1 1 2 2 阶礼2 的局部内半完全有向图d 是哈图当且仅当d 强连通 定理1 1 1 3 3 扩张的局部半完全有向图_ d 是哈图当且仅当d 是强连通的，并且 d 中含有一个圈因子 定理1 1 1 4 3 】扩张的局部半完全有向图d 可迹当且仅当d 中含有一个1 一路一 圈因子。 1 2 局部内( 外) 半完全有向图的可迹性 在文f 4 】中，j b a n g - j e n s e n 给出了连通的有向图可迹的一个充分条件，其结论 如下， 命题1 2 1 设d 是连通的佗阶有向图，若对d 中任意不相邻的受控点对 嚣，) ， 有d ( z ) 礼一1 ，d ( 口) n 一2 ，或d ( y ) 礼一1 ，d ( 甸n 一2 ，则d 是可迹的 事实上，这个命题是不成立的，我们很容易找到它的一个反倒，如图1 在图l 中 只有一对不相邻的受控点对和1 ，地 ，且d ( x 1 ) 4 ，d ( o 。) 3 ，满足命题的条件，但该 图显然没有h a m i l t o n 路，因为z 4 ，0 5 的入度全为零 局部内汐卜j 半完全有向图的可迹性 z 3z 4z 5 图1 作为半完全有向图的推广，局部半完全有向图是一类非常有应用价值的图类，文 【9 】【1 0 】对于它的结构作了详细的讨论由定义我们知道，局部半完全有向图一定是局部 内( 外) 半完全有向图，但反之不然定理1 11 2 证明了强连通的局部内半完全有向图 d 是哈图，故强连通的局部半完全有向图_ d 亦是哈图在文献 1 1 】中，j b a n g - j e n s e n 证明了连通的局部半完全有向图d 是可迹的，但连通的局部内( 外) 半完全有向图未 必是可迹的文 1 2 讨论了寻找局部内( 外) 半完全有向图的h a m i l t o n 路与h a m i l t o n 圈的算法本文对命题1 2 1 的条件作了修改，在度约束下得到局部内( 夕卜) 半完全有 向图可迹的一个充分条件，即对于连通的局部内( 外) 半完全有向图d ，若它的任意不 相邻的受控( 控制) 点对 z ，以，有d ( x ) 竹，d ( ) 2 订一1 ，或有d ( z ) 佗一l ，d ( y ) n ， 则d 是可迹的 在证明本文的主要定理之前，我们先给出几个相关的引理 引理1 2 2 【”i 局部内半完全有向图是内路可合并的 证明设p l = x o z l x 2 薪z ，p 2 = y o y l y 2 玑2 是局部内半完全有向图d 中的任 两条内部点不相交且有公共终点的路若r = 0 或8 = 0 ，由于d 是局部内半完全有 向图，结论显然成立故我们考虑r ，8 1 的情形假设q l 与q 2 是d 中的任两条 有公共终点且内部点不相交的路，若其内部点个数和小于a ，则q 与q 2 可内路合并 成路q 又由于_ d 是局部内半完全有向图，且x ，一z ，y s z ，故与蜘间有弧 不妨设蜘一研，则路p 1 i x 0 ，盘“与p 2 g o ，鲥z ，满足假设条件，故其俩可内路可合并成 路p ，则在d 中存在路p ，其的始点是x 或y ，终点是z ，且v ( p ) = y ( p 1 ) u y ( p 2 ) ， 定理得证 引理1 2 3 t l q 设p = v l v 2 饥是有向图_ d 中的一条路，点 v ( d ) 一y ( p ) ，若 w 不能插入到p 中，且饥控制 ，则d p ) t + 1 ；若 不能插入到p 中，且仇不 控制w ，则d p ( w ) t 证明设邮( 叫) = m 由题设知 不能插入到p 中，故若弧v i w a ( d ) ，则 弧w v l + 1 岳a ( d ) 故当饥叫a ( d ) 时，d + 伽) t 一( m 一1 ) = t m + 1 ，所 以d p ( w ) = d ；( ) + 砧( 叫) sm + 0 一m + 1 ) 一+ 1 故当v t w 掣a ( d ) 时， 砧( 叫) t m ，所以d p ( w ) 一d t ( w ) + d 上m ) m + ( 亡一m ) = t ，定理得证 5 6 有向图的可迹性与泛连通性点对 在讨论图的性质与结构时，近年来提出一个很有效的方法多重插入法这个 方法不仅在无向图中得到广泛的应用，参看文f 1 5 】，而且我们经常用此方法解决有向 图中的一些问题，参看文 1 6 1 7 1 下面利用多重插入法得到一个重要引理 引理124 1 ”) 设p 是有向图d a v p 的一条路，且q = v l v 2 饥是d v ( p 1 中的另一条路若p 可多重插入到q 中，则在d 中存在( 。，v t ) 一路兄，使v ( n ) = v ( p ) u y ( q ) 证明设p = u l 讹，并且l = i 1 i 2 i s g 另外，若在d 中只要有础， 弧( 其中z z ) ，就有z z a ( d ) ，则称d 是可传 递的若d 中不存在长为2 的圈，则称d 是定向图 引理2 1 1 2 竞赛图是可迹的 引理2 1 1 3 1 ”】强连通的竞赛图中有h a m i l t o n 圈 引理2 1 1 4 有向图d 是单向的当且仅当d 含有唯一的强连通分支无圈序 _ d l ，d 2 ，d ，使得( y ( d ) ，y ( 皿+ 1 ) ) o ，( i = 1 ，2 ，t 一1 ) 引理2 1 1 5 2 0 】若半完全多部有向图d 有好圈因子e lu q ，使得a 没有关于c 3 一， 的奇异点i = 1 ，2 ，则d 是哈图，且对于给定的圈因子g 与岛，可在o ( i v ( c , ) l l v ( 岛) 1 ) 时间内找到d 的h a m i l t o n 圈 引理2 1 1 6 2 q 设q u c 是半完全多部有向图d 的圈因子，如果q 没有关于g 的奇异点，且d 非哈图，则q 中的每条弧z ，或者弧z 可插入到g 中，或者两点 嚣与y 均可插入到0 中 引理2 1 1 7 2 0 】设p = “1 u 2 u ，是有向图d 的一条路，c 是d p 中的一个 圈，如果u ，可插入到c 中，并且或者弧撕+ 1 可插入到c 中，或者点恤可插入到 c 中( 其中i = l ，2 ，r 1 ) ，则d 中存在圈z ，使得v ( z ) = v ( p ) u y ( c ) ，并且可 在o ( i v ( p ) l l v ( c ) 1 ) 时间内找到该圈 2 2 竞赛图中的泛连通性点对 若有向图d 中存在一点u ，使得对任意一点u n + ( “) ，在d 中有包含u u 弧的 长为的圈( 3 佗) ，则称点珏是外弧泛圈的姚天行在文 8 】中证明了每个强连 通的竞赛图中都存在一个点让是外弧泛圈的 引理2 2 1 ( 8 】设t 是阶为他的强连通竞赛图则在d 中至少存在一点u ，使点 是外弧泛圈的 由引理2 2 1 ，我们不难有下面的推论t 1 6 有向图的可迹性与泛连通性点对 推论2 22 设t = ( v a ) 是阶为n 的强连通竞赛图，则在t 中存在点对 u ， ) ， 使得在t 中有长为2 ，3 ，n 一1 的( “，口) 一路 证明因为t 是强连通竞赛图，所以由引理2 21 可知在t 中存在一点 是外弧 泛圈的设u a ( t ) ，即在t 中通过w 札弧有长为3 ，4 ，n 的圈，所以在丁中有 长为2 ，3 ，n 一1 的( “， ) 一路，证毕 推论2 2 1 表明强连通的竞赛图t 中存在两点 “， ) ，使得在t 中有长为2 ，3 ，n 1 的( “，v ) 路我们自然会推测在t 中是否亦存在点对o ，y ，使在t 中有长为1 ，2 ，n 一 1 的( o ，y ) - 路，事实上，从图3 中可知此猜想不成立 本节主要讨论了连通的但非强连通的竞赛图t 中存在f “，w ) 点对，使得在t 中 有长为1 ，2 ，n 一1 的( 乱， ) 一路 定理2 23 设t 是阶为礼的连通的但非强连通的竞赛图，则t 中存在两点f “，口 ， 使得 札，u 是r 的泛连通性点对 证明因为t 是竞赛图，故由引理2 1 1 2 知t 可迹，所以t 是单向的由引理2 2 1 4 知t 中存在唯一的强连通分支无圈序乃，乃，噩使得( v ( t d ，y ( 正+ - ) ) 0 ，( i 一 1 ，2 ，t 一1 ) 又因为t 是竞赛图，故墨一t j o j ) 设m l y 慨) 1 0 一l ，2 ，t ) ， 并且n o = 0 因为正是强连通竞赛图，故由引理2 2 1 3 知置中有h a m i l t o n 圈 所以正中存在以任意点为起点的长为h 的路和以任意点为终点的长为h 的路，其中 ( 1shsm 1 ) 设u y ) ，口v ( t 0 ，下面我们将分三种情形证明r 中有长为 k ( k = 1 ，2 ，n 一1 ) 的( u ， ) 一路令 j1 4 - l 7 2 i 9 ( 1 2 ) i = 0i = 0 情形1 ：若f 一0 ，则0 g n 1 由于正中存在以任意点为起点的长为h 的路 ( 1 茎h 茎啦一1 ) ，故孔中存在长为g 一1 的路( 缸，s ) 一路p 因为丑一正，所以 s 一 故p 为t 中长为9 ( 1 曼gsn 1 ) 的( “，w ) 一路 情形2 ：若l5f t 一1 ，则1sf t 一2 ，故t t l g 茎n i 因为五是强连通 竞赛图，故在置中存在h a m i l t o n 路只，设只= ? t i 。札t 2 。( 1 曼l s f ，“1 。= “) 设 b + 1 = v 1 7 3 2 珥是丑+ l 中长为g 一7 t i 一1 的路易知r = k 一n i 令v l = u ( t + 1 ) 1 竞赛图与扩张竞赛图中的搓连通性点对 1 7 由于正ht j ( i j ) ，则有t h 一札( 。+ 1 ) 。，且坼一7 j 则p 1 p 2 p + 1 v 为t 中一条长 一1 为g ( n l + l 兰9 茎m ) 的( “， ) 路 i = o 情形3 ；若l _ t l ，则 由于t 中最长路的长度为n 一1 ，所以( 1 3 ) 为 即 ( 1 3 ) ( 1 4 ) ( 1 5 ) 设只= u t l “小u h ，( 1 i t 一1 ，) 是丑中的h a m i l t o n 路( u 1 1 = u ) ，最= 饥。乱幻毗。( s = k e 毗- t - 1 ，e 。= ) 是五中一条以u 为终点的长为g 一m 的路因为正一t j 0 j ) ，所以u t 。，一u ( i + 1 ) 。则p 1 p 2 只为t 中一条长为 ( 啦- t - 1s9 住一1 ) 的( ， ) 一路由此三种情形我们可知在t 中存在长为 k ( 1sk n 一1 ) 的( “，口) 一路，定理得证 由定理2 2 3 的证明，我们容易找到阶为n 的连通的但非强连通的竞赛图中的泛 连通性点对下面我们将给出找阶为n 的连通的但非强连通的竞赛图t 中的泛连通 性点对的算法 算法 1 找t 的强连通分支掣0 = 1 ，2 ，t ) 2 确定t 的强连通分支无圈序，不妨设该无圈序为噩，乃，丑 3 设u y ) ， y 伍) ，则 u ， ) 即为所求的点对 定理2 2 4 找阶为n 的连通的但非强连通的竞赛图t 中的泛连通性点对f “， 的时间复杂度是o ( n 2 ) 证明由文【2 1 1 知找t 的强连通分支的时间复杂度为0 ( m + 竹) ( 其中i y ( t ) l = 仡，i a ( t ) i m ) 设r 的强连通分支为墨，墨，口把霹，墨，耳收缩成点 佗i ，礼；，n ，】且在收缩过程中删去重弧所得新图记为t ( i v ( t 引一t ) 易知t 中 无圈设l a ( t 引= m 7 = 生产由( 4 知可在时间o ( 亡+ m 7 ) 内找到图t 7 的无圈序， 设佗z ，n 2 ，啦为f 的无圈序故找r 的强连通分支无圈序五，乃，正的时间复 n = 。 一 9 礼 ! l n 1 | n 。：l 凫 n ! i n 一 h n 一 1 +吼 瑚 1 8 有向目的可迹性与搓连通性点对 杂度为o ( t + m ，) 令“v ( 噩) ，u y ( 正) ，则 u ，u ) 即为t 中的泛连通性点对又 t 茎他，m m 且竞赛图t 中的弧数m = ! 等旦，故找该点对的时间复杂度为d ( 扎2 ) 由定理2 2 3 我们可得到下面的推论 推论2 25 设丑，乃，正是连通的但非强连通的竞赛图r 的强连通分支无圈 序则在t 中存在泛连通性点对的个数为1 五 1 五1 由推论22 5 我们易知，当l 丑i = i 五i = l 时，t 中有且仅有一个泛连通性的点 对事实上，设“= y ( 乃) ，u = y m ) 则 u ，口) 即为该唯一的泛连通性点对由于在 竞赛图t 中无双向弧，故t 的任一个强连通分支不能恰好包含两个点，所以我们容 易得到下面的推论 推论2 2 6 设丁是阶为他的连通的但非强连通的竞赛图，则t 中不存在恰好两 个泛连通性的点对 可传递的竞赛图显然有更特殊的结构，下面我们探讨可传递的竞赛图中的泛连通 性点对为了便于该问题的研究，我们先给出一个相关的定理 定理2 2 7 吲设有向图d 的一个强分支无圈序为d 1 ，d 2 ，d ，则d 可传递当 且仅当每个d 是完全图，且把d - ，d 2 ，皿收缩成t 个点n l ，n 2 ，n ，并把重弧 删去得到的日是一传递的定向图，即d = hc d l ，d 2 ，吼】 证明必要性：若j 皿f = l ，则d 显然是可迹的若f d ；j 2 ，则任取两点 ，v 2 y ( d f ) 因b 强连通，故在d 中存在一条( 吨，v 2 ) - 路p ，一条( v 2 ， ，) 一路0 又因 为d 可传递故v l 一忱，且u 2 一”l 所以d i 是完全图下证日是一传递的定向图， 且d = h d 1 ，d 2 ，d c 首先我们可以断然日中无各圈否则设他一嘞，码一n i ( i j ) 由上述证明知 d t 、o ，均为完全图，故d ，和d ，中的点可相互到达，这与d t 和功是d 的强连 通分支矛盾所以吼一呵与吩一m a j ) 不能同时成立即日中无2 一圈，故日 是一定向图 下证若n l n j a ( 日) ，贝4 d i 一岛因为吼a ( h ) ，所以在d 中存在两点v i ， 其中仇y ( d ) ，v j v ( d j ) 使得饥一v j 由于b 是一完全图，故一y ( 马) 一， 又d 是可传递的，所以吡一v ( d j ) 同理又因为d l 是一完全图，故v ( d ) 一饥一吡 又由d 的传递性知，任取 y ( 皿) ，我们有口一y ( 马) ，即d 一马并且由题设 知取与d ，是d 的强连通分支，则有毋一功即d = 日p 1 ，d 2 ，d t 最后证明日是可传递的不妨设n l n 2 ，m 佗3ea ( 日)由上述证明知d 1h d 2 ，玩一d 3 ，由d 的传递性知d 1 一d 3 ，所以扎l m 4 ( 日) 故日的传递性 得证 综上可知td 一日【d 1 ，d 2 ，d t ，h 是一传递的定向图，且每个d i 是完全图 充分性；设口1 2 ，v 2 v 3 a ( d ) ，只需证明v l v 3 a ( d ) 即可 竞赛图与扩张竞赛图中的泛连通性点对 1 9 情形1 设口。，u 。， 3 属于同一个强连通分支，由于d 的任一强连通分支是完全 图，故口1 v 3 a ( d ) 情形2 设v l ，优，7 3 3 属于两个强连通分支显然 l ，u 3 不在同一强分支中否则 由d 为完全图知 1 一啦一 3 一v l ，则w 2 也属于该强连通分支，这与假设矛盾 不妨设0 i ，v 2 v ( d d ，v 3 y ( 功) ，由d = 日f d l ，d 一，_ d d 知，d i b ，所以 v l v 3 a ) 情形3 设 1 ，u 2 ，u 3 属于兰个不同的强连通分支不妨设v l y ( _ d 。) ( i 一1 ，2 ，3 ) 由d = h d l ，d 2 ，n j ，故d l d 2 ，现一d 3 又日是传递的定向图，所以 d 1 一d 3 ，故u l u 3 ，即 1 钝a ( d ) 所以d 是可传递的，定理得证 定理2 2 8 若d 是可传递的竞赛图，则在d 中仅有唯一的泛连通性点对 证明先证泛连通性点对的存在性 由于d 是可传递的竞赛图。则我们可断言d 中无圈下面用归纳法证明此断言成 立首先竞赛图d 中无2 圈，又由_ d 的传递性知，若x y a ( d ) ，y zea ) 扣z ) ， 则有z z a ( d ) ，即d 中无z x 弧，显然d 中亦无长为3 的圈，假设d 中不存在长为 k 的圈，若能证明d 中也不存在长为k + l 的圈，则我们的断言得证不妨设d 中 有长为k + 1 的圈c = 饥啦v k v k + l u l ，由于v l v 2 ，v 2 v 3 a ( d ) ，且d 是可传递的， 则口- v 3 4 ) ，故d 有长为k 的圈，这与假设矛盾，所以d 中不存在长为k + 1 的 圈，即可传递的竞赛图中无圈因d 是连通的但非强连通的竞赛图，由定理2 2 3 知 d 有泛连通性点对 下证泛连通性点对的唯一性 由于d 是可传递的竞赛图，则由定理2 2 7 知_ d 的强分支无圈序d 1 ，d 2 ，n 中的每个强分支_ d 。是完全图若存在一强分支b ，使i y ( 马) l 2 ，则在功中有 圈，故d 中也有圈，这与d 中无圈矛盾，所以i y ( 觑) f = 1 0 = l ，2 ，) 不妨设 d 的强分支无圈序为1 ，2 ，由于d 是竞赛图，故址一v j ( i c 7 由定义2 1 1 0 我们知道，若g 与c 是半完全多部有向图d 的圈因子，则在图 4 中，除了情形( d ) 之外，( a ) ，( b ) ，( c ) 三种情形均是d 的好圈因子 定理2 3 1 若半完全多部有向图d 有好圈因子g - u 岛，则d 是哈图，且找其 h a m i l t o n 圈的时间复杂度是o ( i v ( c t ) l l v ( g ) i ) 证明情形l ：设e - 与g 中至少有一个圈没有奇异点，( 图4 的情形( a ) ) 如果g l 与国均没有奇异点，则由引理2 1 1 5 可知d 是哈图，并且找其h a m i l t o n 圈的时间复杂度是o ( i v ( c , ) l l v ( 岛) j ) 现假设固q 与q 中有且仅有一个圈无奇异点不失一般性设q 有外奇异点， 而岛没奇异点，即岛中的任意点既控制g ，中的某些点，又被g ，中的某些点控 竞赛图与扩张竞赛图中的泛连通性点对 2 1 制，故c 中至少有一点不是外奇异点设。矿( c 1 ) ，使得。是外奇异点，而一是 非外奇异点则岛中有点y 控制z + 若z 与g 相邻，由于z 是c 1 的外奇异点，故。一y ，则可插入到c 】中假设d 中无h , n i l t o n 圈，则由引理2 1 1 6 可知岛中任意弧z ，或弧z 可插入到c l 中， 或两点。与y 均可插入到c 1 中现设路p = c 2 旷，圳，由上面分析知可插入到口 中，则由引理2 11 7 知在d 中存在圈z ，使得v ( z ) = v ( c 1 ) u v ( p ) = v ( c 1 ) u v ( q ) ， 则z 即为d 的h a m i l t o n 圈，这与假设d 中无h a m i l t o n 圈矛盾故z 与y 相邻时， d 中有h a m i l t o n i a n 圈 若。与y 不相邻，由于d 是半完全多部有向图，且z 是外奇异点，故。一g + 否则若。与y + 亦不相邻，则y + 与y 是相似点矛盾此时c 1 i