| 寻找无向图中全部生成树的复合支路和网络撕裂技术 |
| |
| 引用本文： | 李彦,尹宗谋. 寻找无向图中全部生成树的复合支路和网络撕裂技术[J]. 海军工程大学学报, 2004, 16(5): 74-76 |
| |
| 作者姓名： | 李彦 尹宗谋 |
| |
| 作者单位： | 空军工程大学,电讯工程学院,陕西,西安,710077 |
| |
| 基金项目： | 空军工程大学学术基金资助项目(2002X07) |
| |
| 摘 要： | 将复合支路和网络撕裂技术用于寻找无向图中全部生成树的算法.给出复合支路的概念、表示方法和运算规则,以及由各个子图的全部生成树得到原图的全部生成树的方法.在图的分解和找树过程中,可以采用并行算法,从而降低了找树算法的复杂性.
|
| 关 键 词： | 无向图 生成树 复合支路 网络撕裂 复杂性 并行算法 |
| 文章编号： | 1009-3486(2004)05-0074-03 |
| 修稿时间： | 2004-05-12 |
Techniques by compound branch and network ripping to find out all spanning trees of an undirected graph |
| |
| LI Yan,YIN Zong-mou. Techniques by compound branch and network ripping to find out all spanning trees of an undirected graph[J]. Journal of Naval University of Engineering, 2004, 16(5): 74-76 |
| |
| Authors: | LI Yan YIN Zong-mou |
| |
| Abstract: | The techniques of compoundbranch and network ripping are employed to find out all spanning trees of an undirected graph. The concept, expression and operation rules ofcompound branches are given, and the algorithm to obtain all spanning trees of a graph from those ripped sub-graphs is presented. Because of making use of some parallel algorithms, the computing complexity is reduced. |
| |
| Keywords: | undirected graph spanning trees composite edges network ripping complexity parallel algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
