有向图中的泛路问题

来源 :山西大学 | 被引量 : 1次 | 上传用户:bailiyue
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究有向图中的泛路问题.阶为n的有向图D中,u,v是泛路点对是指u,v之间存在长为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∈V(T)满足下列条件  (1)如果d+(u)=n-1,v可任意.  (2)如果d+(u)≤n-1,对于强竞赛子图T[V(T){u}]的点v,d+(v)=min{d+(x);x∈V(T){u}且x不是桥首}则u,v是泛路点对.  定理设T是一个阶为n的竞赛图,整数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.  第二章的第二部分讨论了一般竞赛图中的泛路及泛路点对,得到了以下结果:  定理每个竞赛图都是泛路的.  定理设T是阶为n≥3的强竞赛图.其中V(T)中的任一对顶点u,v之间存在长为k的路,整数k满足2≤k≤n-1.  定理设T是阶为n≥3的一个非强竞赛图,在T中存在一对顶点u,v,它们之间有长为k的路,其中整数k满足1≤k≤n-1.  第三章讨论了半完全n-部有向图的一个注记,得到了以下结果:  定理 V1,V2,…,Vn是一个半完全n-部有向图D的n个部集.V(D)的一个分划V(D)=Y1∪Y2∪…∪Yp,Yi∩Yj=(0),i≠j,且Yi(→)Yj,1≤i<j≤p,并且要么对某个j∈{1,2,…,n}有Yi=Vj,要么D[Yi]是含有至少两个顶点的一个强连通半完全有向子图,则存在一对顶点u,v,使得u,v之间有长为k的路,其中k满足1≤k≤n-1.  定理设D是一个二重正则c-部竞赛图,其中c≥5,u,v是D中的一对顶点,使得u,v之间存在长为k的路,整数k满足2≤k≤c-1.  第四章讨论了强内竞赛图中的泛路及泛路点对,得到了下面的结果:  定理设D是阶为n≥5的一个强内竞赛图,满足δ(D)>8n-17/31.则D中存在一对顶点u,v,它们之间有长为k的路,k=4,5,…,n-1.  定理强内竞赛图是泛路的.
其他文献
该论文核心是建立或完善了几种处理多目标决策、群决策问题的方法,在研究中,遵从思想上有所创新、理论上可靠、计算操作简便、实际应用有效的原则.论文主要包括以下四种方法
本文分为四章。研究内容主要涉及两个方面:(1)多部竞赛图中经过给定顶点所有外弧的圈问题;(2)强连通竞赛图,即每部中只有一个顶点的强连通多部竞赛图中的外弧泛圈点的个数的研
该文共三部分,前两部分主要讨论Orlicz空间逼近的唯一性问题,第三部分主要讨论具有给定混合光滑模的多元周期函数空间B上的求积公式的误差估计方面的问题.
半无限规划问题(Semi-infinite programming,简称SIP)是数学规划的一个研究领域,它在工程设计、最优控制、经济均衡和交通平衡等领域有着广泛的应用.其研究引起国内外学者的
本文研究具有点控制的Euler-Bernoulli梁方程:(6)2z/(6)t2+(6)4z/(6)x4,x∈(0,ξ)∪(ξ,π),[(6)2z/(6)x2]ξ=0,[(6)3z/(a)x3]ξ=0;[(6)z/(6)x]ξ+α2/2(6)3z/(6)x2(6)t(ξ,t
该文采用了最优控制的理论,为冗余双机器人运动学协调控制问题提供了一个系统的解决方案.文中冗余双机器人分为开链式与闭链式两个方面进行研究.开链式的研究是用扩展雅可比
该文介绍一个新的税控系统的组成及其工作原理,着重介绍了"支持税务稽查的会计软件"的设计和实现."支持税务稽查的会计软件"是国家科委"税控收款机的研制与开发"项目的子课题
该文证明了单偶圈图满足猜想.指出了在单奇圈图中存在不满足猜想的反例.并给出了一类反例.指出了在单奇圈图中存在满足猜想的图.并给出了一类满足猜想的单奇圈图.证明了了任