（应用数学专业论文）竞赛图的传递性和半完全多部有向图的3王中王.pdf

摘要 本文的研究内容涉及有向图的两个方面：多部竞赛图的传递性和半完 全多部有向图的3 王中王 n 一部竞赛图是完全n 一部有向图的一个定向当n = 2 时，称其为2 一 部竞赛图，竞赛图是恰好有礼个点的扎一部竞赛图称有向图d 是可传递 的，如果对d 中每一对弧x y 和y z ，z z ，有z z a ( d ) 在文献 1 】中，j o r g e nb a n g j e n s e n ，g r e g o r yg u t i n 证明了若有向图d 的强连通分支无圈序为d ，d z ，d 。，且d 是可传递的，则每一个d 是完 全的，且通过收缩每个现成一点，然后删除重弧得到的有向图日是一个 传递定向图，换句话即d = h d 。，d 2 ，岛】本文的第二章在此基础上给 出了多部竞赛图具有传递性的充分必要条件 有关有向图的王的研究是从1 9 5 3 年开始的，在竞赛图，多部竞赛图的 王方面已有相当丰硕的研究成果在1 9 8 0 年，m a u r e r 提出了竞赛图王中 王的概念即： 设凰是一个竞赛图，令k 2 ( h 1 ) 表示皿的2 一王的集合，对i 1 ，设 皿十t = 凰陋) ，注意到k 。( h 1 ) 三尥( 飓) 三k 。( h 3 ) 三，因为尬( 皿) 是一 个有限集，则必存在一个整数p ，使得对所有i p ，有喝( h a 十1 ) ck 2 ( h d ，且 对i p ，有魁( 皿+ t ) = k 2 ( 皿) ，m a u r e r 称任意点u 场( 珥) 为研的一个王 中王 b pt a n 将王中王的概念推广到了无发点的半完全n 一部有向图t ，且 提出了r 一王中王的概念，并证明了： 当r = 1 时，t 的1 一王中王概念无意义当r = 2 ，4 时，t 的一王中 王集合非空，指出当r = 3 时，t 的3 一王中王集合不一定非空，并提出了 问题：哪些无发点的半完全多部有向图的3 一王中王集合是非空的? 他指 出，要解决该问题只需考虑满足k 3 ( t ) l ( k a ( t ) = k 3 ( t ) ) 的无发点的半完 全多部有向图本文则在第二章中解决了如下的问题： ( 1 ) 给出了正则半完全多部有向图t 中使自。( t ) 兰l 的一些充分条件 ( 2 ) 给出满足3 一王中王集合非空的一类图 关键词：n 一部竞赛图；半完全多部有向图；传递性；王；王中王 中图分类号：0 1 5 7 5 a b s t r a c t t h em a i nc o n t e n t so ft h i st h e s i si n v o l v et w oa s p e c t so fd i g r a p h s ：t h et r a n s i t i v i t y o fm u l t i p a r t i t et o u r n a m e n t sa n dt h e3 k i n g s - - o f - k i n g si ns e m i c o m p l e t em u l t i p a r t i t e d i g r a f i h s n d a r t i t et o u r n a m e n ti sa no r i e n t a t i o no fac o m p l e t en p a r t i t eg r a p h w h e n n = 2 i ti sab i p a r t i t et o u r n a m e n tat o u r n a m e n ti sa nn p a r t i t et o u r n a m e n tt h a t c o n t a i nj u s tnv e r t i c e sad i g r a p hdi st r a n s i t i v ei f ，f o re v e r yp a i ro fa r c sx ya n dy z i nds u c ht h a to y ，t h ea r cx zi sa l s oi nd i n j o r g e n b a n g - j e n s e n ，g r e g o r yg u t i np r o v e dt h a ti fd i sad i g r a p hw i t ha n a c y c l i eo r d e r i n gd l ，d 2 ，d po fi t ss t r o n gc o m p o n e n t s i ft h ed i g r a p hd i st r a n s i t i v e ，t h e ne a c ho fd zi sc o m p l e t e ，a n dt h ed i g r a p hh o b t a i n e df r o md b yc o n t r a c t i o no f d 1 ，d 2 ，珥f o l l o w e db yd e l e c t i o no fm u l t i p l ea r c si sat r a n s i t i v eo r i e n t e dg r a p h i n o t h e rw o r d sd = h d i ，d 2 ，珐 _ b a s e do nt h ea b o v e ，w es t u d yt h et r a n s i t i v i t y o ft o u r n a m e n t s ，b i p a r t i t ea n dm u l t i p a r t i t et o u r n a m e n t s ，a n dg i v et h es u f f i c i e n t m i d n e c e s s a r yc o n d i t i o n so ft h e ni nc h a p t e r 2 f r o m1 9 5 3t on o w a b o u tt h ek i n go ft o u r n a m e n t sa n dm u l t i p a x t i t et o u r n a m e n t s ， t h e r eh a v eb e e nr a t h e ra b u n d a n tr e s u l t si n1 9 8 0 ，m a u r e ri n t r o d u c e dt h ec o n c e p t i o n o fk i n g s o f - k i n g si nt o u r n a m e n t si ti s ： l e t 研b ea t o u r n a m e n t a n d l e t 凰( 风) b e t h es e to f 2 一k i n g so f h if o r i 1 ， l e t 甄+ 1 = h d k 2 ( h d o b s e r v et h a tk 2 ( h 1 ) ，k 2 ( h 2 ) ，i sad e s c e n d i n gc h a i no f s u b s e t so f 玛( 日1 ) s i n c ek 2 ( h 1 ) i saf i n i ts e t t h e r ee x i s t sa ni n t e g e rp ，s u c ht h a tf o r a l li p ，玩( 凰+ 1 ) ck d n 0 ，a n df o ra l li p ，a ，2 ( 凰+ 1 ) = 尬( 凰) m a u r e rc a l l e d a n yv e r t e xm 尥( 珥) ak i n g - o f - k i n g s f o w l h a gm a m e r ，bp t a ni n v e s t i g a t e st h er k i n g s - o f - k i n g si ns e m i c o m p l e t e m u t i p a r t i t ed i g r a p h sw i t hn ot r a n s m i t e r sf o rr = 1 ，2 ，3 ，4 h ep r o v e st h a t ： w h e nr = i w ec a r ln o td e f i n e1 一k i n g s - o fk i n g si ns e m i c o m p l e t em u l t i p a r t i t e d i g r a p h sw i t hn ot r a n s m i t t e r s w h e nr = 2 ，4 ，t h es e to ft k i n g s - o f - k i n g , i ns e m i c o m p l e t em u l t i p a r t i t ed i g r a p h s w i t hn ot r a n s m i t t e r si sn o te m p t y w h e nr = 3 t h es e to fr k i n g s - o f - k i n g si ns e m i e o m p l e t em u l t i p a r t i t ed i g r a p h s w i t hn ot r a n s m i t t e r sm a yb ee m p t y t h e nh er a i s e st h ef o l l o w i n gp r o b l e m ： d e t e r m i n et h o s es e m i e o m p l e t em u l t i p a r t i t ed i g r a p h sw i t hn ot r a n s m i t t e r ss u c h t h a tt h es e to f3 - k i n g s - o f - k i n g si sn o ne m p t y 7 a n dh es a y st h a t ：t os o l v et h ep r o b l e m ，w ej u s tn e e dc o n s i d e rt h o s es e m i c o m p l e t e r n u l t i p a r t i t ed i g r a p h st w i t hn ot r a n s m i t t e r ss u c ht h a tj 岛( t ) 21 i nc h a p t e r3o f t h i st h e s i s ，w es o l v et h ep r o b l e m s8 8f o l l o w s ： ( 1 ) g i v eo u ts o m es u 伍c i e n tc o n d i t i o n sf o rr e g u l a rs e m i e o m p l e t em u i t i p a x t i t ed i - g r a p h stw i t hn ot r a n s m i t t e r s ( 2 ) g i v eo u ts o m es e m i c o m p l e t em u l t i p a r t i t ed i g r a p h sw i t hn ot r a n s m i t t e r ss u c h t h a tt h es e to f3 - k i n g s o f d d n g si sn o ne m p t y k e y w o r d s ：n - p a r t i t et o u r n a m e n t ；s e m i c o m p l e t en m l t i p a r t i t ed i g r a p h s ；t r a n s i t i v ed i g r a p h s ；k i n g s ；k i n g s o f - k i n g s c l cn u m b e r s ：0 1 5 7 5 引言 引言 图论作为数学的一个分支，已有二百年的历史，特别是随着计算机的 出现即广泛的应用背景，近半个世纪以来，一直是一个非常热门的研究领 域现在已成为研究系统工程，管理工程，计算机科学，通信，网络理论， 自动控制，运筹学以及社会科学等学科所必需的一种重要的数学工具图 论的应用之所以如此广泛，在与它可作为分析处理多种问题的一种较为理 想的数学模型，它的算法又可借计算机实现，因而图论与计算机的互相结 合，为图论研究与应用开辟了更为广阔的前景 图论可分为无向图和有向图，无向图的研究已相当深入，结果也非常 丰硕上世纪7 0 年代以来，随着生产中实际问题的提出，人们更多的转向 为对有向图的研究 对于有向图的研究，很多文献集中于研究一类特殊的有向图一多部竞 赛图( 竞赛图的推广) ，在这研究领域取得了一批重要的结果，特别是路和 圈方面，但是对传递性方面的结果不多，对竞赛图，和多部竞赛图的传递 性方面研究很少，本文第二章对它们进行了深入地研究，并给出了它们传 递性的充要条件 王的存在性的研究源于对竞赛图的研究，王的概念最初是在1 9 5 3 年由 数学社会学家l a u d a u 1 0 】首先提出在此研究基础上，1 9 8 0 年m a u r e r 提 出了竞赛图王中王的概念由于它在网络等方面有着广泛的应用，所以近 几年关于这方面的研究成果很多，也日趋完善 设w 是有至多一个发点的n 一部竞赛图，2 ) ，且设珥( ) 表示 的r 一王的集合，r = 1 ，2 ，讫g u t i n 在f 2 中已证明了k 4 ( w ) 1 ，并证明了 有向图中存在无数多个多部竞赛图w ，满足k 3 ( w ) = 0 且k 4 ( w ) 0 多部竞 赛图王的研究方面，众多学者在4 一王的研究方面产生很大的兴趣 设w 是n 一部竞赛图，若w 无发点，k o h 和t a n 6 证明了( 1 ) t ( w ) 4 ( n 2 ) ( 2 ) k 4 ( w ) 3 ( n 3 ) ( 3 ) 完整的描述了使( 1 ) 和( 2 ) 成立的所有的 无发点的更多关于多部竞赛图4 一王方面的结果已经在 4 ，5 ，7 9 ，1 3 ，17 中给出最近t a n ”】进一步研究了3 一王的情况，得出是一个无发点且 无3 一王的礼一部竞赛图w ，礼3 ，如果w 中有r ( 3 r n ) 个部包含的 4 一王，则乜( w ) r + 8 g u t i n 和y e o 3 则将对多部竞赛图的王的研究扩展到 半完全多部有向图中，他们研究了半完全多部有向图的4 一王，并将k o h 和 t a n 6 的( 1 ) 一( 3 ) 的结果进一步推广，他们描述了所有确定k ( k = 1 ，2 ，3 ，4 ，5 ) 个4 一王的半完全多部有向图 竞赛图的传递性和半完全多部有向图的3 一王中王 设日是一个竞赛图，那么且f 尥( 且) 1 也是一个竞赛图r e i d ”j 证明了 日f k 2 ( 日) 无发点k o h 和t a n 在9 1 中证明如果是无发点的n 一部竞赛 图( 扎3 ) 则w 玛( w ) 也无发点b p t a n 则在 2 中将上述结果推广到 半完全n 一部有向图他指出，若丁是一个无发点的半完全多部有向图，设 0 = t k 4 ( t ) ，则有：( 1 ) 0 无发点，( 2 ) k 3 ( q ) c 凰( t ) ( 3 ) k 2 ( q ) 飓( 丁) 此外，他还将m a u r e r 提出的王中王的概念推广到半完全佗有向图，并证 明了当r = 2 ，4 时，半完全n 部有向图的r 一王中王的集合非空当r = l 时，r 一王中王的概念无意义当r = 3 时，半完全佗一部有向图的r 一王中 王的集合不一定非空并指出，要解决该问题，只需考虑满足。( t ) l 的 无发点的半完全多部有向图本文在第三章中( 1 ) 给出了正则半完全多部 有向图t 中满足s ( t ) 21 的一些充分条件( 2 ) 给出满足3 一王中王集合 非空的一类图 预备知识 第一章预备知识 为了便于阅读，本章我们介绍一些与论文相关的定义，记号 定义1 1 1 有向图是指一个有序三元数组( v ( d ) ，a ( d ) ，皿( d ) ) ，其中v ( d ) 是非 空的顶点集，a ( d ) 是不与v ( d ) 相交的弧集而皿( d ) 是关联函数，它使得d 的每 一条弧对应于d 的有序顶点对( 不必相异) ，亦可简记为d = ( k a ) 称_ d 的顶点数 l y ( d ) i 为d 的阶若a = ( u ，”) 是d 的一条弧，称“控制v 或u 被“控制并称让 为a 的尾，v 为a 的头，u 和u 称为a 的端点若有方向的图d 没有环和重弧，称 d 为有向图若d 有重弧但没有环，称d 为有向多重图，简称为多重图 定义1 2 有向图d7 称为d 的子图，如果v ( d 。) v ( d ) ，a ( d7 ) a ( d ) 且 皿( d ) 是霍( d ) 在a ( d7 ) 上的限制如果v ( d ) = v ( d ) 称d 7 为d 的生成子图 定义1 3 称s l ，& 为集合s 的一个划分，如果对于所有的1 i j t ， s n 岛= d 且u ：1 s = s 定义1 4 如果途径w = x l a l x 2 a 2 x 3 z n 一1 a n l x 。的顶点z 1 ，z 2 ，z 3 ，。_ l j 均不相同，则称w 为一条有向路，简称路若研，z 2 ，z 3 ，x 。一1 互不相同且。1 = $ 。， 则称w 为圈长为礼的固称为n 一圈 定义1 5 设d 为一个有向图，称d 是强连通的，如果对于d 中每一对不同的 顶点。和y ，d 中均存在一条( 茁，y ) - 途径和( y ，。) 一途径 定义1 6 设d = a ) 为一个有向图，如果a ( d ) 的每条端点在y ( 日) v ( d ) 中的弧都在a ( h ) 中，称日是由x = v ( 日) 导出的，记为h = d ，且日称 为d 的导出子图d 的由v ( d ) 一x 导出的子图d 记为d x ， 定义1 7 设d 为一个有向图，d 的最大的强连通导出子图称为d 的一个强连通 分支若d 1 ，d 2 ，现为d 的所有强连通分支，则易知v ( d 1 ) u y ( d 2 ) u u v ( d t ) = d 且对于每个i j ，y ( d ) n y ( d j ) = 0 定义1 8 设d = ( k a ) 是一个强连通有向图，集合scv 称为d 的隔集，如 果d s 是不强连通的有向图d 是一强连通的，如果lv ( d ) 1 k + l 且d 没有 少于k 个顶点的隔集使得d 是k 一强连通的最大整数k 称为d 的强连通度，记为 k ( d ) 若d 不是强连通的，记a ( d ) = o 定义1 9 有向图d 是可传递的，如果对d 中每一对弧剐和y z ，茁z ，有 x z a ( d ) 定义1 1 0 有向图d 是竞赛图，如果对d 中每两个不同的点都有且只有一条弧 定义1 1 1 有向图d 中，如果对z ，y y ( d ) ，d + ( z ) 表示岱的出度，d 一( 可) 表示 v 的入度若对任意的。，y y ( d ) ，有i ( d ) = m a x t d + ( 。) 一d - ( g ) i = 0 ，则d 为正则 的 3 4竞赛图的传递性和半完全多部有向图的 王中王 定义1 1 2 有向图d = ( x ，y ) 是多部竞赛图，是指这样的个有向图d ，它以 v ( d ) = v 1 u k u u k 为顶点集，其中n 巧= d ( 0si j n ) ，对任意的 u k 及u k ，乱和 之间有且只有一条弧相连，而对任意的k ( 1 k n ) ，其内 部各定点之间没有弧相连当t t = 2 时，d 为二部竞赛图 定义1 1 3 称一个图为完全n 一部图，如果对不同部的任意两点之间都有边 定义1 _ 1 4 称一个图为半完全n 一部图，如果将完全n 一图的任意一边替换为一 条弧或一对来回弧时，称其为半完全扎部有向图，可以简单称其为半完全多部有向 图 定义1 1 5 如果一个半完全多部有向图没有来回弧时，称其为多部竞赛图 定义1 1 6 如果一个半完全多部有向图的每一部有且只有一个点时，称其为半完 全有向图 定义1 1 7 如果一个半完全有向图没有来回孤时称其为竞赛图 在本论文中，设t 是半完全多部有向图，v ( t ) 表示t 的顶点集，a ( t ) 表示 t 的弧集对任意的两点u ， v 口) ，若t 中存在一条从点札到点”的路则： 定义1 1 8 曲( u ，v ) 表示从u 到中长度最短的路的弧数相反的，我们定义 如( ，u ) = 0 3 表示t 中不存在u 路 定义1 1 9r 是一个正整数，若对每一个x y ( t ) ，都有出( ，z ) r ，则称w 为 t 中的r 一王若存在一点z ，使得d t ( ，o ) = r ，则称w 为真r 一王 定义l _ 2 0 用巧( r ) 表示t 中的r 王的集合辟( f ) 表示t 中r 一王的数， 即珥口) l = 辟( t ) 可知有坼一t ( t ) c o _ 珥( t ) ，同理蟛( t ) 表示t 的真r 一王 蟛( t ) = 珥( t ) 坼一( t ) 定义1 2 1 如果u v a ( t ) ，我们称“控制 ，用一v 来表示同理对t 中的 两个子集以，我们用u 一来表示对每一个u 以w6w ，都有一u 其 中( 矾w ) = u w a ( t ) ：u u 且w w ) 如果u = 扛 则u 一表示为 u 删相似的，如果w = f ，则u ，w 可用u 一w 来表示 t 中由u 诱导的子图表示为t 们 定义1 2 2 对 v ( t ) 有：o t ( v ) = v ( t ) i v 一叫) ，厅( u ) = v ( t ) 1 w u ) 其中1 0 r ( u ) l 为”的出度，1 b ( ”) l 为”的入度同样的可用s ( ”) 和s 一( 口) 分别表示t 中点 的出度和入度则若半完全佗一部有向图的n 一部表示 为m ，k ，可设n 磊= 口f s ( 口) 兰s ( 。) ，。k ) 定义1 2 3 珏为t 的发点，如果在t 中点u 的入度为0 在文f 6 1 中，m a u r e r 提出了竞赛图中王中王的概念，其定义如下： 定义1 2 4 设马是一个竞赛图，对f l ，设甄+ - = 皿 场( 皿) ，注意到恐( 踢) 尥( 玛) 2 扔( 凰) 2 ，因为尬( 既) 是一个有限集，则存在一个整数p ，使得对所 预备知识 有i 0 即对每一点都有出弧和入弧，设x y a ( d ) ，由d 为二部竞赛图，可设。x ，y y 由d + ( ) 0 ，故存在y z a ( d ) ，其中z x 由d 为传递图，从而x z a ( d ) ，与 d 是二部竞赛图矛盾 口 定理3 设d 为多部竞赛图，若d 是可传递的，则d 无圈 证明：设d 是n ( 3 ) 部竞赛图，其点集为：，k ，k 则任意的。e k ，y 巧其中i j 在z ，y 之间有弧相反的，若d 有圈g ，则圈c 上任意一点。在圈 c 上与它相邻的点不在同一部中，否则设x ye a ( g ) ，z x a ( d ) 且y ，z k 由传 递性知，存在z y a ) ，与d 为竹部竞赛图矛盾圈g 上任意两点均属于不同的 部k ，否则若圈g 上有两个在圈g 上不相邻的点。，t 在同一部中，则由传递性必有 弧耐或弧缸，与g 和t 在同一部中矛盾从而可知圈c 上的点在d 中的导出于图 为竞赛图，由定理1 知，传递的竞赛图无圈，矛盾故d 无圈 口 定理4 设d 为扩张竞赛图，则d 是可传递的当且仅当d 无圈 证明：必要性由定理3 知必要性显然 充要性：设d 为扩张的礼一部竞赛图，n 2 ，由扩张图的定义知d 中各部点等 8 竞赛图的传递性和半完全多部有向图的3 一王中王 价，即两部间弧的方向一致则只须考虑其基图h ，由扩张图的定义可知，日为有n 个点的竞赛图则对任意的仇，叶，v k y ( 日) ：i k ，若存在v i + ，码- 啦， 则由d 为扩张的多部竞赛图必有，讥或仇+ 姚，若v k ，v i 知有v l v j v k v 。 为日中的圈，即d 中有圈，与题设矛盾，故必有地。仇口 半完全多部有向图的3 一王中王 第三章半完全多部有向图的3 一王中王 b ，p ，t a n 证明了无发点的半完全多部有向图t 中，t 的2 一王中王和4 一王中 王集合非空，且证明了对无发点的半完全多部有向图t 不能定义1 一王中王的概念， 指出不是所有的3 一王中王集合非空，并指出了目前还没有找到无发点的半完全多部 有向图的k 3 ( t ) 1 的充分条件，进一步提出一个公开的问题，指出哪一类无发点的 半完全多部有向图的3 一王中王集合非空? 本文解决了如下的问题： ( 1 ) 给出了正则半完全多部有向图t 中使3 ( t ) l 的一些充分条件 ( 2 ) 给出一类无发点的半完全多部有向图满足3 一王中王集合非空 1 引理 引理2 1 h 设t 是无发点的半完全扎一部有向图，n 2 ，当i 凰( t ) nm l 1 i = 1 ，2 ，n ，则玛( t ) 2 引理2 2 1 4 1 设“和口是n 一部竞赛图相同部中两点，n 2 ，如果s ( u ) s ( ) ， 则或d ( u ，口) = 2 或o ( “) = 0 ( ”) 推论2 ，3 设“和 是无发点的半完全n 一部有向图t 相同部中两点，n 2 ，如 果s ( “) s ( u ) ，贝0 或d ( u ，v ) = 2 或o ( ) = o ( u ) 证明：如果t 是竞赛图，则由引理2 2 得证； 如果t 不是竞赛图，则存在一种删法使得一个扎一部竞赛图是t 的一个生 成子图且w 满足s ；( u ) s ( ”) 设是由t 删去2 圈中的一条弧得到的n 一部竞赛图，则由引理2 2 可知w 中有d w ( u ，w ) = 2 或o w ( u ) = 0 w ( 。) ；将删去的弧添上，因t ，则w 中， 若d w ( u ， ) = 2 ，则在t 中显然有d ( u ，口) = 2 ； 若o w ( u ) = 0 w ( u ) ，则在t 中有d ( “，u ) = 2 或0 ( ) = o ( v ) 口 引理2 4 设u 和u 是正则半完全礼一部有向图t 相同部中两点，? - t 3 ，且钆在 t 的一个3 圈中，则d ( u ，v ) 3 证明：设u 所在的一个3 圈为u w t u ，因s ( u ) s ( 口) ，则由推论2 3 知d ( 钆， ) = 2 或0 ( “) = o ( v ) 若0 ( “) 0 ( u ) ，则必有d ( u ，”) = 2 ； 若o ( “) = 0 ( u ) ，则有： 当t _ u ，由路u w t v 知d ( ， ) = 3 9 l o 童窒图塑谴塑壁塑堂塞全垒部有向图的3 一王中王 当u t ，由o ( 札) = 0 ( ) ，必有“一t 令u ，u 所在的部为，设= y ，则 可知d ( “) iki ，由t 为正则的半完全有向图，则有d ( “) = d ( v ) 1 l ，故必存在 点墨使得 一z 且。一u ，由o ( “) = o ( v ) ，知“一。，则有路u 。u ，即d ( “， ) ：2 ： 得证口 引理2 5 设t 是正则半完全n 一部有向图，扎2 ，设u 和 是不同部k 和k 中的两点，i j ，设w 巧扣) ，如果有弧钍一 ，则d ( “， ) 3 证明：由题设知u 删同部，且s ( 口) = s ) ，则由推论2 ，3 知，d ( ，w ) = 2 或 o ( v ) = 0 ( ) ， 若d 扣， ) = 2 ，则由“， 知d ( ，w ) d ( u ， ) + d ( v ，w ) = l + 2 = 3 若o ( v ) = 0 ) 且珏一”，若札一训，则有d ( u ，叫) = 1 s ( 戤) 因为对每一个墨，有s ( x 1 ) = s ) ，则必存在一点叫y ( t ) k ，使得翰，w 且 骱可设i = 1 ，若。14 2 则有路x 3 x 1 y 2 与d ( z 3 ，y 2 ) 4 矛盾若x 11 船则 与d ( z l ，y 3 ) 4 矛盾故存在一点w 不属于矿( 日) ，使得x l w 且w y 1 ，同理可 证i = 2 ，3 现在我们考虑点x 3 ，则存在一点 y ( t ) k ，使得x 3 - - - - - 4w 且叫- - - + y 3 ，由引 理2 8 ( i i ) 和x l 隹玛( t ) 且乱= y 3 ，必有w 注意到： ( i ) 叫一茁l ，否则x t w y 3 是从x l 到舶的长为2 的路，与d ( x 1 ，y 3 ) 4 矛盾 ( i i ) y lhw ，否则x 2 x 3 w y l 是从x 2 到y l 的长为3 的路，与d ( x 2 ，y 1 ) 4 矛盾 因此我们得知存在： ( a ) v 2 中的一点w ，使得s ( x 3 ) 在t 中增加l ，但s ( 口3 ) 不增加1 同时在t 中， 使得s ( 玑) 增加1 且s ( z 1 ) 不增加1 同理有： ( b ) 中的一点，使得s ( x 2 ) 在t 中增加1 ，但s ( y 2 ) 不增加1 同时在t 中，使 得s ( y 3 ) 增加1 且s ( z 3 ) 不增加1 ( c ) 中的一点，使得s ( x 1 ) 在t 中增加1 ，但s ( 1 ) 不增加1 同时在t 中，使 得s ( y 2 ) 增加1 且s ( 。) 不增加1 由上述( 口) ( 6 ) ( c ) 与t 为正则半完全有向图矛盾故得证 口 推论3 设t 是正则半完全3 部有向图，如果对每一个i = 1 ，2 ，3 ，存在k ，使 得虢在t 中的一个3 圈中，则 。l ，。2 ，z 3 ) n 耳3 ( t ) 0 即3 口) 1 1 3 1 4 竞赛图的传递性和半完全多部有向图的3 一王中王 证明：如果 包含一个3 圈，则由定理2 得证， 如果 不包含在一个3 圈，则可假设z l 一( 。2 ，。3 ) 或z 1 z 2 ，x 3 且z 3 z 1 ，由推论2 5 ，可知z 1 k 3 ( t ) ，得证 口 定理4 ：设t 是一个正则半完全n 一部有向图，礼4 ，如果对某个乜，q ，r ) c ( 1 ，2 ，n ) ，使得：c p x 口嘶卸形成一个3 圈其中x p k ，k ，x ，w ，且对每一 个j 1 ，2 ，礼) 妇，q ，r ) ，存在码使得 ，珥) 一，则 ，嘞，x , r n 玛( t ) 口，则k 3 ( t ) 1 证明：我们可假设p = l ，q = 2 且r = 3 ，则由题设可对圈中双向弧的情形分情况 讨论： 情况l ： 若x l x 2 ，z l 3 ，x 2 2 3 中至少有一条弧属于a ( t ) ，则存在她k a ( t ) 不妨设z 1 勋 a ( t ) ，如图1 ， 由。l z 2 和z 1 + 。3 ， 对任意的y k z z ) ，由t 为正则的半完全佗一部有向图且s ( 。) = s ( g ) ，则由 引理2 5 得知，有d ( z l ，y ) 3 对任意的y z 3 ) ，由s ( ：c 3 ) = s ( g ) ，有d ( x 1 ，y ) s3 ， 对任意的y k 茁，) ，由s - ) = s 0 ) ，且。在t 中的一个3 圈中，则由引理 2 4 得知，d ( x l ，y ) 3 且由题设对j 1 ，2 ，n ) 1 ，2 ，3 ) ，存在x j 巧，使得( z 1 ，x 2 ，z 3 ) 一由题 设对每一个j 1 ，2 ，n ) ，知对任意的y 巧，有s ( x j ) = s ( y ) 则由引理2 5 可 知，对任意y 巧，j 1 ，2 ，3 ，都有d ( x 1 ，y ) s3 ，由上得知。1 t ( 3 ( t ) 同理可证有弧x 3 x 2 时。3 肠( 丁) 和弧她z l 时z 2 岛( 丁) 情况2 ： 若弧x l x 2 ，x l x 3 ，x 2 x 3 都不属于a ( t ) ，反证之设对每一个i = l ，2 ，3 ，都有 观隹玛( t ) 考虑q ，由z 1 隹玛口) ，对任意一个巧j 1 ，2 ，3 ，由题设对j 1 ，2 ，n t 1 ，2 ，3 ) ，存在，使得 z 1 ，z 2 ，x 3 ) 一则由引理2 5 ，对任意 y 巧，都有d ( x l ，y ) 3 ；对任意y h ，由s ( 。1 ) = s ( ) ，且茁l 在一个3 圈中， 由引理2 4 得知，d ( z t ，y ) s3 ；对任意k ，由s ( x 2 ) = s ( y ) ，且由引理2 5 得 知，d ( x l ，可) 3 ；由z l k 3 ( t ) ，故必有y 3 ，使得d ( z 1 ，y 3 ) 4 在t 中有 d ( z l ，y 3 ) 4 ，同理可证d ( z 2 ，1 ) 4 ，d ( x 3 ，y 2 ) 4 ，且t 包含图f 2 作为其子图设其 为爿，则在口中对每一个i = 1 ，2 ，3 ，有s ( ) = s ( 肌) 因为对每一个s ( 甄) = s ( t ) ，姗对每一个点执，必存在一点”y ( t ) 磁，使得 z 。一7 1 1 且一玑同理由引理28 ( “) 的证明可知不存在任何点 m ，使得茁3 一 ，且u 一驰相似的，不存在任何点v 使得。2 一u ，且u 一2 和不存在任何 半完全多部有向图的3 一王中王 点u k 使得0 1 一o ，且u1 札 考虑点功，对j = 2 ，4 ，5 ，n ，设w 是中的点，使得x 3 7 1 ) ，且叫一3 注 意到： ( o ) w x l ；否则x l w y 3 是一条从z 1 到蜘的长为2 的路，与d ( x l ，y 3 ) 4 矛盾 ( b ) y 1 一训；否则x 2 2 5 3 w y l 是一条从z 2 到y 1 的长为3 路，与d ( z 2 ，1 ) 4 矛盾 且对j 4 ， ( c ) 叫一x 2 ；否则z l x 2 w y 3 是一条从。l 到9 3 的长为3 路，与d ( x l ，y 3 ) 4 矛 盾且 ( d ) y 2 一叫；否则3 ：3 叫是一条从x 3 到2 的长为2 路，与d ( x 3 ，y 2 ) 芝4 矛盾 因此我们有： ( i ) 对j = 2 ，4 ，5 ，n ，存在巧中的一点w ，使得t 中的点x 3 的出度增加1 ，但 3 的出度没有增加1 ，同样的t 中，2 ( 如果j 2 ) 和1 的出度增加1 ，但z 2 和。1 的出度没有增加 同样的我们有 ( i i ) 对j = 1 ，4 ，5 ，n ，存在k 中的一点，使得t 中的点x 2 的出度增加1 ，但y 2 的出度没有增加1 ，同样的t 中，y - ( 如果j 1 ) 和弘的出度增加1 ，但z 1 和。3 的 出度没有增加 ( 涮) 对j = 3 ，4 ，5 ，n ，存在中的一点，使得t 中的点嚣，的出度增加1 ，但 y t 的度没有增加1 ，同样的t 中，y 3 ( 如果j 2 ) 和她的出度增加1 ，但x 3 和x 2 的 度数没有增加 这些结果与t 为正则得半完全n 一部有向图矛盾，证明完毕 口 推论5 ：设t 是无正则半完全几一部有向图，仃4 ，如果对每一个i = 1 ，2 ，n ， 存在x i k ，使得对一些 p 1q ，r ) c 1 ，2 ，n ，存在唧，研在一个3 圈中；且对 每一个j 1 ，2 ，n ) 切，q ，r ) ，有 ，斟) ，。j ，则 唧，研) n j 岛( t ) d ， 因此有b ( t ) 1 证明：如果 包含个3 圈，设其为唧x ，x p ，则由定理3 得证 若唧， ，研) ，则由推论2 5 可知唧e 3 ( t ) 得证口 3 ( 2 ) 的主要定理的证明 定理6 ：设t 是无发点的半完全2 一部有向图，若对任意的点w k ( f = 1 ，2 ) ，都 有对每一点z k 叫) ，满足d ( 伽，z ) = 2 ，则t 中的3 一王中王集合非空 1 6 ： 童童里竺! 堑墼垡垫堂塞全垒墅童鱼里墅! 三三童垂 证明：令乃= t ，由题没中对任意一点 k 0 = 1 ，2 ) ，都有对每一点z m 甜) ，满足d ( 叫，。) = 2 ，则由定理1 知每一点”k ，w 均为3 王，故有： k 3 ( n ) = k 3 ( 疋) 一 则对任意p ，均有五毛( 乃) d 由3 一王中王的定义知丑中的3 王中王集合为 y ( 丑) 得证口 由定理1 和定理6 有如下推论： 推论7 ：若正是无发点的半完全2 一部有向图，若存在p ，使得； 当i p 时，有凰( 正+ 1 ) 玛( 正) 当i p 时，有玛( 丑+ ) = k a ( t d ，且玛) 口则t 必须包含有满足定理6 的条件的图作为t 的子图 定理8 ：若丑是无发点的半完全2 一部有向图，若 ( 口) k l = 2 ( 6 ) 丑中存在一个4 圈，且圈中至少存在一点z ，使得对所有y m z ) ，有 d ( z ，y ) = 2 则乃中3 王中王集合非空 证明；设这个4 圈为现x 2 x s x 4 x l ，不妨设。1 ，则易知 。2 ，z 4 ) u ，且 ki = 2 ，故= 。2 ，。4 ，由。2 。3 。4 和a ：4 2 1 。2 分别是长为2 的z 2 拍路和。4 2 2 路，则有屯( 勉，锄) = 2 ，d n ( 。4 ，。z ) = 2 ，由定理1 可知z 2 ，锄玛( 噩) 若圈中至 少存在一点z ，使得对所有y d ，有d ( 。，y ) = 2 不妨设。对所有的 y h 研) ，有d ( x 1 ，y ) = 2 ： ( n ) 若。2z - ，且无其他任意一点，使得对任意g ，有d ( ，z ) ：2 ，则由 定理1 ，知( 五) = 。2 ，z a ，。z ) ， 。4 ) ，故当i 3 时，有玛呱十，) = 若有x 2 一g j l ，z ，一x 4 ，则蚝( 马) = x n = 娲( 码) ， 若有2 9 2 _ z 1 ，2 3 1 _ x 4 ，则k a ( t 2 ) = z 1 ，z 2 ，z 4 ) = 凰( 码) ， 若有2 9 2 * 。l ，z l - - - - - + 。4 ，则k 3 ( 马) = z 1 ，。4 ) = 蚝( 码) 都有当i 2 时，凰( 噩+ ，) = j 岛慨) 则由3 一王中王的定义知丑的3 一王中王 集合非空 ( 6 ) 若存在其他点 ，使得对任意的z h ，有d ( 口，z ) = 2 设这些点集为u ， 若缸矿，则显然乃= 噩渺u 缸2 ，。4 h 且玛( 正) = 玛，故当i 2 时， 玛( 五十1 ) = 凰) 由3 一王中王的定义知丑的3 一王中王非空，得证 若勋茌u ，有如下情况： 情况1 ：若存在1 u ，使得 包含个4 圈，由上同理得知， 正的3 一王中王非空 马 ，l 知此由 卅。嚣 书 现若 故劭“ k 半完全多部有向图的3 一王中王 情况2 ：若对任意的u 1 u ， 都不包含一个4 圈则有： 情况2 1 ， u