（运筹学与控制论专业论文）竞赛图的外弧泛圈性.pdf

中文摘要 中文摘要 本文分为三章文中主要讨论了竞赛图中的外弧泛圈点问题以及在若干限制条件 下的几类强连通竞赛图的外弧泛圈点问题 第一章主要介绍了本文的研究背景和相关内容 第二章是预备知识在本章中，详细介绍了一些重要的。基本的定义如竞赛图， k 强连通竞赛图以及外弧泛圈点等重要的概念和定义并且在本章还详细给出了在第 二章中将要用到的所有的引理和定理 第三章给出并证明了本文的全部重要结果第3 1 节中主要给出了具有强连通分 解的竞赛图在某些限制条件下具有3 个外弧泛圈点的两个充分条件y e o 在文献【3 】 中曾经猜测2 - 强连通竞赛图包含3 个外弧泛圈点在第3 2 节中，我们主要证明了 对2 - 强连通竞赛图t ，如果饥，也是r 的外弧泛圈点，并且t 一 口1 ，也) 不是强连通 的，那么t 包含个不同于仇，也的顶点协，使得姐是t 的外弧泛圈点第3 3 节 主要讨论了3 - 强连通竞赛图的外弧泛圈点问题本节中使用路收缩运算证明了一个 3 _ 强连通竞赛图t 至少包含3 个顶点口l ，忱，地，使得的所有外弧是4 - 泛圈的，其 它两个顶点是t 的外弧泛圈点本节中的另外一个结论是如果口1 是3 - 强连通竞赛 图t 中外度最小的顶点，也是+ ( ”1 ) 中外度最小的顶点，那么t 包含个不同于 t ，l ，v 2 的顶点，使得v 3 是t 的外弧泛圈点在第3 4 节中，我们主要讨论了4 - 强连 通竞赛图在度约束条件下包含3 个外弧泛圈点的一个充分条件 关键词：竞赛图；强连通竞赛图；外弧泛圈点；强连通分解；路收缩 中圉分类号；0 1 5 7 5 a b s t r a c t t h i sp a p e ri sc o m p o s e do ft h r e ec h a p t e r s i nt h i sp a p e r ，t h ep r o b l e m so ft h e o u t - a r c sp a n e y d i ev e r t i c e sf o rt o u r n a m e n t sa n daf e wk i n d so fs t r o n gt o u r n a m e n t sa r e d i s c u s s e du n d e rs o m ec o n s t r a i n e dc o n d i t i o n s i nt h ef i r s tc h a p t e r ，t h eb a c k g r o u n da n dt h er e l a t e dc o n t e n t sa r ei n t r o d u c e d i nt h es e c o n dc h a p t e r ，t h em a i nc o n t e n t sa r ep r e l i m i n a r i e s s o m ei m p o r t a n ta n d b a s i cd e f i n i t i o n sw h i c hl i k et o u r n a m e n t s ，k - s t r o n gt o u r n a m e n t sa n do u t - a r e sp a n c y e l i e ，e t ea r ei n t r o d u c e di nd e t a l l t h el e m m a sa n d t h e o r e m sw h i c ha r er e l a t e do ft h ep a p e r a r ei n t r o n d u c e di nt h i sp a p e r ，t o o i nt h et h i r dc h a p t e r ，a l lo fi m p o r t a n tr e s u l t sa r e g i v e na n dp r o v e d t w o s u f f i c i e n t c o n d i t i o n st h a tt h et o u r n a m e n t sw h i c hh a v es t r o n gd e c o m p o s i t i o nh a v et h r e eo u t - a r c s p a n c y c l i ev e r t i s e sa r ed e s c r i b e du n d e rs o m ec o n s t r a i n e dc o n d i t i o n si ns e c t i o n3 1 y e o c o n j e c t u r e dt h a tt h e r ea r et h r e eo u t - a r e sp a n c y c l i ev e r t e i c e si na2 - s t r o n gt o u r n a m e n t s i nb i b l i o g r a p h y 3 ks e c t i o n3 2 w ep r o v et h a ta2 - s t r o n gt o u r n a m e n ttc o n t a i n sa v e r t e xv 3w h i c hi sn o ts a m et ot i la n dv 2i fv la n d 地a r eo u t - a r c sp a n c y e f i cv e r t i c e so f ta n d t - 口1 ，地 i sn o ts t r o n g i ns e c t i o n3 3 ，t h eo u t - a r c sp a n c y c l i cp r o b l e n mo f a3 - s t r o n gt o u r n a m e n ta r ed i s c u s s e d i nt h es e c t i o n ，w eu s ep a t h - c o n t r a c t i o nt op r o v et h a t a3 - s t o n gt o u r n a m e n ttc o n t a i n sa tl e a s tt h r e ev e r t i c e s 口l ，也，蚀a n da l lo fo u t - a r e so f 地a r e4 - p a n c y c l i e ，t h er e s tv e r t i c e sa r eo u t - a r e sp a n c y e l i cv e r t i c e s a n o t h e rr e s u l tt h a t 83 - s t r o n gt o u r n a m e n ttc o n t a i n s8o u t - a r o sp a n c y c l i cv e r t e x w h i c hi sn o ts a m et o 7 1 1a n d7 1 2i ft h eo u t - d e g r e c so f7 1 1a r e l i l 】i m mi nv ( t ) a n dt h eo u t - d e g r e e so f 吨a r e m i n i m u mi n ( ”1 ) i sp r e s e n t e di nt h i ss e c t i o n i ns e c t i o n3 4 ，w ed i s c u s sp r i n c i p a l l ya s u f f i c i e n tc o n d i t i o nf o ra4 - s t r o n gt o u r n a m e n tw h i c hi n c l u d e st h r e eo u t - a r c sp a n c y c l i e v e r t i c e su n d e rd e g r e ec o n s t r a i n e de o n d i t o n s k e yw o r d st o u r n a m e n t s ，s t o n gt o u n a m e n t s ，o u t - a r c sp a n c y c l i cv e r t 镪s t r o n g d e c o m p o s i t i o n ，p a t h - c o n t r a c t i o n c l c0 1 5 7 5 承诺书承话吊 本人郑重声明：所呈交的学位论文，是在导师指 导下独立完成的，学位论文的知识产权属于山西大学。 如果今后以其他单位名义发表与在读期间学位论文相 关的内容，将承担法律责任。除文中已经注明引用的 文献资料外，本学位论文不包括任何其他个人或集体 已经发表或撰写过的成果。 姗。铭薪妈 2 0 0 7 年多月万日 l 第一章研究背景及相关内容的介绍 第一章研究背景及相关内容的介绍 图论是数学中新兴的一个分支，其最早起源于十八世纪1 7 3 6 年，瑞士数学家 欧拉发表首篇图论论文被称为图论之父随着科学研究的不断发展，图论的应用范围 越来越广图论不但在数学方面作用巨大，同时，对电信网络、计算机程序设计、反 馈理论、随机过程、可靠性理论，以及人工智能等也产生了很大的推动作用 2 0 世 纪，由于高速计算机的出现，使得图论的发展更加迅速与此同时，图论本身的理论 也取得了很大的进展，它与其它数学学科联系紧密，起到了互相促进的作用从数学 教育的角度看，图论对于锻炼学生的组合思维能力，提高运用数学工具描述和解决实 际问题的能力也大有裨益因此，当前图论在全世界数学界、教育界、工程技术界受 到了越来越广泛的重视图论的应用之所以如此广泛，在于它可作为分析处理多种同 题的一种较为理想的数学模型，它的算法又可借助计算机实现因而图论与多学科相 结合为图论的研究和应用开辟了广阔的前景 本文只对有限图进行研究有限图分为有向图和无向图两类自上世纪7 0 年代 以来，随着图论研究的不断深入以及生产过程中若干实际问题的提出，人们更多地转 向于对有向图的研究竞赛图是类非常有用而且有趣的有向图，而研究有向图的泛 圈点同题更是当今图论研究过程当中的类热点问题1 9 8 0 年，t h o m a s s e n 证明 了每一个强连通竞赛图包含个顶点x ，使得这个顶点的每一条外弧都包含在一个 h a m i l t o n 圈中2 0 0 0 年，姚天行，郭余宝等经过进步的研究，推广了上述结果 的研究范围他们证明了个强连通竞赛图包含一个顶点z ，使得霉的每一条外弧都 是泛圈的，同时他们还给出了这个外弧泛圈点的多项式算法2 0 0 1 年，t e w e s 和 v o l k r n a n n 研究了个内竞赛图的点肛泛圈性问题他们对个强连通内竞赛图t 的最小度给出了一个更精确的下界，使得这个强连通竞赛图是点舡泛圈的，其中k 5 并且k n 一3 并且还猜想了，对个阶为n 的强连通内竞赛图，如果满足其最小度 大于雨i 9 + ( n f 一- k 1 ) - 2 1 ) 研+ 1 ，那么图t 就是点泛圈的而在2 0 0 2 年，r a n d e r a t h 等人研 究了点泛圈图的问题，在【8 】中，他们给出了使得个图是点泛圈的若干充分条件 2 0 0 4 年，p e t e r s 和v o l k m a n r t 证明了当k 6 时t e w e s 等人在【1 0 】中提出的猜想 是正确的 m o o n 曾给出，对所有非平凡的强连递竞赛图正h ( t ) 3 而h a y e r 给出，对 竞赛图的外弧泛圈性 所有2 - 强连通竞赛图 ( t ) ，其中 ( r ) 表示有向图t 中属于同一个h a m i l t o n 圈的 泛圈弧的最大个数进步地，2 0 0 5 年，y e o 对个b 强连通竞赛图中的泛圈弧 的个数进行了研究和证明在【3 】中，y e o 证明了对个肛强连通竞赛图t ，k 2 ， 有p ( 印譬，h ( t ) 2i ! 此处p ( d 表示有向图t 中瑟圈弧的个数由此就解决 了h a y e r 提出的一个猜想，即对任意的缸强连通竞赛图t 存在一个常数o ，使得 p ( t ) n k n 同时，y e o 在f 3 l 中提出一个猜想，即若t 是一个二强连通竞赛图，财它包含3 个不同的顶点z ，y ，。，使得$ ，y ，z 的每一个外弧均是泛圈的本文对此猜想在某些条 件下进行了一定的研究和证明，并且得到了一些相关的结果在 3 】中，y e o 证明了 每个3 - 强连通竞赛图至少包含2 个外弧泛圈点，在本文中也将对这一问题作更深一 步的研究和探讨 另外，本文还给出许多与主要结论相关的定义与引理，这部分内容也是关于强连 通竞赛图所具有的泛圈点性质研究的一个较为全面的资料 2 第二章预备知识 第二章预备知识 2 1 术语和记号 首先对文中经常用到的一些概念加以说明，下面的定义是规范的，不常见的术语我 们给出其出处，其它用到但未定义的图论术语见文【l 】，设t 是个有向图，y ( ，a ( 即， n 分别表示t 的顶点集，弧集和顶点数除特别声明外本文中提到的图均指无环且无 平行弧的有向图 定义2 1 1 个图称为有限图，如果它的顶点集和边集都有限本文只研究有限 图，故术语“图”一词总是指有限图” 定义2 1 2 只有一个顶点的图称为平凡图，其余的图称为非平凡的 定义2 1 3 设t 是个有向图，如果它的任意两个顶点之间有且仅有一条弧，那 么称t 为竞赛图 定义2 1 4 对有向图t ，$ ，暑，v 口) ，如果硼j 4 ( 刁，则称z 控制y 或趔是嚣 的一个外弧，记作。一，我们用a b 表示。一b ，v d a 并且v b b 如果 a = 8 ) ，则用i f , 一b 来代替以一b ；如果b = 6 ) ，则用4 一b 来代替a b z 控制( 控制霉) 的所有顶点组成的集合，称为z 的外邻( 内邻) ，记作吩( 功( ：( 茹) ) 并且，瞄( z ) = f j 时( 动i ，喀( z ) = i 婀：( z ) 1 分别称为。的外度和内度如果上下文不 引起歧义，可忽略下标r 定义2 1 5 对于有向图t ，称矿( t ) = r a i n 露( $ ) ：z y ( ( 6 - ( 印= m i n d - ( x ) ：y ( 巧 ) 为t 的最小外( 内) 度，称矿( 印= 矿口) ，6 - ( t ) 为t 的 最小半度称+ ( 力= m o $ 瞄( z ) ：$ y ( ”) ( 一( t ) = m d _ ( 妨：。y ( ) ) 为t 的最大外( 内) 度，称o ( d = z x + ( q ，a 一( ) 为t 的最大半度如果r 满足 矿( t ) = a o ( t ) ，则称t 是正则的 定义2 1 6 把无向图d 的每条边 z ，) 用弧叼或弧妒或弧吲和妒代替所 得到的有向图t 称为无向图d 的双重定向图 定义2 1 7 如果对任意。，y ( 刃，t 中都存在( z ，! ，) 路，则称t 是强连通的 如果i y ( 刃i k + 1 ，且对任意u v i 刃，i u l k l ，都有t 一厂是强连通的，则 称t 是肛强连通的 3 竞赛图的外弧泛圈性 定义2 1 8 一条弧或一个顶点被称为缸泛豳的，是指它包含在所有乒圈中，其 中 = k ，k + 1 ，n 特别的，当k = 3 时，称这条弧是泛圈的这里讨论的圈郡是 有向圈，并且扛圈是指长为i 的圈个顶点被称为外弧泛圈点。是指这个顶点的每 一条外弧都是泛圈的如果一个图包含长为竹的圈，则这个圈称为h a m i l t o n 圈，这 个图称为h a m i l t o n 图如果个图包含长为竹的路，则这条路称为h a m i l t o n 路 定义2 1 9 设z ，| ，y ( 刃，尸是t 上的一条0 ，们路，称r 是收缩p 到删得 到的图，如果以下三条成立。 ( 1 ) y ( 2 1 ) = ( v ( t ) y ( p ) ) u ， ( 2 ) 蛄( ) = 川( 暑，) n ( y ( 刁y ( 尸) ) ，v ；( ) 一v ；( $ ) n ( y ( 刃y ( p ) ) ， ( 3 ) 对s ，t v ( r ) 矿( p ) ，s t a ( r ) 当且仅当彪a ( 注意到，伽，t ，是r 中的一条路当且仅当口，电是t 中的一条路类似地，r 上 存在包含w 的肛圈当且仅当t 上存在包含p 的( k + i 且( p ) i ) 一圈 定义2 1 1 0 对于有向图r ，称r 中最短圈的长度为t 的围长，记为9 口) 2 2 相关结论 定理2 2 1 ( 【2 】) 非平凡竞赛图t 包含h a m i l t o n 圈当且仅当? 是强连通的 引理2 2 2 ( 3 0 设r 是个2 - 强连通的竞赛图，如果铡a ( 刃，满足d + ( 掣) 扩( o ) ，则是泛圈的 引理2 2 3 ( 【3 】) 设t 是强连通有向图，茁y ( 研，如果t z 是竞赛图且醇( o ) + 薛( z ) f v ( t ) i ，则顶点z 是二泛圈的 定理2 2 4 ( 【4 】) 正则竞赛图中的每条弧都泛圈 定理2 2 5 ( 【1 】) 强连通竞赛图的每个点是泛圈的 定理2 2 6 ( 【5 】) 每个强连通竞赛图包含一个外弧泛圈点 引理2 2 7 ( 1 3 1 ) 设r 是个舡强连通竞赛图，k 1 ，并且设s 是t 中的个 分离集，使得d = t s 是个竞赛图设d 1 ，功，d r ( r 2 ) 是d 的强连通分 支，使得d 1 辛d 2 号专上i 则下面的结论成立t 。( 1 ) s 中至少有k 个顶点控制d 1 中的某些顶点，并且s 中至少有七个顶点被工) r 中的某些顶点所控制 4 第二章预备知识 ( 2 ) 对任取u d - ，口d r ，在d 中存在一条长为t ( 1 z i v ( d ) i ) 的( “，口) 路 ( 3 ) 若s = z ) ，则z 在t 中是泛圈的 引理2 2 8 ( 【1 1 】) 每个包含7 1 , 个顶点和至少n m + 1 ) 一1 条弧的h a m i l t o n 图 是泛圈的 引理2 2 9 ( 1 1 ) 个具有r 个顶点的强连通的局部半完全有向图t 包含长度为 后，k + 1 ，r 的圈，其中k = 9 ( t ) 引理2 2 a 0 ( 1 2 ) 设t 是一个强连通的局部竞赛图，i y ( 刃l = t 1 如果t 不是圆 可分解的，那么t 是点泛圈的 定理2 2 1 1 ( 1 3 ) 每个至少包含5 个部集的正则多部竞赛图是点泛圈的 5 第三章主要结论 第三章主要结论 3 1 竞赛图中外弧泛圈点问题的讨论 引理3 1 1 每个强连通竞赛图一定存在3 个顶点饥，也，地，使得从“= 1 ，2 ，3 ) 的每一条外孤都在一个3 圈上 证明设t 是个强连通竞赛图，i 矿( t ) i = ，设铆是t 中外度最小的顶点，设 是+ ( 口1 ) 中任意一点，y 是+ ( z ) 中任意个顶点，假设f 不控制v l ，即口1 控 制+ ( 正) 中每个点又因为仇一士，所以扩( 口1 ) 扩( g ) ，这与口1 的定义矛盾， 所以y 一饥，贝! ；v a x y v l 是一个包含口1 z 的3 - 圈设v 2 是j v + ( v 1 ) 中外度最小的顶 点，设z 是+ 池) 中任意一个顶点如果一口l ，则也l 也是个包含抛z 的3 - 圈因此不妨假设”l 一茹，如果+ ( 霉) 中存在一点y ，使得y v 2 ，则v 2 x y v 2 是个 包含现z 的3 - 圈因此假设+ ( 甸中所有点都被沈控制，故扩他) d + ( ) ，这与 也的定义矛盾如果+ ( u 1 ) n + ( 吨) 0 ，则取+ ) n + ( 也) 中外度最小的顶 点记为任取z n + ( ) ，如果害一饥0 = 1 或 = 2 ) ，则 0 3 x v i v 3 是个包含功z 的3 - 圈因此设仉_ z ，且蚀。z ，任取暑，( 岳) ，如果y _ 珊，则v 3 x y v 3 是一 个包含v 3 x 的冬圈因此假设+ ( 功中每一点都被啦控制，则扩( 蚀) 矿( 功，这 与珊的选取矛盾如果+ ( 1 ) n + 他) = 0 ，则选取+ 她) 中外度最小的顶点记 为，有一口l ，可知r a y l 包含在3 - 圈诒饥忱姐中任取顶点z n + ) w l ， 如果z 一忱，则z 吻地是一个包含地$ 的3 - 圈。因此不妨设吨一z ，任取顶点 y + ( z ) ，如果y - + 堍，则v a x y v 3 是个包含v 3 x 的3 - 圈因此不妨设n + ( 中 每一点都被控制，则d + ) d + ( 霉) ，与的选取矛盾 口 引理3 , 1 2 设t 是强连通竞赛图，t ，是t 中所有外弧包含在3 圈中的顶点，如 果$ + ( 口) ，则t z 中包含以口为终点的h a m i l t o n 路 证明如果t 一是强连通的，则t 一茹中包含个h a m i l t o n 圈c ，从而g ( t ，+ ，纠 是以t ，为终点的h a m i l t o n 路如果t 一是不强连通的，设毋，马，正是t z 的强连通分支无圈序若t ，彗v ( 卫) ，对任意可y ( 噩) 咎一弘易见鲈的外邻只可能 是。或五中其它点，但这些点均不控制t ，这与 $ 包含在个3 圈中矛盾因此， t ，y 仍) 容易证明，此时，r 一嚣也包含一条以口为终点的h a m i l t o n 路 口 6 竞赛图的外弧臣圈性 引理3 1 3 设t = r d 1 ，d 2 ，d r 】( r23 ) 是一个竞赛图，其中，d i “= 1 ，2 ，r ) 是单点或强连通竞赛图，且是一个竞赛图，且收缩每个d i 得蛩顺点孔， 即v ( r ) = z l ，x 2 ， ( 1 ) 如果曩z j a ( r ) 在五中是泛圈的，则对任意y ( d ) ，y y ( 功) ，x y 在 t 中也是泛圈的； ( 2 ) 如果口y ( d i ) 在子图d t 中每条外弧都包含在3 圈中，且r 是强连通的， 猁对任意z + n 矿( 盈) ，卯在r 中也是泛西的 证明( 1 ) 由于巧在r 中是泛圈的，敌矗在只中包含在所有长为3 ，4 ，r 的圈中。设c 是r 的个通过弧z 1 的h a m i l t o n 圈，则对任意的z 矿( 觑) ， y ( 易) ，口也可看作t 中通过习的个长为r 的圈 由于每个d k 是单点或强连通竞赛匣，则它有h a m i l t o n 圈g 当k i ，j 时， 取r 为瓯任意去掉条弧得到的h a m i l t o n 路，当k = i 时，取只为仇去掉弧 + 得到的h a m i l t o n 路，即只是以耋为终点的h a m i l t o n 路，类似她，当k = ， 时，取马为瓯去掉弧y - y 得到的h a m i l t o n 路，即只是以y 为起点的h a m i l t o a 路这样由g 出发，每次沿着最 = l ，2 | ，r ) 的方向增加个顶点，得到所有长 为r + 1 ，r + 2 ，l 的圈，且由最的构造过程可以看到，这些圈均包含z 玑因此， 雄是泛圈的 ( 2 ) 对任意z + ( ) n y ( d t ) ，由题设可知，t ，z 包含在3 - 圄中，下证u 在r 中是4 - 泛圈的由 l 理3 1 2 ，衄一z 包含条以t ，为终点的h a m i l t o n 路，记为只 当k l 时，同( 1 ) 取最是p i 中的h a m i l t o n 路 由于月是强连通的，根据定理2 2 5 ，妨是惩圈的，耶戤包含在长为3 ，4 ，r 的圈中从而口在t 中包含在所有长为4 ，5 ，一，r + 1 的圈中设长为r + 1 的圈为 g 于是，由d 出发，每次增加r 上的个顶点得到所有长为r + 2 ，r + 3 ，竹的 盈且这些圈都包含骝因此，馏是泛圈的 口 定理3 1 4 设t = r 吼，d 2 ，d r 】聊竞赛图，其中皿a = 1 ，2 ，r ) 是单 点或强连通竞赛图，r 是正则竞赛图，且l y ( r ) l = r 则 ( 1 ) 如果l y ( b ) j = 1 ，则此顶点是t 中的个步卜弧泛圈点 ( 2 ) 如果i y ( 毋) i 3 ，则n j 包含t 中的3 个外弧泛圈点 证明由定理2 2 4 可知，r 中的每条疆都泛圄当j y ( d d l = 1 时，设矿( 现) = 口) ， 7 第三耄主要结论 z n + ( 口) ，由引理3 1 3 ( 1 ) 可知，t ，茹在t 中琵圈从而， 是外弧泛圈点 当i y ( d j ) i = 3 ，根据引理3 1 1 ，皿包含3 个顶点，记为仇，地，地，使得每条从 地( = 1 ，2 ，3 ) 出发的弧都包含在珐内的3 圈中对任意g n + 似) ，当z 1 ，( d j ) 时，由于正贝4 竞赛图均强连通，根据引理3 1 3 ( 2 ) ，u 在t 中是泛圈的当z 簪y ( 功) 时，由引理3 1 3 ( 1 ) ，可知忱z 是泛圈的因此口l ，t j 2 ，啦均是t 中的外弧泛圈点 口 定理3 1 5 设t = r 【d i ，d 2 ，。珥1 是个竞赛图，其中皿“= 1 ，2 ，r ) 是非 平凡强连通竞赛图，兄是个强连通竞赛图则t 至少包含3 个外弧泛圈点 证明设表示收缩觑得到的顶点，即v ( r ) = z l ，z 2 ，研) ，由于r 是强连 通的，根据定理2 2 6 ，存在i 1 ，2 ，r ) ，满足是月中的外弧泛圈点又由于 功是强连通竞赛图，由引理3 1 1 可知，存在3 个顶点，y ，z y ( d i ) ，使得z ，y ，z 在 d t 中的每条外弧都在3 - 圈中下证z ，y ，2 是r 中的外弧泛圈点下面以$ 为饲， 对$ 的所有外弧分情形讨论设踟a ( r ) 是茹的条外弧 情形l ：口y ( d 1 ) 由引理3 1 2 ，d l t ，存在条以为终点的h a m i l t o n 路只 由定理2 2 6 ，8 在r 中包含在长为从3 到r 的圈中。将蜀用。口代替，得到包 含删的所有长为4 ，5 ，r + 1 的圈又由于每个马0 l ，2 ，r ) 且j 1 ) 包 含一条h a m i l t o n 路且毋一口存在一条以。为终点的h a m i l t o n 路，故我们不难从 翩，所在的长为r + 1 的圈，得到所有长为r + 2 ，l y ( t ) i 的圈又因为包含在 3 - 圈中，所以在t 中是泛圈的 情形2 ：口圣y ( 功) 由于翱是r 的外弧泛圈点，故删包含在长为3 ，4 ，r 的 圈中，由于每个易0 l ，2 ，r ) ) 且 包含一条h a m i l t o n 路且皿存在一条 以为终点的h a m i l t o n 路，与情形1 类似，可以得到长为r + 1 ，l y ( 即i 的圈 因此，z 是外弧泛圈点同理，y ，z 也是外弧泛圈点 口 3 22 - 强连通竞赛图和墨强连通竞赛图中外弧泛圈点问题的讨论 引理3 2 1 设? 是个孓强连通的竞赛图，x y z 是r 中条长为2 的路设 是收缩x y z 到 得到的图。则是强连通的 证明显然有瓦一西= t - z ，弘z ) 是竞赛图，如果死一 强连通，由定理2 2 1 可知，一伽包含个h a m i l t o n 圈g 由于妨( 2 ) 3 ，喀( 3 ，则z 控制g 上 8 竞赛图的外弧泛圈性 的某个顶点且。被g 上某个顶点控制，故 在v ( c ) 中既有外邻。又有内邻，因此 是强连通的 如果蜀一 不是强连通的，即t 一 。，y ，z ) 不是强连通的，设噩，正，霉是 t 一 ，y ，z ) 的强连通分支，满足乃一死一一耳如果d + i ( z ) = 0 或d 云( z ) = 0 ， 我们将有t 一伽，! ，) 或t 一 玑z 不强连通，这与t 是3 - 强连通有向图矛盾故有 畦( 。) 2 1 且( z ) 1 ，从而畦( ) 之1 且( t l ，) 1 因此死是强黼的 定理3 2 2 设t 是3 - 强连通竞赛图，则t 中包含至少3 个不同顶点 l ，忱，地，使 得口1 ，t j 2 的所有外弧是3 - 泛圈的，蚀的所有外弧是垂泛圈的 证明设m 表示t 中所有最小外度顶点组成的集合，由引理2 2 2 可知，m 中 所有顶点的外弧都是3 瑟固的若f 膨f 2 ，取口l ， 0 2 m ，不妨设饥一t j 2 若 i m i = 1 ，取饥m ，取他为口i 的外邻中外度最小的点下面证明当i m i = 1 时，对 任何茹n + 池) ，都有t 1 2 是3 _ 泛圈的事实上，若d + ( z ) d + 池) ，由引理2 2 2 ， 可知地z 是孓泛圈的，下面我们假设矿( 动l y ( ) i 刚乱，在正中是2 泛圈的，从而 u 3 v 2 是4 - 泛圈的 定理3 2 3 设t 是个3 - 强连通竞赛图设t ，1 是t 中外度最小的顶点，也是 + ( 口1 ) 中外度最小的顶点，且+ ) n + ( 地) 死则t 包含个不同于姐，地的 顶点他，使得地是外弧泛圈点 证明设蜥是+ ( 口1 ) n n + ( v 2 ) 中外度最小的顶点设z 是+ ) 中任意个顶 点下证或者弧地z 是泛围的，或者存在另外一个不同于 l ，睨， 0 3 的顶点满足结论 如果扩p ) 2d + ) ，则由引理2 2 2 知弧锄z 是泛圈的，结论得证因此不妨 设d + ( 互) d + ( 口1 ) 设d 是通过将t 中的路 口1 霉收缩为点得到的有向图易知，矗+ ) + d 一( 脚) 扩( 妨一1 + 扩忱) 一1 = 矿( z ) 一1 + ( n 一1 一矿h ) ) 一1 n 一2 = i v ( d ) i t 是3 - 强连通的。故d 是强连 通的由引理2 2 3 ，在d 中存在包含 t o 的f - 圈，2 j s l v ( d ) 1 因此在t 中存在 包含t j 3 z 的缸圈，对所有4 詹曼i y ( 刃i ，从而v s x 是泛圈的 口 定理3 2 4 设t 是个二强连通竞赛图，m ，t j 2 是t 的两个外弧泛圈点若 t 一 口l ：t j 2 不是强连通的，则t 包含个不同于 0 1 ，他的顶点地，使得地是t 的 个外弧泛圈点 1 0 竞赛图的外弧泛圈性 证明不失一般性。设 l t j 2 设置，疋，耳( r22 ) 是t t 口1 ，忱) 的强连通 分支，使得丑一乃一一矸通过如下规则选取协，若耳是一个单点，则选取 这个单点作为地；若乃不是单点，则诒是露中一个外弧泛圈点( 注意到定理2 2 6 保证了这个顶点的存在) 由于t 是2 一强连通的，故存在y ，z y ( 五) ，使得仇一y 且t j 2 _ z 设z 是他的一条外弧 情形1 ：霉y ( 耳) 设1 1 旷( 耳) i = m 由于3 z 在耳中是泛圈的，易知v 3 x 处 在长为k ( k = 3 ，4 ，m ) 的圈里设x l x 2 z 。善l 是乃中通过弧 0 3 x 的h a m i l t o n 圈，其中。l = 地，x 2 = 若存在某个j 2 ，3 ，m 一1 ) 使得巧一口l ，则 诒铀x j v l y x j + 2 地是通过地。的m + l 一圈，并且可知诒3 - x j v l v 2 z x j + 2 协， 蚀撕巧口l 他z 2 f + l 蚀分别是通过地$ 的m + 2 一固和m + 3 - 圈而且从这个 m + 3 - 圈，每次增加个点，得到所有长为m + 4 ，n 的圈，结论得证因此假 设n h 娩，x 3 ，一1 ) ，则t j 3 - + v l 且- t ，l ，否则 0 1 v 3 不在任何3 - 圈里，或 饥规不在任何参圈里类似地，若存在某个j 2 ，3 ，m 一1 ) 使得码一u 2 ，则 v 3 x x 3 x j v 2 z x j + 2 珊，钝”3 l ”1 ，z l ，铅z 船x m u i , 1 2 z z l 分别是m + 1 - 豳， m + 各圈和m + 3 - 圈并且，从m + 3 - 圈每次增加个点，得到所有长为m + 4 ，n 的圈，结论得证因此假设忱h 勋，如，一1 ) ，则d + ( v 2 ) 1 + m 一2 = m 一 1 ，扩( 口1 ) 2 + m 一2 = m 此外，由于地巧在耳中，包含在个3 - 圈里，故巧一 从而扩( ) 3 当m 4 时，有d + ) 扩( ) ，d + ( 口1 ) 2 矿( ) ，因此这个具有 最小外度的顶点包含在y ) 中，并且根据引理2 2 2 ，我们可选择t 中最小度顶点 作为铅( 由上面讨论可知，这个点不同于吼，地) ，所以结论得证当m = 3 时，如果对 某个i 1 ，2 及某个j l ，2 ，3 有仇一即，则矿( 即) 2 此外，根据引理2 2 2 我们可选择为如，所以对所有的，= 1 ，2 ，3 ， = 1 ，2 有巧一地，易知巧巧+ 1 和饥 是泛圈的对于弧吩也，x ，v 2 z x j 是包含它的3 _ 圈，并且从这个3 - 圈我们能得到不包 含饥的所有长为4 ，5 ，竹一1 的圈设这个他一1 - 圈为g ，由于翱一砚0 ，) 且 + ( 仇) n ( y ( 噩) u y ( 霉一1 ) ) d ，故口l 可插入到g b ，】得到路尸，故p v 2 是包 含弧$ 忱的h a m i l t o n 圈 幅f 形2 ：均t ，1 易看出协仇是泛圈的 情形3 ：协吨t ，3 也是包含在3 - 圄t 坼】2 z 啦里的，并且由这个3 - 圈可获得不包含 地的所有长为4 ，5 ，n 一1 的圊类似于情形1 ，可把口1 插入到n 一1 圈中，得到 1 1 第三章主要结论 包含地地的h a m i l t o n 圈 3 34 - 强连通竞赛图中存在3 个外弧泛圈点的一个充分条件 口 引理3 3 1 设丁是个4 _ 强连通竞赛图，善i x 2 x 3 x 4 是t 中的一条长为3 的路 设死是收缩z l 观。3 轧到 得到的图，则死是强连通的 证明易知死一t ，= t 一 1 ，娩，嬲，翔 仍然是竞赛图 情形l ：如果死一 不是强连通的，即? 一 o l ，x 2 ，x 3 ，瓤) 不是强连通的，则假 设五，马，霉是? 一 z 1 ，2 ，铂 的强连通分支，满足t l 一疋一，耳如果 珐( 铂) = 0 或者眨( $ 1 ) = 0 ，则可知t 一 $ l ，2 ，翔，或t 一 茁2 ，如，$ 4 ) 不强连通， 这与r 是4 - 强连通有向图矛盾所以有姥( 瓤) 1 且甑( 9 4 ) 1 ，从而嚏扣) 2 1 且d - r ( ) 1 ，因此死是强连通的 情形2 ：如果死一是强连通的，由一w 包含一个h a m i l t o n 匿口因为 薛( 黝) 4 ，蝣( 乳) 4 ，则钆控制c 上的某个顶点，且$ l 被c 上某个顶点所控制， 所以w 在y ( c ) 中既有外邻，又有内邻，因此死是强连通的 口 定理3 3 2 设丁是一个4 _ 强连通竞赛图，设 l 是t 中外度最小的顶点，也是 + h ) 中外度最小的顶点，是n + ( v 2 ) 中外度最小的点若存在y + ( v 1 ) t 1 2 ， 使得矿( ) 矿( 也) + 2 ，并且对任取的z + ) 、啦都有d + ( 茁) 矿m ) + 2 ，则 t ，l ，抛是t 的外弧瑟圈点，并且t 还包含个不同于饥，钯的顶点使得口是外弧 泛圈点 证明因为t 是垂强连通竞赛图，由定理3 2 2 知啦，也是t 中的外弧泛圈点 若蜘+ h ) ，则由定理3 2 3 知存在r 中不同于。l ，地的顶点口，使得口是外弧泛 圈点，所以不妨设一口1 设茹是十帆) 仇中的任意一点，若矿( z ) 矿( 蜘) ，则 由引理2 2 2 可知，蚀。是泛圈的，故不妨设矿( 茹) d + ) 下面分情况进行讨论 情形1 ：口l z 由钝的定义可知，$ 一也再由地的定义可知，d + ( 矿( 也) 如果d + ( ) = d + 沁) ，则z 是外弧泛圈点，所以不妨设扩( 善) 矿( 地) 记d l 是收缩 路也硼砚为铆得到的图则有 竞赛图的外弧泛圈性 d 占，( 1 ) + d 五( 叫1 ) = 衅( 。) 一1 + d ；( 也) 一2 = 辞( z ) + ( n 一1 一d ；= ( t j 2 ) ) 一2 行一3 i y ( d 1 ) i 由于t 是垂强连通竞赛图，故d 1 是强连通的，并且显然d l 一 i 是竞赛图，所 以由引理2 2 3 知伽l 在d 1 中是 泛圈的。可得 0 3 9 1 在丁中是5 - 泛圈的同时， u i ，2 v 3 v 1 是包含v s r l 的个3 - 圈， p 1 t u 2 0 3 v l 是包含v s v l 的个垂圈，因此地口1 在 t 中是泛圈的设d 2 是r 收缩路睨埯聋为撕得到的图则有 咳( 耽) + d 动( 耽) ；醛一1 + 靠池) 一1 = 砖( ) 一1 + ( 礼一1 一砧( t j 2 ) ) 一1 一2 l y ( d 2 ) i 由于? 是4 - 强连通竞赛图，故d 2 是强连通的。并且玩一耽是竞赛图，所以由 引理2 , 2 3 知2 在d 2 中是2 - 泛圈的，可得z 在t 中是4 - 泛圈的又因为v 2 v s x v 2 是包含地z 的一个3 - 圈，故姐茹在t 中是泛圈的，所以地是t 中的外弧泛圈点 情形2 ：z 一 1 由于丁是4 - 强连通的，所以j + m ) 忱j 3 若存在 可n + h ) t 1 2 ，使得坳一y ，则由定理3 2 3 可知t 存在不同于仇，他的点口是泛图 点，故可设任取y n + ( v 1 ) z 2 ，有”一也，则也地口l g t ，2 是包含口l 的一个4 - 圈 若一y ，即+ ( 口1 ) n + ( ) d ，设；是+ 帆) n + ( ) 中外度最小的点，是 + ( 孑) 中任意一点着扩( 力d + ( z ) 刚由引理2 2 2 知韶7 在t 中是泛固的，故可 设a - , - c e ) a +