| 最小度生成树的最大度算法 |
| |
| 引用本文： | 申玉红. 最小度生成树的最大度算法[J]. 云南民族大学学报(自然科学版), 2013, 22(2): 144-145 |
| |
| 作者姓名： | 申玉红 |
| |
| 作者单位： | 德宏师范高等专科学校数学系,云南芒市,678400 |
| |
| 摘 要： | ![]()
最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.
|
| 关 键 词： | 最小度生成树 近似算法 最大度 破圈 |
Maximum-degree algorithm for the minimum-degree spanning tree problem |
| |
| SHEN Yu-hong. Maximum-degree algorithm for the minimum-degree spanning tree problem[J]. Journal of Yunnan Nationalities University:Natural Sciences Edition, 2013, 22(2): 144-145 |
| |
| Authors: | SHEN Yu-hong |
| |
| Affiliation: | SHEN Yu-hong(Department of Mathematics,Dehong Teachers College,Mangshi 678400,China) |
| |
| Abstract: | ![]()
|
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
