有向圖中的泛路問題.pdf

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

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

3、}且x不是橋首}則u，v是泛路點對.
　　定理設(shè)T是一個階為n的競賽圖，整數(shù)k滿足3＜k≤n，且k≥2δ+（T）+2.如果T包含一個t-路R，這里t＜k，并且若對某個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.
　　第二章的第二部分討論了一般競賽圖中的泛路及泛路點對，得到了以下結(jié)果:
　　定理

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

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