【硕士论文】竞赛图的外弧泛圈性.pdf

《【硕士论文】竞赛图的外弧泛圈性.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中文摘要中文摘要本文分为三章．文中主要讨论了竞赛图中的外弧泛圈点问题以及在若干限制条件下的几类强连通竞赛图的外弧泛圈点问题．第一章主要介绍了本文的研究背景和相关内容．第二章是预备知识．在本章中，详细介绍了一些重要的。基本的定义．如竞赛图，k．强连通竞赛图以及外弧泛圈点等重要的概念和定义．并且在本章还详细给出了在第二章中将要用到的所有的引理和定理．第三章给出并证明了本文的全部重要结果．第3．1节中主要给出了具有强连通分解的竞赛图在某些限制条件下具有3个外弧泛圈点的两个充分条件．Yeo在文献【3】中曾经猜测2-强连通竞赛图包含3个外弧泛圈点．在第3．2节中，我们主要证明了对2-强连通竞赛图T，

2、如果饥，也是r的外弧泛圈点，并且T一{口1，也)不是强连通的，那么T包含—个不同于仇，也的顶点协，使得姐是T的外弧泛圈点．第3．3节主要讨论了3-强连通竞赛图的外弧泛圈点问题．本节中使用路收缩运算证明了一个3_强连通竞赛图T至少包含3个顶点口l，忱，地，使得％的所有外弧是4-泛圈的，其它两个顶点是T的外弧泛圈点．本节中的另外一个结论是如果口1是3-强连通竞赛图T中外度最小的顶点，也是Ⅳ+(”1)中外度最小的顶点，那么T包含—个不同于t，l，v2的顶点％，使得v3是T的外弧泛圈点．在第3．4节中，我们主要讨论了4-强连通竞赛图在度约束条件下包含3个外弧泛圈点的一个充分条件．关键词：竞赛图；强

3、连通竞赛图；外弧泛圈点；强连通分解；路收缩中圉分类号；0157．5百度排名http://www.001baidu.com/童装批发网http://www.tongzhuangpifawang.com/ABSTRACTThispaperiscomposedofthreechapters．Inthispaper，theproblemsoftheout-arcspaneydieverticesfortournamentsandafewkindsofstrongtournamentsarediscussedundersomeconstrainedconditions．Inthefirstchapt

4、er，thebackgroundandtherelatedcontentsareintroduced．Inthesecondchapter，themaincontentsarepreliminaries．Someimportantandbasicdefinitionswhichliketournaments，k-strongtournamentsandout-arespancyelie，eteareintroducedindetall．Thelemmasandtheoremswhicharerelatedofthepaperareintronducedinthispaper，too．Int

5、hethirdchapter，allofimportantresultsaregivenandproved．Twosufficientconditionsthatthetournamentswhichhavestrongdecompositionhavethreeout-arcspancyclievertisesaredescribedundersomeconstrainedconditionsinsection3．1．Yeoconjecturedthattherearethreeout-arespancyclieverteicesina2-strongtournamentsinbibli

6、ography[3]．ksection3．2．weprovethata2-strongtournamentTcontainsavertexv3whichisnotsametotIlandv2ifVland地areout-arcspancyeficverticesofTandT-{口1，地}isnotstrong．Insection3．3，theout-arcspancyclicproblenmofa3-strongtournamentarediscussed．Inthesection，weusepath-contractiontoprovethata3-stongtournamentTco

7、ntainsatleastthreevertices口l，也，蚀andallofout-aresof地are4-pancyclie，therestverticesareout-arespancyelicvertices．Anotherresultthat83-strongtournamentTcontains8out-arospancyclicvertex％whichisnotsameto711and712iftheou