(二)、图的宽直径相关概念 1、问题背景 分析评价互联网络的性能有多个指标，如网络的开销 (通信与材料开销)，网络的容错性（连通性），网络中信息传 递的传输延迟等。 所谓传输延迟，又称为时间延迟，是指信息从源传到 目的地所需要的时间。 如何度量网络的传输延迟？ 信息从源到目的地需要经过若干中间站存储和转发。 因此，信息传输延迟可以用图的顶点间距离来度量。当然， 每条边的长度可以定义为1. 12
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 (二)、图的宽直径相关概念 1、问题背景 分析评价互联网络的性能有多个指标，如网络的开销 (通信与材料开销), 网络的容错性(连通性), 网络中信息传 递的传输延迟等。 所谓传输延迟，又称为时间延迟，是指信息从源传到 目的地所需要的时间。 如何度量网络的传输延迟？ 信息从源到目的地需要经过若干中间站存储和转发。 因此，信息传输延迟可以用图的顶点间距离来度量。当然， 每条边的长度可以定义为1
于是，网络的最大通信延迟可以通过图的直径来度量。 图的直径定义为： d(G)=max{d(u,v)u,vEV(G) 在信息的单路径传输中，分析通信延迟，只需要考虑 网络的直径即可。 直径虽然能够刻画网络的通信延迟，但毕竟是在最坏 情形下的通信延迟，而网络中大距离点对并不多，所以用 直径对信息传输延迟进行描述，还有点不精细。于是，有 如下平均距离的概念：
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 于是，网络的最大通信延迟可以通过图的直径来度量。 图的直径定义为： dG duv uv VG ( ) max ( , ) , ( ) 在信息的单路径传输中，分析通信延迟，只需要考虑 网络的直径即可。 直径虽然能够刻画网络的通信延迟，但毕竟是在最坏 情形下的通信延迟，而网络中大距离点对并不多，所以用 直径对信息传输延迟进行描述，还有点不精细。于是，有 如下平均距离的概念：