给定度序列图的覆盖成本和反向覆盖成本的研究

• 作者: 贾雁宇 李玉瑛 郝艺方
• 来源期刊: 数学的实践与认识
• 关键词: 星型树 度序列 段序列 覆盖成本 反向覆盖成本
• 年，卷（期）: 2022,（1）
• 所属期刊栏目: 研究|Research
• 页码范围: 188-195
• 页数: 8页
• 语种: 中文

摘要

具有n个顶点且度序列为(m,2,…,2,1,…,1)(1的重数为m)的连通图不止一个(这些图均为树),而每个树对应唯一一个段序列(l1,l2,…,lm).通过对任意一树移动最长段的悬挂点到最短段悬挂点的方式得到另一树,比较前后两树的覆盖成本和反向覆盖成本,给出了具有最小覆盖成本和反向覆盖成本的极树,并且进一步给出了取得最小覆盖成本和反向覆盖成本的顶点.