多部競賽圖中包含指定頂點(diǎn)的路和強(qiáng)子競賽圖.pdf

1、競賽圖是有向圖研究中的熱點(diǎn)問題之一，它在實(shí)際問題中有極其廣泛的應(yīng)用.多部競賽圖是競賽圖的一個(gè)重要分支，其研究非常有意義，其中正則c-部競賽圖中包含給定頂點(diǎn)的路和強(qiáng)子競賽圖問題是多部競賽圖研究的一個(gè)熱點(diǎn)問題.
　　競賽圖是完全圖的定向圖.而且一般多部或者c-部競賽圖是完全c-部圖的定向圖.有向圖D的頂點(diǎn)集和弧集分別用V(D)和A(D)來表示.若x是有向圖D的一個(gè)頂點(diǎn)，那么我們用d+(x)和d-(x)分別表示x的出度和入度.一個(gè)有向圖

2、的全局非正則度被定義為: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是幾乎正則的.
　　本文內(nèi)容分為三章.文章中主要討論了正則c-部競賽圖中過指定頂點(diǎn)數(shù)目的路和正則c-部競賽圖中包含給定頂點(diǎn)的強(qiáng)子競賽圖這兩類熱點(diǎn)問題.
　　在第一章中，我們給出本文將用到的圖論方面的一些預(yù)備知識(shí)，主要介紹了圖論中的基本定義，

3、基本性質(zhì)及基本符號(hào)等內(nèi)容.
　　在第二章中，我們主要討論了在正則c-部競賽圖中過指定頂點(diǎn)數(shù)目的路這類問題，結(jié)果主要有如下幾個(gè):
　　(1)對于一個(gè)正則的c-部競賽圖D，V1，V2，…，Vc是圖D的部集，且|V1|=|V2|=…=|Vc|=r，在每一個(gè)部集中均除去n個(gè)頂點(diǎn)后余下的圖D'中還包含子競賽圖(1≤n≤r-1).
　　(2)若D是正則c-部競賽圖(c≥2)，V1，V2，…，Vc是D中的部集，且滿足|V1|=|V2

4、|=…=|Vc|=r≥6，則D中包含一條階為3c的路.
　　(3)設(shè)D是正則c-部競賽圖(c≥2)，V1，V2，…，Vc是D中的部集，且滿足|V1|=|V2|=…=|Vc|=r≥9，則D中包含一條來自每一部集至少兩個(gè)頂點(diǎn)且階為4c的路.
　　(4)設(shè)D是正則的c-部競賽圖(c≥2)，V1，V2，…，Vc是D的部集，而且滿足|V1|=|V2|=…=|Vc|=r≥3(n-1)，這里n∈N+而且n≥5，那么D中包含一條來自每一部集