论文部分内容阅读
无向图G中两点u,v之间的距离是G中最短的(u,v)路的长.无向图G的直径是指G中任意两个顶点之间距离的最大者.类似地,有向图D中点u到点v的距离指u到v的最短路的长度.另外,Chartrand et al.定义了有向图D中两个点u,v之间的强距离sd(u,v)是包含u,v的D的强连通子图的最小弧数.有向图D中点v的强偏心距se(v)定义为v到V(D)中任意一点的强距离的最大值.有向图D的强直径指D中任意一个点强偏心距的最大值,类似地,有向图D的强半径指D中任意一个点强偏心距的最小值.给定一个无向图G,将G的每条边{x,y}用弧xy或yx替代后得到的有向图称为G的定向图.若连通图G在定向后是强连通的,则称该定向为G的强定向.使得G的所有定向图中强直径最大的定向称为G的最大强直径定向,其最大强直径记为SDIAM(G).在G的所有可能的强定向中,强直径最小的定向称为G的最小强直径定向,其最小强直径记为sdiam(G).同理,强半径的定向类似.对于无向图和有向图的直径,许多学者已经研究得出大量结果.对于有向图而言,有关强直径和强半径概念的提出较迟,而且关于其研究结果的文献还很少,因而研究难度也较大.本文主要研究了几个特殊有向图的强直径及其强半径的界.
本文分为四章,主要内容如下:第一章是预备知识,介绍了一些本文中将要用到的图论方面的基本概念和术语.
第二章简要介绍了关于强直径和强半径目前的研究结果.
第三章的第一部分首先讨论了圈的2顶点扩张图的最大强直径的界,并有如下结论:设H是阶n≥3的圈,令G=H(2),则有不等式SDIAM≥n+2.特别地研究了奇圈的2顶点扩张图的最小强直径的定向,得到如下结论:设H是阶n>3的圈,其中n为奇数,令G=H(2),则有结果sdiam(G)≤n
第二部分首先讨论了5圈添加弦后构成的弦图的2顶点扩张图的最小强直径的一个上界,并有如下结论:5圈添加弦构成的弦图记为H,令G=H(2),则有sdiam(G)≤5.接着讨论了6圈添加弦后构成的弦图的2顶点扩张图的最小强直径的一个上界,并成立结论:6圈添加弦构成的弦图记为H,令G=H(2),则有sdiam(G)≤6.一般地,将n圈添加弦构成的弦图记为H,令G=H(2),则有sdiam(G)≤n.
第四章则讨论了最小强直径与最小强半径相等的特殊图类.主要结果如下:(1)令G=C(2)3,那么sdiam(G)=srad(G).(2)令G=C(2)4,那么sdiam(G)=srad(G).(3)设H是4圈添加弦后构成的弦图,令G=H(2),那么sdiam(G)=srad(G).