（运筹学与控制论专业论文）关于一类图的可圈性与强连通可推性.pdf

硕士学位论文 m a s t e r 。st h e s i s 摘要 设g 是无向简单图，定义伊为g 的k 次幂，其顶点集v ( c ) = y ( g ) ， 边集e ( c ) = u v l d c ( u ，口) k ，乱， y ( g ) ) 设d 是一有向图，如果d 中 存在有向圈a 含d 中所有顶点，则称g 为d 的哈密尔顿有向圈如果d 中含有一个哈密尔顿有向圈，则称d 为哈密尔顿有向图若对有向图| d 中任 意两个不同顶点z ，y ，d 中既存在从z 到y 的有向路，又存在从y 到2 7 的有 向路，则称d 为强连通有向图在有向图d 中，定义推点”为将d 中所有 与口关联的弧反向若一同构于日的有向图可通过对有向图d 施行一系列 推点运算得到，则称d 可推为h 若某简单图的所有定向均可推成哈密尔顿 有向图，则称其为可固图 c a m i o n 的一个著名定理宣称一个竞赛图是强连通有向图当且仅当其为哈 密尔顿有向图k l o s t e r m e y e r 证明了固平方的任意一个定向可推成强连通有 向图当且仅当其可推成哈密尔顿有向图在本文中，我们将证明路的三次方的 任意一个定向可推成强连通有向图当且仅当其可推成哈密尔顿有向图作为 推论，当礼4 和n = 偶数时，阶为n 的路的三次方的2 抽“个定向中存在 2 。一6 2 n 个定向可推成哈密尔顿有向图( 从而可推成强连通有向图) 关键词：哈密尔顿有向图；强连通；推点 硕士学位论文 m a s t e r st h e s i s a b s t r a c t l e tgb ea s i m p l eg r a p h ，a n dg b e a s i m p l eg r a p h o nt h es a m ev e r t e xs e t a sgs u c ht h a tt w ov e r t i c e si ng a r ea d j a c e n ti fa n do n l yi ft h e yh a v ed i s t a n c e a tm o s tki ng a s s u m edb ead i g r a p h ad i r e c t e dc y c l eci sah a m i l t o n d i r e c t e dc y c l ei fv ( c ) = 矿( d ) a d i g r a p hd i sh a m i l t o n i a ni fdc o n t a i n sa h a m i l t o nd i r e c t e dc y c l e ad i g r a p hdi ss t r o n g l yc o n n e c t e d ( o r ，j u s ts t r o n g ) i f ， f o re v e r yp a i rz ，yo fd i s t i n c tv e r t i c e si nd ，t h e r ee x i s t sa nz yd i r e c t e dp a t h a n day zd i r e c t e dp a t h p u s h i n gav e r t e x i nad i g r a p hr e v e r s e sa l lt h e o r i e n t a t i o n so fa l la r c si n c i d e n tw i t hv w es a yt h a tad i g r a p hdc a nb ep u s h e d t oad i g r a p hhi fad i g r a p hi s o m o r p h i ct ohc a nb eo b t a i n e db ya p p l y i n ga s e q u e n c eo fp u s h e st od ag r a p h i ss a i dt oc y c l a b l ei fe a c ho fi t so r i e n t a t i o n s c a nb ep u s h e dt oah a m i l t o n i a nd i g r a p h c a m i o n st h e o r e ms t a t e st h a tat o u r n a m e n ti ss t r o n gi fa n do n l yi fi th a s ah a m i l t o nd i r e c t e dc y c l e k l o s t e r m e y e rp r o v e dt h a ta no r i e n t a t i o nc 2o ft h e s q u a r eo f ac y c l ecc a d _ b em a d e s t r o n gu s i n gt h ev e r t e xp u s ho p e r a t i o ni fa n d o n l yi fi tc a nb em a d e t oh a v eah a m i l t o nd i r e c t e dc y c l eu s i n gt h ev e r t e xp u s h o p e r a t i o n i nt h i sp a p e r ，w ew i l lp r o v et h a ta no r i e n t a t i o np 3o ft h ec u b eo f ap a t hpc a nb em a d es t r o n gu s i n gt h ep u s ho p e r a t i o ni fa n do n l yi fi tc a n b em a d eh a m i l t o n i a nu s i n gt h ep u s ho p e r a t i o n a sac o r o l l a r y 7w eg e tt h a t 2 瓤一2 ”o ft h ep o s s i b l e2 3 ”一6o r i e n t a t i o n so ft h ec u b eo fap a t h ，f o rn24 ， c a l lb em a d et oh a v eah a m i l t o n i a nd i r e c t e dc y c l e ( a l s oc a db em a d es t r o n g ) u s i n gv e r t e xp u s h e s k e y w o r d s ：h a m i l t o n i a nd i g r a p h ；s t r o n g ；p u s hv e r t e x i i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明；所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 玲巧恢 日期：z 棚5 年占月，目 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名：均n j 霞 日期：多p 5 年占月，j 日 导师签名瑚铣 b 瓤：铽年6 冠” 本人已经认真阅读“c a m s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定事受相关权益。回塞途塞握童厦遗蜃i 旦圭生! 旦二笙i 旦三生 筮壶! 作者签名：泠。，霞 日期：加5 年易月，f 目 硕士学位论文 m a s t e r st i - i e s i s 1 引言 c a m i o n 的著名定理【1 2 ，1 3 宣称一个竞赛图是强连通有向图当且仅当其 为哈密尔顿有向图k l o s t e r m e y e r 证明了圈平方的任意一个定向可推成强连 通有向图当且仅当其可推成哈密尔顿有向图f 在有向图中，如果与某个顶点相 关联的弧均反向，则称该顶点被推) 在本文中，我们将证明路的三次方的任意 一个定向可推成强连通有向图当且仅当其可推成哈密尔顿有向图作为推论， 当n 4 和n = 偶数时，阶为? j 的路的三次方的所有定向中存在2 3 ”6 2 ” 个定向可推成哈密尔顿有向图( 从而可推成强连通有向图) 推点运算过去曾被f i s h e r 和r y a n 【2 】研究过，他们主要在竞赛图中研究 该运算，主要成果是计算由该运算生成的非同构等价类k l o s _ l ；e r m e y e r 等人 3 ，5 ，6 1 主要在竞赛图，多部竞赛图和图的幂中研究该运算，特别是在可圈图 ( 若某简单图的所有定向均可推成哈密尔顿有向图，则称其为可圈图) 类中 文献f 3 1 中已证阶至少是5 的竞赛图一定能推成哈密尔顿有向图文献 5 i 中 证明了阶至少是1 2 的竞赛图不仅能推成哈密尔顿有向图，而且能推成至少含 n 蠢- 1 个哈密尔顿有向圈的图，此处1 o 1 ，并且断言6 对j 一1 成立在断言1 中取i = j + 1 知，弱4 圈v j v j 一1 ”舟2 勘+ 3 口，为坏的，因为v j y j l a ( d 7 ) ，”对2 v j 十3 a ( d ，) ， 所以 q 一1 v j + 2 】v j + 3 ) a ( d ) 或者 码+ 2 “v j v j + 3 ) a ( d ) ，由该结论 和数学归纳法容易证明断言6 对所有的j = 1 ，2 ，2 一3 成立 口 据断言6 ，我们可以确定d 7 上的所有长弧均符合a ( 或口) ，以下根据弧 u ，均是否属于a ( d ) 分两种情形进行讨论 情形1 3 啦a ( d 7 ) 该情形下，我们将证明d = a 首先，根据断言2 知，对任意的i 一3 ，4 ，2 k 一3 ，弱4 一圈v i v i 一2 v i + l ? ) i + 3 v i 是坏的又根据断言6 ，v i - - 2 v 件1 a ( d ) 当且仅当v i v i + 3 a ( d ) 因此对所 有的i = 3 ，4 ，2 一3 v i v i 一2 a ( d 7 ) = = = v i + iv i + 3 a ( d 7 ) ( 女) 1 7 硕士学位论文 m a s t e r st h e s i s 由( ) 式的递推关系以及弧v 3 v 1 ，v 2 v 4 ，v 5 v 3 即可以确定d 上所有中弧均 符合a 故仅需证明口2 a ( d ) 和v 5 v 3 a ( d ) 即可 根据断言4 知，弱4 一圈v 4 v 3 l v 2 v 4 是坏的因为 l u 2 ，v 3 v 1 ，v 3 v 4 a ( d ，) 7 所以 1 ) 2 0 4 a ( d ，) 又由于u i v 2 ，v 3 v l ，v 5 v 2 a ( d ) ，所以据断言5 ，有 0 5 7 ) 3 a ( d ，) 情形2v l 0 3 a ( d 7 ) 类似于情形l ，可以证明d = b 口 下面将证明定理3 和推论1 定理3 的证明：因为哈密尔顿有向图一定是强连通的，故只须证必要性 假定碳的某种定向d 能够推成强连通有向图，则d 一定能够推成哈密尔 顿有向图，否则的话，据引理9 ，d 一定能推成a 或_ b 由引理5 和引理6 ， 可知a 和b 均不能推成强连通有向图，所以d 不能推成强连通有向图，与 假定矛盾 口 推论1 的证明：容易知道，碳一共有2 6 杠6 种定向据引理4 ，每个等 价类含有2 2 。个定向据引理5 , 6 ，9 可知，除了a 和b 所在的等价类以外 所有的定向均能推成哈密尔顿有向图( 从而可推成强连通有向图) ，所以结论成 立 1 8 口 硕士学位论文 m a s t e r lst h e s i s 参考文献 【1 r d i e s t e l ，g r a p ht h e o r y , s p r i n g - v e r l a gn e w y o r k ，2 0 0 0 【2 2 df i s h e ra n dj r y a n ( 1 9 9 5 ) ，t o u r n a m e n tg a m e sa n dp o s i t i v et o u r n a m e n t s ， j g r a p ht h e o r y , v 0 1 1 9 ，p p 2 1 7 - 2 3 6 【3 3w k l o s t e r m e y e r ( 1 9 9 7 ) ，p u s h i n gv e r t i c e sa n do r i e n t i n ge d g e s ，a r sc o m b i n a t o r i a t oa p p e a r 4 w k l o s t e r m e y e r ，a na n a l o g u eo fc a m i o n st h e o r e m i ns q u a r e so fc y c l e s ， t oa p p e a r f 5 w k l o s t e r m e y e r ，c m y e r s ，a n dl s o l i d s ( 1 9 9 7 ) ，p u s h i n g v e r t i c e si nt o u r n a - m e n t sa n dm u l t i p a r t i t et o u r n a m e n t s ，p r e p r i n t 6 1 6w k l o s t e r m e y e ra n d s o l i d ( 1 9 9 8 ) ，h a m i l t o n i c i t ya n dr e v e r s i n ga r c si n d i g r a p h s ，j g r a p ht h e o r y , v o l ，2 8 ，p p 1 3 3 0 f 7 1 k m m o s e s i a n ( 1 9 7 2 ) ，s t r o n g l y b a s a b l e g r a p h 8 ( r u s s i a n ) a k a d n a u k a r m i a n s s rd o k l ，v o l5 4 ，p p 1 3 4 - 1 3 8 8 o p r e t z e l ( 1 9 9 1 ) ，o r i e n t a t i o n s a n d e d g e l 丑m e t i m mo n g r a p h s ，i n s u r v e y si nc o m b i n a t o r i c s ，a d k e e d w e l l ，e d i t o r ，l o n d o nm a t h e m a t i c a ls o - e i e t yl e c t u r en o t e ss e r i e s ，n o 1 6 6 ，p p 1 6 t 一1 8 5 9 】o p r e t z e l ( 1 9 8 6 ) ，o nr e o r i e n t i n gg r a p h sb yp u s h i n gd o w n m a x i m a lv e t t i c e s ，o r d e r ，v 0 1 3 ，p p ，1 3 5 - 1 5 3 f 1 0 1o p r e t z e l ( 1 9 8 5 ) ，o ng r a p h st h a tc a nb eo r i e n t e d a sd i a g r a m so fo r d e r e d s e t s o r d e rv o l ，2 p p 2 5 4 0 1 1 1 g m a c g i l l i v r a ya n dk w o o d ( 1 9 9 7 ) ，r e - o r i e n t i n gt o u r n a m e n t sb yp u s h i n g v e r t i c e s ，m a n u s c r i p t ，u n i v e r s i t yo fv i c t o r i a 【1 2 p c a m i o n ( 1 9 5 9 ) ，c h e m i n s e tc i r