（应用数学专业论文）有向图中若干问题的研究.pdf

摘要 摘要 本篇论文主要研究有向图中的有向圈，讨论有向图中的围长g ( d ) ( 最短有 向圈的长度) 与图的顶点度以及结合数之间的关系，并重点分析了点可迁图类 论文源自于有向图中两个具有一定相关性的猜想： c a c c e t t a - h i i g g k v i s t 猜想若有向图d 满足矿( d ) d ，那么g ( d ) 吲。 s e y m o u r 二出度猜想任一有向图d 中都存在顶点v v ( d ) ，使得 l n + + ( ”) i i n + ( u ) 。 在论文的第一章，我们介绍了论文中涉及的一些基本的图论概念和术语，本 论文的研究内容以及论文中所得到的主要结果。 第二章综述了上述两个猜想的研究进展重点介绍了c a c c e t t a - h i g g k v i s t 猜 想的特殊情形：d2 ；，给出了与c a c c e t t a - h i g g k v i s t 猜想或其特殊情形等价 的相关猜想。证明了s e y m o u r 二出度猜想成立等价于该猜想在强连通有向图上 成立 第三章讨论理论和应用上都非常重要的特殊图类一一可迁图我们将许多无 向点可迁图的结果平行地推广到有向点可迁图中，同时得到了一些不同与无向图 情形的结论。证明了c a c c e t t a - h i _ g g k v i s t 猜想和s e y m o u r 二出度猜想均在可迁 图上成立重点讨论了点可迁图的连通性及连通度，提出了原子匹配、原子收缩 图、原子稳定子群等一些新的概念，在此基础上进一步分析了点可迁图的结构特 征，完善了现有的点可迁图的连通性理论特别地，给出了c a y l e y 图连通度的 精确表达式，推广并改进了d o o r n 和孟吉祥的结果，并在最后分析了一些达到 最优连通度的c a y e l y 图类 第四章将有向图的度条件( 顶点的邻域) 与围长的关系进行了推广，考虑结 合数( 点集合的邻域条件) 与围长的关系由于若无向图g 的结合数b ( g ) 2 ， 则g 中存在三角形，而c a c c e t t a - h j i g g k v i s t 猜想研究有向图中存在有向三角形 的条件，受此启发，我们在有点向图中引入结合数的概念在此基础上，论文讨 论了有向图结合数的性质，得到了结合数的范围并论证了给定结合数的有向图的 i 摘要 存在性，提出了关于结合数与围长之间联系的两个猜想。同时，还给出了几类特 殊有向图的结合数，并分析了结合数与有向图连通性及连通度之间的关系 最后，我们对本论文的结果加以总结，归纳了文章中提出的或遗留的问题， 给出了论文中提到的有向图中尚未解决的猜想之间的相互关系，并对进一步的研 究给予展望 关键词：c a c c e t t a - h i i g g k v i s t 猜想，s e y m o u r 二出度猜想，围长，顶点度， 哉可迁图，原子，原子匹配，原子收缩图，结合数 a b s t r a c t a b s t r a c t t h i st h e s i sc o n t r i b u t e st od i r e c t e dc y c l e si nd i g r a p h s ，i n c l u d i n gt h er e l a t i o n s b e t w e e nt h eg i r t hg ( d ) ( 1 e n g t ho ft h es h o r t e s td i r e c t e dc y c l e ) o fda n dd e g r e e s o fv e r t i c e so fda n db e t w e e nt h es h o r t e s td i r e c t e dc y c l eo fda n dt h eb i n d i n g n u m b e ro fd ，a m o n gw h i c hv e r t e x t r a n s i t i v ed i g r a p h sa r es t u d i e di nd e t a i l t h i s t h e s i si sm o t i v a t e db yt h ef o l l o w i n gt w or e l a t e dc o n j e c t u r e so nd i g r a p h s c a c c e t t a - h i i g g k v i s tc o j e c t u r e l e tdb ead i g r a p hw i t hd + f d ) 2d t h e ng ( d ) 哪 s e y m o u r ss e c o n do u t d e g r e ec o n j e c t u r e na n ys i m p l ed i g r a p hd ， t h e r ei sa tl e a s to ? z ev e r t e xv v ( d ) s u c ht h a tl n + + ( 口) l2 l n + ( ” i nc h a p t e r1 ，t h et e r m i n o l o g ya n dn o t a t i o n s0 1 2g r a p h t h e o r y a r ei n t r o d u c e d ， a n dt h e nab r i e fi n t r o d u c t i o nt ot h es t u d yc o n t e n t sa n dm a i nr e s u l t so b t a i n e di n t h i st h e s i si sg i v e n i nc h a p t e r2 ，as u m m a r yo nt h ed e v e l o p m e n to ft h ea b o v et w o c o n j e c t u r e si s g i v e n ，i nw h i c ht h es p e c i a lc a s eo fc a c c e t t a - h g g g k v i s tc o n j e c t u r e ，i e ，d ，i s d e s c r i b e dp a r t i c u l a r l y a n ds o m ec o n j e c t u r e st h a ta r ee q u i v a l e n tt ot h ec a c c e t t a - h g g g k v i s tc o n j e c t u r ea n di t ss p e c i mc a s ea r eg i v e n i ti sp r o v e dt h a ts e y m o u r s s e c o n do u t d e g r e ec o n j e c t u r eh o l d si fa n do n l yi fi th o l d sf o rs t r o n gc o n n e c t e d d i g r a p h s i nc h a p t e r3 ，v e r t e x t r a n s i t i v ed i g r a p h sa r es t u d i e d ，w h i c ha r ev e r yi m p o r - t a n ti nb o t ht h e o r ya n da p p l i c a t i o n m a n yr e s u l t so nu n d i r e c t e dv e r t e x - t r a n s i t i v e g r a p h sa r ea p p l i e do nd i r e c t e dc a s e si np a r a l l e l a n ds o m ed i f f e r e n tc o n c l u s i o n s f r o mu n d i r e c t e dc a s ea r eo b t a i n e d i ti sp r o v e dt h a tt h ea b o v et w oc o n j e c t u r e s h o l df o rv e r t e x - d i g r a p h s c o n n e c t i v i t yi sd i s c u s s e dp a r t i c u l a r l y , a n ds o m ed e w c o n c e p t i o n sa r ep r o p o s e d ，s u c h a sa t o m m a t c h i n g ，a t o m c o n t r a c t e dd i g r a p ha n d a t o ms t a b i l i z e rs u b g r o u p ，b a s e do nw h i c ht h es t r u c t u r ec h a r a c t e r i s t i co fv e r t e x t r g n s i t i v ed i g r a p h s i sa n a l y z e df u r t h e r ，a n dc u r r e n tc o n n e c t i v i t yt h e o r yo nv e r t e x - i i i a b s t r a c t t r a n s i t i v ed i g r a p h si sc o n s u m m a t e d p a r t i c u l a r l y , e x p l i c i te x p r e s s i o nf o rc o n n e c t i v i t yo fc a y l e yd i g r a p h si sg i v e n ，d o o ma n dm e n g sr e s u l t sa r ea l s og e n e r a l i z e d a n di m p r o v e d a tl a s t ，c a y l e yd i g r a p h sw i t ho p t i m a lc o n n e c t i v i t ya r ea n a l y z e d i nc h a p t e r4 ，t h ec o n c e p t i o no fb i n d i n gn u m b e ro fu n d i r e c t e dg r a p h si si n - t r o d u c e dt od i g r a p h s ，b a s e do nw h i c ht h er e l a t i o n s h i pb e t w e e nd e g r e ec o n d i t i o n o fv e r t i c e sa n dg i r t hi sg e n e r a l i z e dt ot h er e l a t i o n s h i pb e t w e e nn e i g h b o r h o o dc o n - d i t i o no fv e r t i c e ss e t sa n dg i r t h t h ep r o p e r t i e so fb i n d i n gn u m b e ra r ed i s c u s s e d ， t h ev a l u e s c o p e o f b i n d i n g n u m b e ri so b t a i n e d ，a n dt h ee x i s t e n c eo f d i g r a p h s w i t h ag i v e nb i n d i n gn u m b e ri sp r o v e d t w oc o n j e c t u r e so nt h er e l a t i o n s h i pb e t w e e n b i n d i n gn u m b e ra n dg i r t ha r ep r o p o s e d a l s o ，t h eb i n d i n gn u m b e r s o fs o m es p e a i md i g r a p h sa r ec o m p u t e da n dt h er e l a t i o n s h i pb e t w e e nb i n d i n gn u m b e ra n d c o n n e c t i v i t yi sa n a l y z e d a tt h ee n do ft h et h e s i s ，w eg i v ea no v e r v i e wo ft h ew h o l ec o n t e n t so ft h e t h e s i sa n da l s op r o p o s es o m ep r o b l e m sf o rf u r t h e rr e s e a r c h k e y w o r d s ：c a c c e t t a - h i i g g k v i s tc o n j e c t u r e ，s e y m o u r s t w oo u t d e g r e e c o n j e c t u r e ，g i r t h ，d e g r e e ，v e r t e x t r a n s i t i v ed i g r a p h ，a t o m ，a t o mm a t c h i n g ，a t o m c o n t r a c t e dd i g r a p h ，b i n d i n gn u m b e r i v 第一章绪论 第一章绪论 1 1 引言 图论的历史可以追溯到1 7 3 6 年瑞士数学家e u l e r 解决k b n i g s b e r g 七桥问 题。但在随后的两百年里，图论的发展非常缓慢这一时期，图论的研究主要 集中在两个方面：一是如四色问题和h a m i l t o n 问题等一些图论难题；二是以 图为工具去解决其它领域的问题，其中最具代表性的成果是k i r c h h o f f ( 1 8 4 7 年) 和c a y l e y ( 1 8 5 7 年) 分别用树的概念去研究电网络方程组和有机化合物的分子结 构进入二十世纪三十年代，出现了许多漂亮的图论新理论和结果，如m e n g e r 定理( 1 9 2 7 年) ，k u r a t o w s k i 定理( 1 9 3 0 年) 和r a m s e y 定理( 1 9 3 0 年) 等这 些理论和结果为图论的发展奠定了基础。1 9 3 6 年，匈牙利数学家k b n i g 出版了 第一本图论专著有限图和无限图理论，标志着图论作为一个新的数学分支已 经基本形成 图论作为一个新兴的数学分支，近几十年发展十分迅速它广泛用于运筹 学、计算机与信息科学、网络理论、生物化学、经济管理及社会科学等多个领 域；同时，图论与数学的其它分支，如群论、矩阵理论、概率论、数值分析等都有 着密切联系图论为任何包含二元关系的系统提供了一个数学模型，它使用图解 式的方法，具有一种直观的、符合美学的外形因而受到数学界和工程技术界， 乃至经营决策管理者的极度重视，形成了图论学科迅猛发展的局面 图的结构性质作为图论研究的一个主要内容，具有重要的理论及应用价值 如：大规模集成电路( l s i ) 的分析与设计，印刷电路板的设计与布线，传递网络 和通讯网络稳定性与可靠性研究等，就是利用图的结构性质指导实际工程技术 在图论研究中，图中的圈结构是图的结构特征的一个重要部分。例如图的 h m a i l t o n 圈，e u l e r 迹；图的最长圈、最短圈和泛圈性，有向图中的有向圈、无 圈定向等研究内容；以及图中的圈与图的其它参数( 连通度、直径、顶点度、离 散度、结合数等) 之间的关系一直是图论中的热门主题在这些方面，有向图的 研究显得更为复杂，得到的结果和无向图相比，也要明显薄弱 通讯和计算机互联网络常常用无向图g 或有向图d 来模拟连通度是该网 络可靠性的一个重要度量一般说来，连通度越高，网络越可靠，但不能无限制 1 第一章绪论 地增加通讯路线，这样会增加费用，因而部件标准化，也是通讯和计算机互联网 络设计是所要考虑的重要因素可迁图本身的高度对称性正迎合了这种实际需 求，因而其理论研究具有重要价值。 本篇论文主要研究有向图中的有向圈，讨论有向图中的最短有向圈与图的顶 点度( 点邻域) 以及结合数( 点集合邻域) 之间的关系，并且对点可迁图类作了 重点分析。 1 2 问题的引入 引入研究内容之前，给出本文常用的一些基本术语和记号论文中未加说明 的术语和记号参见 8 8 。为了便于阅读，以后各章节中我们还将陆续给出一些涉 及的概念和术语。 设d ( y ( d ) ，a ( d ) ) 是有向图，其中v ( d ) 是顶点集，a ( d ) 是边( 弧) 集。 对于v v ( n ) ， + ( u ) = 珏v ( d ) l u u a ( d ) ) ；n 一扣) = 乜v ( d ) i u v a ( d ) ) 分别称为顶点v 的出邻域和入邻域； 的出度d + ( ) = n + ( ) i ，入度d 一( u ) = l 一( u ) l ，弱度d ( v ) = m i n d + ( v ) ，d - ( ) ， 对于v ( d ) 的非空子集s ，t v ( d ) ，( s ，t ) 表示弧集 ( u ， ) l u s ， ”。 r + ( s ) = u 十( 甜) ，f - ( s ) = u n 一( 封) ； y e s y e s + ( s ) = r + ( s ) s ，n 一( s ) = f 一( s ) s 分别称为s 的出邻域和入邻域；外出邻域和外入邻域r ( s ) 为 r + ( s ) ，1 1 一( s ) ) 中势较小者，称为s 的弱邻域；( s ) 为 + ( s ) ，一( s ) ) 中势较小者，称为s 的外弱邻域我们定义顶点口的七一阶外出邻域如下： w ( ) = r + ( 椎- 1 ) ( ”) ) 噍_ 1 ) ( ) 顶点”的2 一阶外出邻域j 7 、磅( ”) ，我们一般记成n + + ( ) 2 5 1 2 问题的引入 论文中用+ ( d ) ，一( _ d ) ，6 + ( d ) ，5 - ( d ) 分别表示d 的顶点最大和最小 出、入度，即： 十( d ) = m a x d + ( 廿) ，掣y ( d ) ) ；一( d ) = m a x 2 8 5 d + 1 5 2 由上式可知当d 茎1 0 时，礼= 3 d + 1 结论9 f 3 3 】若d 为d 一正则有向图，g ( d ) 24 且如曼6 ，那么凡3 d + 1 。 2 、关于s e y m o u r 二出度猜想的主要结论 f i s h e r 在【16 】中证明了s e y m o u r 猜想在竞赛图上成立随后，h a v e t 和 t h o m a s s 6 【2 9 】给出了更为简短的证明，而且他们得到了下述结果： 结论1 0 ( h a v e t 和t h o m a s s 6 【2 9 ) 如果竞赛图d 中不合有控制顶最u v ( d ) r 出 度d + ( ) = 0 ，那么d 中至少存在两个顶点饥，满足s e y m o u r 二出度猜想 结论1 1 ( k a n e k o 和l o c k e 3 2 ) 如果有向图d 满足6s 6 ，那么d 中存在顶 点v 使得d + + ( ) d + ( ) 结论1 2 ( a n d e r s o n 等【1 】) s e y m o u r 二出度猜想在下列有向图中成立： j 无圈有向图 2 一出正则有向图，4 3 笛卡尔乘积图d h ，其中有向图d 和日满足猜想 4 特殊的有向c a y l e y 图 5 出正则二部有向图 6 1 3 本文的主要研究工作和研究成果 6 针轮图p w g 其中情形2 ( k = 1 ，2 ) ，4 6 ，的有向图中每个顶点均满足d + + ) d + 扣) 。 我们得到了关于s e y m o u r 二出度猜想的下述结论。 结论1 3 如果s e y m o u r 二出度猜想对于任意强连通有向图成立，那么猜想对于 任意有向图d 都成立 第三章讨论理论和应用上都非常重要的特殊图类一一可迁图。我们证明了 c a c c e t t a - h i g g k v i s t 猜想和s e y m o u r 二出度猜想均在可迁图上成立重点讨论了 点可迁图的连通性及连通度，提出了一些新的概念，完善了现有的点可迁图的连 通性理论特别地，给出了c a y l e y 图连通度的精确表达式，推广并改进了d o o r n 和孟吉祥的结果，并在本章的最后分析了一些达到最优连通度的c a y e l y 图类 论文将许多无向点可迁图的结果平行地推广到有向点可迁图中，同时得到了 一些不同与无向图情形的结论，主要有： 结论1 4 j 任一点可迁有向圉都是不交的同构强连通点可迁有向图的并； 2 有向点可迁图必是正则的 结论1 5 设d 是边可迁圈且6 ( d ) 0 ，则d 是点可迁困。 结论1 6 如果d 是p 阶点可迁图，p 为素数，则d 是循环图 结论1 7 令r 是点可迁图d 的自同构群，h = f 。是顶点z v ( d ) 的稳定 子群，则d 皇d ( f h ，j s ) ，其中d ( f h ，s ) 表示r 关于子群h 的左陪集图， s = 盯r ( z ，口( z ) ) a ( d ) ) 关于点可迁的原子与其性质，以及由此得到的点可迁图的结构特征，主要包 括下面几个结论： 结论1 8 如果a ，a ，是c a y l e y 图的两个相邻原子，即存在。a i ，! ，山使 得( 。，y ) a ( d ) ( 或( y ，z ) a ( d ) ) ，那么a j n + ( a ) ，a n 一( a j ) ( 或 a + ( ) ，a j n 一( a t ) ) ，且a 与如之间存在出( 或入) 弧匹配即任意 c a y l e y 图都是原子匹配图 结论1 9 。任意。占、可迁圜的原于为中于。 结论2 0 若d 是点可迁有向图，则d 是原子匹配图如果d 的原子a 是正 的，则n + ( a ) 是不交原子的并集 结论2 1 如果d 是点可迁的， w 是最小的顶点割，那么w 是不交的原子的 7 第一章绪论 并集，因而d 至少包含3 个不同的原子。 结论2 2 对点可迁图d 的原子的稳定子群如，下述四个条件等价： 上“是a u t ( d ) 的正规子群； 2 对任意的y v ( d ) ，y 关于子群巩的轨道是原子； ，b 是d 的原子，则h a = h b ； 4 对任意的 + v ( d + ) ，其中d + 为原子收缩图，有稳定子群g r = f l ，即 a u t ( d + ) 是正则的 结论2 3 如果点可迁图d 的原子稳定子群h 是正规的。那么原子收缩图d 4 是c a y l e y 图 我们定义了点可迁图的原子收缩图，给出了它的有关性质，得到了点可迁图 的归纳特征，并且由此证明了c a c c e t t a - h i i g g k v i s t 猜想和s e y m o u r 二出度猜想 在可迁图上成立 结论2 4 若d + 是强连通点可迁图d 的原子收缩图，则d + 是最可迁的 结论2 5 若日是阿贝尔群，d 是强连通c a y l e y 图d s ( h 1 的原子收缩图，则 d + 是阿贝尔群上的c a y l e y 图 结论2 6 若d 为点可迁图且6 ( d ) = d ，则围长g ( d ) 曼i r l l ，而且任一顶点 u v ( d ) 都包含于圈长为围长的有向圈 结论2 7 如果d 是点可迁图，那么对任意u v ( d ) 有l + + ( ) i l n + ( u ) 1 对c a y l e y 图及一般点可迁图的连通度，论文主要得到下面结果： 结论2 8 c a y l e y 图d s ( h ) 的连通度圪( d ) 可由下式给出： 尤( d ) 。r m 珧i n 6 ( d ) ；i r l i r s l 结论2 9 设a 是强连通点可迁有向图d 的原子，那么k ( a ) = 扩i a i ，其中 扩= 6 ( d + ) ，d + 是d 的原子收缩图 第四章将有向图的度条件( 顶点的邻域) 与围长的关系进行了推广，考虑点 集合的邻域条件与围长的关系，将结合数的概念引入到有向图中，讨论了有向图 结合数的性质，提出了关于结合数与围长之间联系的两个猜想同时，还给出了 几类特殊有向图的结合数，并分析了结合数与有向图连通性及连通度之间的关 系。 8 1 3 本文的主要研究工作和研究成果 引入结合数的概念到有向图同时，我们给出了结合数的一个等价定义，得到 了任意有向图d 的结合数b ( d ) 的范围，并且构造出了任意给定结合数的有向 图，论证了其存在性 结论3 0 ( 等价定义) 6 ( d ) _ 。鼢d ) 啪冬器黔) 结论3 1 有向图d 的结合数b ( d ) 为0 b ( d ) 2 之间的有理数 结论3 2 对于任意有理数0s ：1 ( 其中p ，g 为正整数) ，存在有向图d ，使 得b ( d ) = ! 。 结论3 3 对于任意有理数1s ： 2 ( 其中p ，q 为正整数) ，存在有向循环图 d = c s ( n ) ，使得b ( d ) = ：。 关于有向图的结合数与连通性和连通度的关系，我们得到了下述结果： 结论3 4 如果d 非强连通，则b ( d ) s1 ；反之不真，即存在b ( d ) 图2 1 ( 6 ) s = 1 ，2 ) 不难确定有向( d ，9 ) 一笼的顶点数n 的一个界，不同的是我们得到的是一个 上界： n 9 ( d 一1 ) 十1 b e h z a d 等在1 9 7 0 年文献中【2 猜想上式等号成立下面我们给出这个猜 想： 猜想5 2 若d 是d - 正则有向图，那么g ( d ) 告1 1 9 7 8 年，c a c c e t t a - h 盏g g k v i s t 【1 0 提出了更一般化的猜想，将条件弱为每一 顶点的出度不小于d 即是c a c c e t t a - h 苴g g k v i s t 猜想并证明了当d = 2 时，猜 1 1 第二章有向图中的两个重要猜想 想成立。 猜想1 若有向图d 满足d + ( d ) d ，那么g ( d ) 茎； 。 实际研究中，很多学者考虑5 ( d ) d 条件下的情况，变为猜想3 。 猜想3 若有向图d 满足d ( d ) 芝d ，那么g ( d ) ；1 。 事实上，如果有向图d 的每一顶点出度都不小于d ，则d 存在一个任意顶 点的出度都为d 的生成子图( s p a n n i n gs u b g r a p h ) ，所以c a c c e t t a - h i i g g k v i s t 猜 想中出度不小于d 的条件可以等价为任一顶点出度都等于d 。 猜想6 若d 是d 一出正则有向图，那么g ( d ) 3 1 c a c c e t t a - h i g g k v i s t 猜想提出之后，引起了图论学者的广泛兴趣d 5 的情 形已经分别在 1 0 ， 2 6 1 ， 3 0 中给出了证明对于任意的d ，c h v d t a l 和s z e m e r 6 d i 在【1 3 得到了围长g ( d ) 的一个上界 定理2 1 1 【1 3 1 若有向图d 满足6 + ( d ) d ，那么g ( d ) s 0 + 2 5 0 0 。 n i s h i m u r a 在【3 6 中将常数从2 5 0 0 降低到3 0 4 2 0 0 2 年s h e n 4 1 进一步 将常数降为7 3 ，而且得到了下面定理 定理2 1 2 4 1 】若有向图d 满足矿( d ) d ，那么 卯) 3 f ( i n 掣) 1 9 8 1 年，h a m i d o u n e 在【2 3 】中证明了猜想5 在点可迁图( 定义见3 1 节) 上成立但其证明过程尚有待推敲 定理2 1 3 【2 3 若d 为点可迁图且5 ( d ) = d ，那么g ( d ) 曼3 此外，s h e n 在阻0 1 中得到了以下结果： 定理2 1 4 4 0 若有向图d 满足矿( d ) d ，那么g ( d ) 兰m a x 吕 ，2 d 一2 ) 。 故对任意的d ，当佗2 d 2 3 d + l 时，c a c c e t t a h i i g g k v i s t 猜想成立 c a c c e t t a - h i i g g k v i s t 猜想及相关猜想主要讨论有向图的顶点阶数、顶点度与 最短有向圈的长度等结构参数之间的关系关于图中的有向圈结构，图论学者已 经取得了许多成果，也有很多尚未解决的问题，下面我们介绍其中两个猜想； 猜想7 ( c t h o a n g 和b r e e d 3 0 ) 若d 满足矿( d ) d ，则d 中合有有向 圈g ，i = l ，2 ，d ，使得 j l i c jnu c ：ls1 ，1 j d 】2 5 2 1c a c c e t t a - h i g g k v i s t 猜想 猜想8 ( s e y m o u r ，1 9 9 5 ) 任意有向图d 含有一个分离顶点”满足：d 中存在 d = d + ( ) 个有向圈d ，i = 1 ，2 ，d ，使得 区n 岛= u ) ，1 i 0 3 4 7 7 n ，那么d 中包含 李学良教授的学生李朝霞在硕士论文【5 0 】中利用b o n d y 提出的数子图的方 法将定理2 1 6 中的矿( d ) 降到o 3 4 0 9 6 n b r o e r s m a 和l i 在 9 】中考虑猜想4 的反例所具有的结构性质 定理2 1 8 9 】若有向图d 满足5 ( d ) ；且不合a ，那么下列结论成立： d 中的任一顶点包含在有向4 一圈中 2 d i a m ( d ) 4 3 + ( d ) ，一( d ) 2 8 5 d + 1 5 2 由上式可知当d 1 0 时，n = 3 d + 1 q l i 和b r u a l d i 在【3 3 中定义： 5 去= ：r a 。i ，n 6 + , n + ( 。) 】2 2 。u m 。i n + ( 。) d 占 + ( ”) l ( “) 】4 2 2s e y m o u r 二出度猜想 蛄。学哂删2 州m 。i n - ( v ) d d n 删( u ) 记而= m i n 骷，蛄) ，他们得到以下结论： 定理2 1 _ 1 0 【3 3 】若d 为d 一正则有向图，a ( d ) 4 且如6 ，那么n 3 d + 1 尽管诸多学者分别从正、反两个方面对d ；，；等这一类特殊情形进行了 研究，但现有的结果尚未说明这类情形特别是关于g ( d ) = 3 的猜想4 和猜想9 成立与否 2 2s e y m o u r 二出度猜想 对任意的 v ( d ) ，我们记d + + v ) = i n + + ( 圳，称为”的二出度( s e c o n d o u t d e g r e e l 。s e y m o u r 提出下述猜想2 ： 猜想2 任一有向图d 中都存在顶点u v ( d ) ，使得l + + ( ) i i n + ( ) i ， 即d + + ( ) d + ( ) 我们通常称猜想2 为s e y m o u rs e c o n do u t d e g r e e 猜想，即s e y m o u r 二出度 猜想对于竞赛图，s e y