关于图的边添加和边减少问题研究

摘要

本文用图G来作为互连网络拓扑结构的模型.图G的直径是网络延迟和通信有效性的重要度量.在实时系统中，信息传输延迟被限制在某个时间内，超出这个时间接收到的信息是无效的.一种减小传输延迟的办法是给网络增加连线，使得信息传输时间限制在给定范围内.前人已经证明在任意一个直径为d的图中添加t条边后得到的变更图的直径不会小于一条长为d的路添加t条边后所得图的直径. 本文研究的是“加边问题”和“减边问题”.确定了以下参数值的范围和某些精确值. 用P(t，d)和C(t，d)分别表示在n阶无向路和n阶无向圈中添加t条边后得到的变更图的最小可能直径. 用TP(p，d)和TC(p，d)分别表示在n阶无向路和n阶无向圈中至少需要添加的边数，使得变更图的可能直径不大于p. 用f(t，d)表示在直径为d的连通图中去掉t条边后得到的连通图的最大可能直径. 在第二章中，我们对某些满足与k相关条件的t和d证明了P(t，d)≤2k或P(t，d)≤2k+1.主定理证明中用到了不等式的上界. 在第三章中，我们得到以下结果： 1.当t≥4，d≥3时，有[d-2/t+1]≤P(t，d)≤[d-2/t+1]+1；对t≥4和某些d值有P(t，d)=[d-2/t+1]+1. 2.当t≥3，d≥2时，有C(t，d)≥[d-1/t+2]，并且对某些特殊的t和d值不等式取等号.对某些t和d值也得到了C(t，d)的最优界. 3.当p≥4,d≥12时；有[d/p]-1≤TP(p,d)≤[d-7/p-3]-1.当P(t，d)=[d-2/t+1]+1和t≥4时;有[d-2/p-1]-1≤TP(p,d)≤[d-2/p-2]-1.当d≥11时，有d-7≤TP(3，d)≤d-3;TC(3，d)=d-8;其中后者是Grigorescu的猜想. 4.对于t≥3，d≥3；当P(t，d)=[d-2/t+1]+1时有f(t，d)≥(t+1)d-t+1；其它情形有f(t，d)≥(t+1)d+t.对某些t和d值证明了Schoone等人的猜想f(t，d)≤(t+1)d-t+1.

目录

文摘

英文文摘

Acknowledgements

Chapter 1 Introduction

Chapter 2 Some Upper Bounds of P(t, d)

Chapter 3 Edge Addition and Deletion of Altered Graphs

Further Researchs

References

Published Papers