有向图中的泛路问题

有向图中的泛路问题

论文摘要

本文主要研究有向图中的泛路问题.阶为n的有向图D中,u,υ是泛路点对是指u,υ之间存在长为k的路,其中k=1,2,·…,n-1.阶为n的有向图D中的泛路是指D中存在长为k的路,满足k=1,2,…,n-1.本文分为四章,主要内容如下:第一章的第一部分介绍了有向图的一些基本概念和术语.第二部分给出了圈与路的一些重要结果.第二章的第一部分主要讨论了特殊竞赛图中的泛路点对,得到了以下结果:定理设T是n个顶点的非强竞赛图,其中d+(u)=max{d+(x);x∈V(T)},u1,u2,…,un-1是T[V(T)\{u}]的n-1个顶点标号,且T[V(T)\{u}]是强竞赛子图.同时有d+(u1)≤d+(u2)≤…≤d+(un-1),设u,υ∈V(T)满足下列条件(1)如果d+(u)=n-1,υ可任意.(2)如果d+(u)≤n-1,对于强竞赛子图T[V(T)\{u}]的点υ,d+(υ)=min{d+(x);x∈V(T)\{u}且x不是桥首}则u,υ是泛路点对.定理设T是一个阶为n的竞赛图,整数k满足3<k≤n,且k≥2δ+(T)+2.如果T包含一个t-路Pt,这里t<k,并且若对某个u∈V(Pt)有N-(u)(?)V(Vt),则在T中存在路只+1,只+2,…,Rk,使得|V(Pi)|=i和V(只-1)(?) V (Pi),其中i有t+1≤i≤k.第二章的第二部分讨论了一般竞赛图中的泛路及泛路点对,得到了以下结果:定理每个竞赛图都是泛路的.定理设T是阶为n≥3的强竞赛图.其中V(T)中的任一对顶点u,υ之间存在长为k的路,整数k满足2≤k≤n-1.定理设T是阶为n≥3的一个非强竞赛图,在T中存在一对顶点u,υ,它们之间有长为k的路,其中整数k满足1≤k≤n-1.第三章讨论了半完全n-部有向图的一个注记,得到了以下结果:定理V1,V2,…,V。是一个半完全n-部有向图D的n个部集. V(D)的一个分划V(D)=Y1∪Y2∪…∪Yp,Yi∩Yj=φ,i≠j,且K(?)Yj,1≤i<j≤p,并且要么对某个j∈{1,2,…,n}有Yi=Vj,要么D[Yi]是含有至少两个顶点的一个强连通半完全有向子图,则存在一对顶点u,υ,使得u,υ之间有长为k的路,其中k满足1<k<n-1.定理设D是一个二重正则c-部竞赛图,其中c≥5,u,υ是D中的一对顶点,使得u,υ之间存在长为k的路,整数k满足2≤k≤c-1.第四章讨论了强内竞赛图中的泛路及泛路点对,得到了下面的结果:定理设D是阶为n≥5的一个强内竞赛图,满足则D中存在一对顶点u,υ,它们之间有长为k的路,k=4,5,…,n-1.定理强内竞赛图是泛路的.

论文目录

  • 中文摘要
  • ABSTRACT
  • 引言
  • 第一章 预备知识
  • 1.1 图论的有关术语和符号
  • 1.2 相关结果
  • 第二章 竞赛图中的泛路
  • 2.1 特殊竞赛图中的泛路点对
  • 2.2 竞赛图中的泛路及泛路点对
  • 第三章 半完全n-部有向图的一个注记
  • 第四章 强内竞赛图中的泛路
  • 结束语
  • 参考文献
  • 研究成果
  • 致谢
  • 个人简况
  • 相关论文文献

    标签:;  ;  ;  ;  ;  

    有向图中的泛路问题
    下载Doc文档

    猜你喜欢