【作者】 李杰；

【导师】 李胜家；

【作者基本信息】 山西大学 ， 运筹学与控制论， 2011， 硕士

【摘要】 本文分为三章.文章主要讨论了正则竞赛图的有向生成三角形问题和多部竞赛图中包含给定弧的路和圈问题.第一章是预备知识,我们介绍了一些本文中将要用到的图论方面的基本概念.第二章,我们研究了正则竞赛图中生成三角形的问题,主要结果如下：(1)设T是顶点个数为5的正则竞赛图,那么对于T的任意顶点x都存在生成T的2个有向三角形Ti使得V(Ti)∩V(Tj)=x,其中1≤i<j≤2.(2)设T是顶点个数为7的正则竞赛图,那么对于T的任意顶点x都存在生成T的3个有向三角形Ti使得V(Ti)∩V(Tj)=x,其中1≤i<j≤3.(3)设T是顶点个数为9的正则竞赛图,那么对于T的任意顶点x都存在生成T的4个有向三角形Ti使得V(Ti)∩V(Tj)=x,其中1≤i<j≤4.第三章,我们研究了多部竞赛图中包含给定弧的路和圈问题,主要结果如下：(1)设D是阶为n的c-部竞赛图,x,y是D中不同的顶点.如果c≥5且n>105ig(D)+2790,那么D中存在长为ι的(x,y)-路P对任意的42≤l≤n-1成立.(2)设D是阶为n的c-部竞赛图其中c≥5,P是D中长为l的路,如果n>105ig(D)+106l+2684,那么D中存在包含路P的H-圈.(3)设D是阶为n的c-部竞赛图其中c≥5,A=｛e1,e2…ek)是任意的k-可扩路弧集.如果n>105ig(D)+2366+424k,那么D中存在包含弧集A的Hamilton圈.更多还原

【Abstract】 This paper is composed of three chapters. In this paper, The problems of spanning directed triangles in the regularity tournaments and paths and cycles containing given arcs in multipartite tournaments are discussed.In the first chapter, we introduce some useful basic concepts which will be used in the paper.In the second chapter, We study the problem of spanning directed triangles in the regularity tournaments. The main results are as follows:(1) Let T is a regular tournaments of order 5, for any vertex x in V(T), there exist 2 triangles Ti such that:V(Ti)∩V(Tj)=χfor 1≤i＜j≤2.(2) Let T is a regular tournaments of order 7, for any vertex x in V(T), there exist 3 triangles Ti such that:V(Ti)∩V(Tj)=χfor 1≤i＜j＜3.(3) Let T is a regular tournaments of order 9, for any vertex x in V(T), there exist n triangles Ti such that:V(Ti)∩V(Tj)=χfor 1≤i＜j≤4.In the third chapter, We study the problem of paths and cycles containing given arcs in multipartite tournaments. The main results are as follows:(1) Let D is an c—partite tournament with order n,χ, y are different vertexs. if c≥5 and|V(D)|＞105ig(D)+2790, then there exists (χ, y)-path of length l, for all 42≤l≤|V(D)|-1 are right.(2) Let D is an c—partite tournament with order n and c≥5, P is a path of length l in D. if|V(D)|＞105ig(D)+106l+2684, then there exists a H—cycle containing path P in D.(3) Let D is an c—partite tournament with order n and c≥5, A=｛e1,e2…ek｝is an k—path extendible, if c≥5 and |V(D)|＞105ig(D)+2366+424k, then there exists a Hamilton-cycle containing A in D.更多还原