论文部分内容阅读
竞赛图是有向图研究中的热点问题之一，它在实际问题中有极其广泛的应用.多部竞赛图是竞赛图的一个重要分支，其研究非常有意义，其中正则c-部竞赛图中包含给定顶点的路和强子竞赛图问题是多部竞赛图研究的一个热点问题. 竞赛图是完全图的定向图.而且一般多部或者c-部竞赛图是完全c-部图的定向图.有向图D的顶点集和弧集分别用V(D)和A(D)来表示.若x是有向图D的一个顶点，那么我们用d+(x)和d-(x)分别表示x的出度和入度.一个有向图的全局非正则度被定义为:ig(D)=max{d+(x)，d-(x)}-min{d+(y)，d-（y）}((V)x，y∈V(D)）.若ig(D)=0，则称D是正则的，若ig(D)≤1，则称D是几乎正则的. 本文内容分为三章.文章中主要讨论了正则c-部竞赛图中过指定顶点数目的路和正则c-部竞赛图中包含给定顶点的强子竞赛图这两类热点问题. 在第一章中，我们给出本文将用到的图论方面的一些预备知识，主要介绍了图论中的基本定义，基本性质及基本符号等内容. 在第二章中，我们主要讨论了在正则c-部竞赛图中过指定顶点数目的路这类问题，结果主要有如下几个: (1)对于一个正则的c-部竞赛图D，V1，V2，…，Vc是图D的部集，且|V1|=|V2|=…=|Vc|=r，在每一个部集中均除去n个顶点后余下的图D中还包含子竞赛图(1≤n≤r-1). (2)若D是正则c-部竞赛图(c≥2)，V1，V2，…，Vc是D中的部集，且满足|V1|=|V2|=…=|Vc|=r≥6，则D中包含一条阶为3c的路. (3)设D是正则c-部竞赛图(c≥2)，V1，V2，…，Vc是D中的部集，且满足|V1|=|V2|=…=|Vc|=r≥9，则D中包含一条来自每一部集至少两个顶点且阶为4c的路. (4)设D是正则的c-部竞赛图(c≥2)，V1，V2，…，Vc是D的部集，而且满足|V1|=|V2|=…=|Vc|=r≥3(n-1)，这里n∈N+而且n≥5，那么D中包含一条来自每一部集至少两个顶点且阶为nc的有向路. 第三章，我们主要讨论了正则c-部竞赛图中包含给定顶点的强子竞赛图这类问题，结果主要有如下这个: (1)设D是正则c-部竞赛图(c≥5)，V1，V2，…，Vc是D的部集，而且满足|V1|=|V2|=…=|Vc|=r＞2(c+1).那么D中每个顶点都包含在阶为p的强子竞赛图中，且p∈{3，4，5，…，c-2}.