| 步数可变循环图中生成树的计数 |
| |
| 引用本文： | 卢鹏丽. 步数可变循环图中生成树的计数[J]. 甘肃科学学报, 2007, 19(2): 1-4 |
| |
| 作者姓名： | 卢鹏丽 |
| |
| 作者单位： | 兰州理工大学,计算机与通信学院,甘肃,兰州,730050 |
| |
| 摘 要： | 生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.一般的图还无简单有效的算法计算生成树的个数,利用切比雪夫多项式的性质推出了步数可变循环图中生成树计数的在线性时间内即可实现的算法,并应用于具体的图中.
|
| 关 键 词： | 生成树 步数可变的循环图 Chebyshev多项式 |
| 文章编号： | 1004-0366（2007）02-0001-04 |
| 收稿时间： | 2006-04-24 |
| 修稿时间： | 2006-04-24 |
Formulas for the Number of Spanning Trees in Non-fixed Step Circulant Graphs |
| |
| LU Peng-li. Formulas for the Number of Spanning Trees in Non-fixed Step Circulant Graphs[J]. Journal of Gansu Sciences, 2007, 19(2): 1-4 |
| |
| Authors: | LU Peng-li |
| |
| Affiliation: | School of Computer Science and Communications, Lanzhou University of Science and Technology, Lanzhou 730050, China |
| |
| Abstract: | The number of spanning trees in a graph(network) is an important,well-studied quantity.No simple and efficient methods can count the number of spanning trees in general graphs.By means of the properties of Chebyshev polynomials,an algorithm running in linear time is derived for non-fixed step circulant graphs and can be applied to specific graphs. |
| |
| Keywords: | spanning tree non-fixed step circulant graph Chebyshev polynomial |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
