计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (3): 106-109.DOI: 10.3778/j.issn.1002-8331.1504-0259

• 网络、通信与安全 • 上一篇    下一篇

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

周后卿1,徐幼专2   

  1. 1.湖南邵阳学院 数学系,湖南 邵阳 422000
    2.邵阳广播电视大学,湖南 邵阳 422000
  • 出版日期:2017-02-01 发布日期:2017-05-11

 Algebraic connectivity of trees based on network topology

ZHOU Houqing1,XU Youzhuan2   

  1. 1.Department of Mathematics, Shaoyang University, Shaoyang, Hunan 422000, China
    2.Shaoyang Radio & TV University, Shaoyang, Hunan 422000, China
  • Online:2017-02-01 Published:2017-05-11

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

关键词: 树, 拉普拉斯矩阵, 代数连通度, 直径

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

Key words:  tree, Laplace matrix, algebraic connectivity, diameter