多部竞赛图的(拟)外弧泛圈点问题

来源 :山西大学 | 被引量 : 0次 | 上传用户:lxw19831201
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文分为四章。研究内容主要涉及两个方面:(1)多部竞赛图中经过给定顶点所有外弧的圈问题;(2)强连通竞赛图,即每部中只有一个顶点的强连通多部竞赛图中的外弧泛圈点的个数的研究。  第一章主要介绍了本文的研究背景和要解决的科学问题。  第二章是预备知识。我们详细介绍了一些基本的但是非常重要的定义,并且还详细给出了在第三、四章中将要用到的所有的引理、定理和推论。  第三章主要研究了多部竞赛图中经过给定顶点所有外弧的圈问题。竞赛图中外弧泛圈点个数的问题已研究的相对完善,但在多部竞赛图中这个问题则显得比较困难。2004年,Guo and Volkmann在文献[6]中证明了强连通的半完全n-部(n≥3)有向图中每个顶点都包含在一个Cq-圈中,并且对每个q∈{3,…,n},使得V(C3)(∈)…(∈)V(Cn)成立。受竞赛图中外弧泛圈点问题的启发,我们考虑在某些限定条件下的多部竞赛图中某个顶点的所有外弧是否具有上述性质。我们给出本章的主要结论:  定理3.1:若D是一个强连通的n-部(n≥3)竞赛图,κ(D)=1且D中每条弧都包含在D中的一个3-圈中,则D中至少包含3个顶点v1,v2,v3使得每个vi(i=1,2,3)的外弧都包含在一个Cj-圈中,且对每个j∈{3,4,…,n},均有V(C4)(∈)…(∈)V(Cn)成立。  第四章主要研究了连通度为1且最小外度至少为2的竞赛图中外弧泛圈点的个数问题。关于竞赛图中外弧泛圈点个数的问题已有许多结果。Feng证明了s-强连通(s≥3)的竞赛图含有s+1个4-外弧泛圈点且证明了3-强连通的竞赛图至少包含3个外弧泛圈点;Guo证明了2-强连通的竞赛图包含至少3个外弧泛圈点。因此只剩下连通度为1的竞赛图中外弧泛圈点个数的研究。下面我们给出本章的主要结论:  定理4.2:设T是含n个顶点的竞赛图,κ(T)=1并且最小外度至少为2。则T至少包含3个外弧泛圈点。
其他文献
近年来,自然语言研究的热点已经转到了语义角色标注上来。本文以汉语框架语义知识库为基础,结合汉语自身的特点,重点研究了汉语框架语义角色自动标注问题,为以后构建大规模的