论文部分内容阅读
对有向图D中的任意一条长为k的路,若起点和终点相邻,则称有向图D是k准传递有向图.当k=2时,称为准传递有向图.k准传递有向图的概念是由Galeana-Sánchez等人在准传递有向图的基础上提出的.准传递有向图和k准传递有向图是有向图中非常重要的图类,近几年来,有关这类图的结构性质和其它相关内容的研究越来越受到学者们的关注,也取得了很多突出的成果.本文研究直径diam(D)≥k+2的强连通k准传递有向图的性质,并刻画了它的结构. 本文共分为三章. 第一章介绍了k准传递有向图的研究背景和现状以及一些与本文相关的基本概念. 第二章研究了k为偶数且diam(D)≥k+2的强连通k准传递有向图D的结构特征.设P是D中的一条长为k+2的最短路,得到以下结论: (1)D[V(P)]和D[V(D)V(P)]都是半完全有向图. (2)D有一条哈路. 第三章研究了k为奇数且diam(D)≥k+2的强连通k准传递有向图D的结构特征.设P是D中的一条长为k+2的最短路,得到以下结论: (1)D[V(P)]或者是半完全二部有向图,或者是半完全有向图. (2)令BC={x∈V(D)V(P):(x,V(P))≠(Φ)且(V(P),x)≠(Φ)},可以得到D[BC]或者是一个半完全二部有向图,或者是一个半完全有向图,或者是一个空图.