二)、 图的宽直径相关概念 1、问题背景 分析评价互联网络的性能有多个指标，如网络的开销 (通信与材料开销)，网络的容错性（连通性），网络中信息传 递的传输延迟等。 所谓传输延迟，又称为时间延迟，是指信息从源传到 目的地所需要的时间。 如何度量网络的传输延迟？ 信息从源到目的地需要经过若干中间站存储和转发。 因此，信息传输延迟可以用图的顶点间距离来度量。当然， 每条边的长度可以定义为1
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 11 (二)、图的宽直径相关概念 1、问题背景 分析评价互联网络的性能有多个指标，如网络的开销 (通信与材料开销), 网络的容错性(连通性), 网络中信息传 递的传输延迟等。 所谓传输延迟，又称为时间延迟，是指信息从源传到 目的地所需要的时间。 如何度量网络的传输延迟？ 信息从源到目的地需要经过若干中间站存储和转发。 因此，信息传输延迟可以用图的顶点间距离来度量。当然， 每条边的长度可以定义为1
于是，网络的最大通信延迟可以通过图的直径来度量。 图的直径定义为： d(G)=max{d(u,v)u,vEV(G) 例如：dPn)=n-1;d(Cn)=n/2];d(K)=1。 在信息的单路径传输中，分析通信延迟，只需要考虑 网络的直径即可。图论工作者、计算机、通信领域研究者 通过研究，已经确定了若干典型网络的直径和一些图的直 径的界。 定理1设G是强连通有向图.如果它的阶m≥2且最大度 为△，则： =n-1,若△=1 d(G ≥1og(n(△-1)+1)-1，若△≥2 2
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 于是，网络的最大通信延迟可以通过图的直径来度量。 图的直径定义为： d G d u v u v V G ( ) max ( , ) , ( ) = 在信息的单路径传输中，分析通信延迟，只需要考虑 网络的直径即可。图论工作者、计算机、通信领域研究者 通过研究，已经确定了若干典型网络的直径和一些图的直 径的界。 例如：d(Pn )=n-1 ; d(Cn )=[n/2]; d(Kn )=1。 定理1 设G是强连通有向图.如果它的阶n≧2且最大度 为Δ，则： 1, 1 ( ) log ( ( 1) 1) 1, 2 n d G n = − = − + − 若 若