基于网络拓扑图的树的代数连通度

Algebraic connectivity of trees based on network topology

代数图谱理论方法在网络设计中发挥重要作用。网络拓扑图的Laplacian矩阵的谱与网络的同步能力有关,代数连通度就是一个刻画同步能力的重要参数。采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论:当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少。进一步地,讨论了树的代数连通度的上界和下界。

Algebraic graph theory methods play an important role in the network design.Spectrum of Laplacian matrix isassociated with the synchronous ability of network.The algebraic connectivity is a depict important parameter of synchronousability.In this paper,using a grafting method,it discusses the relationship between algebraic connectivity and diameter ofa tree.For a special class of trees,the algebraic connectivity of the tree with a fixed number of vertices,is decreasingalong with the increase of diameter.Moreover,using the Cauchy-Schwarz inequality as a guide,it also obtains bounds forthe algebraic connectivity of a tree.