| 最小度生成树的最大度算法 |
| |
| 引用本文： | 申玉红.最小度生成树的最大度算法[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 |
| |
| Institution: | SHEN Yu-hong(Department of Mathematics,Dehong Teachers College,Mangshi 678400,China) |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
