信息传输延迟与图的直径

摘要

本文主要运用图论的一些知识,解决信息传输延迟与图的直径的关系.通过对强连通有向图D和连通无向图G的分析论证,得出了直径的下界,并且在此基础由局域网推广为广域网,对G为连通无向图时进行推广,通过严格的证明得到了直径的下界,但所得不等式只是一个数学表达式图的直径大小的选择是相对的.如果要求网络中某两点的传输速度快,则直径越小越好;如果从源点发出一个信息要求网络中的客户都能收到,则直径越大越好.这样,图的直径就能直接反映点对点互连网络的传输延迟,在现实生活中具有很广泛的应用.