论文部分内容阅读
本文用图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.