| 切比雪夫多项式与循环图中生成树的个数 |
| |
| 引用本文： | 卢鹏丽.切比雪夫多项式与循环图中生成树的个数[J].兰州大学学报(自然科学版),2007,43(3):114-117. |
| |
| 作者姓名： | 卢鹏丽 |
| |
| 作者单位： | 兰州理工大学,计算机与通信学院,甘肃,兰州,730050 |
| |
| 摘 要： | 生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性.
|
| 关 键 词： | 矩阵树定理 生成树 循环图 Chebyshev多项式 |
| 文章编号： | 0455-2059（2007）03-0114-04 |
| 修稿时间： | 2006-04-242006-10-30 |
Chebyshev polynomials and formulas for a number of spanning trees in circulant graphs |
| |
| LU Peng-li.Chebyshev polynomials and formulas for a number of spanning trees in circulant graphs[J].Journal of Lanzhou University(Natural Science),2007,43(3):114-117. |
| |
| Authors: | LU Peng-li |
| |
| Institution: | School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China |
| |
| Abstract: | The number of spanning trees in a graph (network) is an important, well-studied quantity. Through the use of the properties of Chebyshev polynomials, simple and running-in-linear-time methods to count the spanning trees for circulant graphs were given, and asymptotic properties were discussed. |
| |
| Keywords: | matrix tree theorem spanning tree circulant graph Chebyshev polynomial |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
