| 【中文题名】 | 强定向的最小平均距离 |
| 【英文题名】 | Minimum Average Distance of Strong Orientations |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-5-25 |
| 【中关键词】 | 定向,平均距离,Sperner定理推广,,, |
| 【英关键词】 | Orientation,Average distance,Generalization of Sperner's theorem, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 对一个图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))的值，并且给出了它的最优定向。 |
| 【论文题纲】 |
|
中文摘要 |
4-5 |
|
英文摘要 |
5-8 |
|
第一章 引言 |
8-15 |
|
第二章 定向图平均距离的界 |
15-23 |
|
§2.1 一般图的平均距离的界 |
15-16 |
|
§2.2 定向图的新指标μ_(min)~* |
16-18 |
|
§2.3 完全多部图和乘积图的平均距离的界 |
18-23 |
|
第三章 Sperner定理的一个推广及完全二部图的最优定向 |
23-31 |
|
§3.1 Sperner定理的推广 |
23-29 |
|
§3.2 完全二部图的最优定向 |
29-31 |
|
参考文献 |
31-34 |
|
致谢 |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.11803 |
