| 引用本文: | 陈庆华.单点次限制的第二棵最小树的简单算法.[J].国防科技大学学报,1983,(3):123-131.[点击复制] |
| Chen Qinghua.Finding the Secnd Spanning Tree with a Fixed Number of Edges at a Vertex[J].Journal of National University of Defense Technology,1983,(3):123-131[点击复制] |
|
| |
|
|
| 本文已被：浏览 4949次 下载 5197次 |
| 单点次限制的第二棵最小树的简单算法 |
| 陈庆华 |
|
()
|
| 摘要: |
| 给定赋权连通图 G=(V，E)，正整数 k，以及特别指定顶点 V0∈V，一棵支撑树 T，满足V0在 T中恰关联k条边，使得T具有尽可能小的权，树T称为具单点次限制的第一棵最小树。求单点次限制的第一棵最小树已经有好的算法，本文给出求具单点次限制的第二棵最小树的简单算法。由于 Matroid 的基也具有本文所用到的关于支撑树的性质，因而本文的结果也无困难地推广到Matroid上去。 |
| 关键词: |
| DOI： |
| 投稿日期：1983-04-21 |
| 基金项目: |
|
| Finding the Secnd Spanning Tree with a Fixed Number of Edges at a Vertex |
| Chen Qinghua |
| Abstract: |
| The minimum Spanning tree problem in which a given vertex is required to have a fixed number of incident edges was solved by F. Glover and D. Klingman. This paper give a simple algorithm finding the second spanning tree with a fixed number of edges at a vertex，and extend this algorithm to finding the second order-constrained base of Matroid. |
| Keywords: |
|
|
