【作者】 徐伟；

【导师】 钱建国；

【作者基本信息】 厦门大学 ， 应用数学， 2006， 硕士

【摘要】 对一个图G的每一条边指定一个方向使其成为有向图，这样所得到的有向图D称为图G的定向。如果有向图D中任意两点都是可以互达的，则称D为强定向。图G的平均距离μ（G）定义为所有的点对（若G为有向图则为有序点对）之间的距离的和的平均值。定义（?）_min（G）为取遍G的所有强定向的平均距离的最小值。本文主要考虑（?）_min（G）的问题，由两部分构成：第一部分主要考虑确定（?）_min（G）界的问题，给出了一般图的（?）_min（G）的下界，完全多部图、乘积图的（?）_min（G）的上界；特别地，在前面讨论的基础上对乘积图的上界又做了进一步的改进。而且，我们还提出了一个新的指标μ_min^*（G），讨论了它的一些性质以及它与（?）_min（G）的联系，从而给出了（?）_min（G）的一个下界。第二部分主要考虑了完全二部图的最优定向问题，我们首先给出了Sperner定理的一种扩展形式，在此基础之上我们确定了完全二部图（?）_min(K_p，q)的值，并且给出了它的最优定向。更多还原

【Abstract】 An oriented graph D of a graph G is obtained from G by assigning a direction to each edge of G; such an oriented graph is also called an orientation of G. An orientation D of G is strong if every two vertices in D are mutually reachable in D. The average distance μ（G） of G is defined to be the average among all distances between all pairs （ordered pairs if G is a digraph） of vertices of G. Let μ|→min（G） denote the minimum average distance taken over all strong orientations of a graph G. This paper deals with μ|→min（G）. The main is organized to two parts. Part one aims at bounding the index μ|→min（G）. We give a lower bound for general graphs and an upper bound for complete multipartite graphs and Cartesian product graphs, respectively. In particular, we improve the bound for some special Cartesian product graphs. Moreover, a new index μ^*min（G） is introduced which is shown to have a closed relation with μ|→min（G）. Then we give a lower bound for μ|→min（G） in terms of μ^*min（G）. Part two is to solve the optimal orientation for complete bipartite graphs. To this end, a generalization of Sperner’s theorem is established. By using this generalized Sperner’s theorem, we determine the exact value of μ|→min(K_P,q) by constructing an optimal orientation.更多还原