随着信息网络的飞速发展,许多与之相关的理论性问题越来越引起人们的重视,其中之一即为网络的信息传输延迟.网络的信息传输延迟是指在网络中数据在中间结点频频储存和转发而形成的传输时间,是网络设计中需要关注的一个主要因素.我们通常用一个有向图来模拟一个网络,其中一个点对应一个处理器,一条弧对应一条通信通道.实际上,如果所有的通信通道都是双向连通的,这个有向图图就是一个无向图.对于一个网络的性能来说,有向图和无向图的直径D（G）是一个非常重要的因素,因为它能直接反映点对点互联网络的传输延迟.因此,人们通常选择网络所对应的图的直径作为数据传输延迟的度量.在这样一个背景下,对于网络来说直径应该是越小越好.在实时系统中,传输延迟必须控制在一定的时限范围内,因为超过这个时限到达的数据被认为是无用的.无限制的添加边当然能做到这一点,但不可取,因为这样不仅会增加过多的费用,而且不利于网络布线.因此,添加的连线要尽可能的少.而这个最小数目究竟是多少呢?这就是我们的添加边问题要研究的东西.当通信发生故障时,相当于在图中去掉相应的边.在实时系统中,要求在发生故障时的通信延迟仍然不超过一个给定的实数h,问题是最多可以去掉多少条边,这就是所谓的减边问题.以下4个参量是添、减边后直径变化的度量：D-k（G）表示使G直径减少至少k所要加到G上的边的最小数目；D+k（G）表示使G的直径增加至少k所要从G删去边的最小数目；D+0（G）表示保持G直径不变删去边的最大数目；D-0（G）表示保持G直径不变增加边的最大数目.据我们所知,对于有向图来说这几个参数还没有研究过.在上述定义中将边改为弧,即得到了有向图G的D+k,D-k,D-0,D+0这四个量.本文主要研究添加或者删除有向图Cm和Tm,n上的某些弧时它们的直径变化情况.本文共分四章.第一章,我们介绍了研究背景及相关研究.第二章,我们给出了在有向圈Cm和有向环形网络Tm,n上加弧使其直径至少减少k所需弧的最小数目.结论如下：1.当m≥4时,D*（Cm）=[（3m）/4]－1,其中D*（Cm）表示以不同的方式在Cm上加两条弧e1,e2所得到的所有新图的直径的最小值.2.当m≥4时,对于任意一个满足1≤k≤[m/4]的整数k,D-k（Cm）=2.3.当max{m,n}≥4时,D（Tm,n）=2.4.设m≥4（n+k－1）,则D-k（Tm,n）=2.5.假设m≥4k且k≤[n/2],那么D-k（Tm,n）≤4.第三章,我们得出了对某些强连通有向图加弧保持直径不变的以下三个结论.1.对任意一个n个顶点,m条弧且没有双向弧的强连通有向图G=（V,A）,D-0r（G）=n（n－1）/2－m,其中D-0r（G）为使得图G直径没有改变且不出现双向弧所加的弧的最大数目.2.设G是一个n个顶点,m条弧的点传递有向图,u是点集V（G）中的任意一点.对于r=0,1….,D（G）,记nr=｜Nr（u）｜,其中且Mr（u）={v∈V（G）｜distG（u,v）=r}.当nD（G）=1时有3.D-0（Cn）=（n－2）（n+1）/2.4.设m≤n,那么D-0（Tm,m）=3/2m2n2+8mn+66－40m－33n+6m2+m3－3/2m2n第四章,给出了删除有向图Cm和Tm,n上的某些弧使其直径增加至少k的两个结论：1.对于任意顶点数不小于2的强连通图,D+k（G）≤δ（G）恒成立,其中k是正整数.2.当k≥1时,D+k（Cn）=1.当k≥2时,D+1（Ts,t）=1,且D+k（Ts,t）=2.