论文部分内容阅读
无向图G中两点u，v的距离是G中最短的(u，v)路的长.无向图G的直径是指G中任意两个顶点之间的最大距离.有向图中直径定义类似.有向图D中点u，v之间的强距离是包含u，v的D的强连通子图的最小弧数，有向图D的强直径指D中任意两点强距离的最大者.图G的定向是对G的每条边指定一个方向，这样由G得到的有向图D叫做G的定向.如果G的定向D中任意两点之间可以相互到达，则称D为G的强定向.在G的所有可能的定向中，强直径最小的定向称为G的最小强直径定向，其最小强直径记为sdiam(G). 本文分为三章，主要内容如下: 第一章的第一部分介绍了图的一些基本概念和术语.第二部分给出了强直径和最小强直径定向的一些重要结果. 第二章的第一部分主要讨论了最小强直径定向，得到了以下结果: 定理设H是n（n≥3）阶树，则sdiam(H(2)={2dian(H)+2，diam(H)≤22diam(H)，diam(H)≥3。 另外，对一般的n(n≥3)阶连通无向图G，我们还得到了下面的关系式:2diam(G)≤sdiam(G(2)≤2diam(G)+2. 第二章的第二部分讨论了圈的最小强直径定向，得到了以下结果: 定理当n是偶数时，sdiam(C(2)n)=2diam(Cn); 当n是奇数时，2diam(Cn)≤sdiam(C(2)n)≤2diam(Cn)+1. 第二章的第三部分讨论了单圈图的最小强直径定向，并有下面的结论: 定理若G是n阶单圈图，diam(G)≥3，则sdiam(G(2)=2diam(G). 第三章的第一部分讨论了路与路的乘积的最小强直径定向，得到了以下结果: 定理记Pk是长度为k-1的路，令G=Pm×Pn(m≥2，n≥2)则sdiam(G)=2diam(G). 并且还证明了，对无向图G，若ρ(G)=0，有sdiam(G)=2diam(G). 第二部分讨论了路与路的强乘积的最小强直径定向，得到了以下结果: 定理记Pk是长k-1的路，令G=Pm(⊕)Pn(m≥2，n≥4)，则sdiam(G)=2diam(G).