论文部分内容阅读
本文分为三章.主要讨论了竞赛图中的外弧泛圈点问题以及在若干限制条件下的几类强连通竞赛图的外弧泛圈点问题.
第一章主要介绍了本文的研究背景和相关内容.
第二章是预备知识.在本章中,详细介绍了一些重要的,基本的定义.如竞赛图,k-强连通竞赛图以及外弧泛圈点等重要的概念和定义.并且在本章还详细给出了在第二章中将要用到的所有的引理和定理.
第三章给出并证明了本文的全部重要结果.
第3.1节中主要给出了具有强连通分解的竞赛图在某些限制条件下具有3个外弧泛圈点的两个充分条件. Yeo在文献[3]中曾经猜测2-强连通竞赛图包含3个外弧泛圈点.
在第3.2节中,本文主要证明了对2-强连通竞赛图T,如果v<,1>,v<,2>是T的外弧泛圈点,并且T-{v<,1>,v<,2>)不是强连通的,那么T包含—个不同于v<,1>,v<,2>的顶点v<,3>,使得v<,3>是T的外弧泛圈点.
第3.3节主要讨论了3-强连通竞赛图的外弧泛圈点问题.本节中使用路收缩运算证明了一个3-强连通竞赛图T至少包含3个顶点v<,1>,v<,2>,v<,3>,使得v<,3>的所有外弧是4-泛圈的,其它两个顶点是T的外弧泛圈点.本节中的另外一个结论是如果v<,1>是3-强连通竞赛图T中外度最小的顶点,v<,2>是N+(v<,1>)中外度最小的顶点,那么T包含一个不同于v<,1>,v<,2>的顶点v<,3>,使得v<,3>是T的外弧泛圈点.
在第3.4节中,主要讨论了4-强连通竞赛图在度约束条件下包含3个外弧泛圈点的一个充分条件.