论文部分内容阅读
图G的距离和是G的所有顶点对之间距离的和，记为σ(G)，也被称为“Wiener数”.图G的平均距离是G的所有点对（若G为有向图，则为有序点对）之间的距离和的平均值，记为μ(G).图G的定向是对G的每条边指定一个方向，这样由G得到的有向图D叫做G的定向.如果G的定向D中任意两点之间可以相互到达，则称D为G的强定向.在G的所有可能的定向中，平均距离最小的定向称为G的最小平均距离强定向，其平均距离记为μmin(G). 本文分为三章，主要内容如下: 第一章的第一部分介绍了图的一些基本概念和术语.第二部分给出了平均距离和最小平均距离强定向的一些重要结果. 第二章的第一部分主要讨论了k点强连通图，k弧强连通图的距离和平均距离，证明了: D是n阶k点强连通简单有向图，则diam(D)≤(「)n-2/k」+1，μ(D)≤(「)n-2/k」+1-k((「)n-2/k」+1)(「)n-2/k]/2（n-1）. D是n阶k弧强连通简单有向图，则diam(D)≤｛2, k＞n-2/2;(「)n-2(k+1)/√k」+3，k≤n-2/2.μ(D)≤(「)(n-k+2√k)2-3n/2√k+k-1」/n-1. 第二章的第二部分讨论了平均距离与控制数，并给出了一个比较简单的结果:G是控制数为γ(G)的简单连通无向图，则μG）≤max{3/2γ(G)，2}.第三部分给出了一些复合图平均距离的界. 第三章的第一部分考虑了一些复合图的最小平均距离强定向，证明了: G是顶点为v1,v2,…,vm（m≥3）的简单连通图， Kc1,Kc2,…,Kcm为顶点数大于1的K1,K2，…,Km的补图，则μmm（G[Kc1,Kc2，…,Kcm]）≤2μ（G[Kc1,Kc2…,Kcm]）.第二部分讨论了每条边都在3-圈上的简单图的最小平均距离强定向，并证明了:G是每条边都在3-圈上的简单无向图，则μmin(G)≤5/3μ(G).这一结果改进了P.Dankelmann.O.R.Oellermann，W.Jian-liang已有的结果.