有向圖中的泛路問(wèn)題.pdf

1、本文主要研究有向圖中的泛路問(wèn)題.階為n的有向圖D中，u，v是泛路點(diǎn)對(duì)是指u，v之間存在長(zhǎng)為k的路，其中k=1，2，…，n-1.階為n的有向圖D中的泛路是指D中存在長(zhǎng)為k的路，滿足k=1，2，…，n-1.
　　本文分為四章，主要內(nèi)容如下:
　　第一章的第一部分介紹了有向圖的一些基本概念和術(shù)語(yǔ).第二部分給出了圈與路的一些重要結(jié)果.
　　第二章的第一部分主要討論了特殊競(jìng)賽圖中的泛路點(diǎn)對(duì)，得到了以下結(jié)果:定理設(shè)T是n個(gè)頂點(diǎn)的非

2、強(qiáng)競(jìng)賽圖，其中d+（u）=max{d+(x);x∈V（T）}，u1，u2，…，un-1是T[V（T）\{u}的n-1個(gè)頂點(diǎn)標(biāo)號(hào)，且T[V(T)\{u}]是強(qiáng)競(jìng)賽子圖.同時(shí)有d+(u1)≤d+(u2)≤…≤d+（un-1），設(shè)u，v∈V（T）滿足下列條件
　　(1)如果d+(u)=n-1，v可任意.
　　(2)如果d+(u)≤n-1，對(duì)于強(qiáng)競(jìng)賽子圖T[V(T)\{u}]的點(diǎn)v，d+(v)=min{d+(x);x∈V(T)\{u

3、}且x不是橋首}則u，v是泛路點(diǎn)對(duì).
　　定理設(shè)T是一個(gè)階為n的競(jìng)賽圖，整數(shù)k滿足3＜k≤n，且k≥2δ+（T）+2.如果T包含一個(gè)t-路R，這里t＜k，并且若對(duì)某個(gè)u∈V(Pt)有N-(u)(c) V(Pt)，則在T中存在路Pt+1，Pt+2，…，Pk，使得|V(Pi)|=i和V(Pi-1)(c) V（Pi），其中i有t+1≤i≤k.
　　第二章的第二部分討論了一般競(jìng)賽圖中的泛路及泛路點(diǎn)對(duì)，得到了以下結(jié)果:
　　定理

4、每個(gè)競(jìng)賽圖都是泛路的.
　　定理設(shè)T是階為n≥3的強(qiáng)競(jìng)賽圖.其中V(T)中的任一對(duì)頂點(diǎn)u，v之間存在長(zhǎng)為k的路，整數(shù)k滿足2≤k≤n-1.
　　定理設(shè)T是階為n≥3的一個(gè)非強(qiáng)競(jìng)賽圖，在T中存在一對(duì)頂點(diǎn)u，v，它們之間有長(zhǎng)為k的路，其中整數(shù)k滿足1≤k≤n-1.
　　第三章討論了半完全n-部有向圖的一個(gè)注記，得到了以下結(jié)果:
　　定理 V1，V2，…，Vn是一個(gè)半完全n-部有向圖D的n個(gè)部集.V(D)的一個(gè)分劃V(

5、D)=Y1∪Y2∪…∪Yp，Yi∩Yj=(0)，i≠j，且Yi(→)Yj，1≤i＜j≤p，并且要么對(duì)某個(gè)j∈{1，2，…，n}有Yi=Vj，要么D[Yi]是含有至少兩個(gè)頂點(diǎn)的一個(gè)強(qiáng)連通半完全有向子圖，則存在一對(duì)頂點(diǎn)u，v，使得u，v之間有長(zhǎng)為k的路，其中k滿足1≤k≤n-1.
　　定理設(shè)D是一個(gè)二重正則c-部競(jìng)賽圖，其中c≥5，u，v是D中的一對(duì)頂點(diǎn)，使得u，v之間存在長(zhǎng)為k的路，整數(shù)k滿足2≤k≤c-1.
　　第四章討論了