论文摘要
G=(V,E)是一个以V为点集和E为边集的图.子集D(?)E是一个全边控制集,如果G中每一条边至少与D中的一条边相邻.全边控制集问题是找到G的一个最小全边控制集.图G的最小全边控制集的边数称为全边控制数,记做γt’(G).对于一个图G,在移除v之后如果连通分支的个数增加,则点v是一个割点.一个图的块是这个图的一个不含割点的极大的连通子图.若图中的块要么为一个圈要么为一条边,并且两个块的交点为空或是一个割点,则这个图称为仙人掌图.同样,如果图中的块要么是一条边要么是一个团,则称为块图.本论文从算法的角度研究了图的全边控制集问题,为了研究仙人掌图和块图上的全边控制问题,首先用标号法给出了树上的算法,接着通过树的算法给出了仙人掌图上的线性时间算法.尽管块图与仙人掌图较为相似但是解决方法相差很大.因此本文接着给出了块图上的全边控制问题的线性时间算法.
论文目录
文章来源
类型: 硕士论文
作者: 杨宇
导师: 徐守军
关键词: 全边控制问题,割点,线性算法,仙人掌图,块图
来源: 兰州大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 兰州大学
分类号: O157.5
总页数: 69
文件大小: 1556K
下载量: 11
相关论文文献
- [1].关于企业内部会计控制问题的分析[J]. 企业导报 2014(24)
- [2].高职英语有效教学的策略研究[J]. 散文百家(新语文活页) 2016(09)
- [3].让课堂提问更有效[J]. 探秘(科学课) 2011(05)
- [4].关于企业内部会计控制问题探讨[J]. 中国乡镇企业会计 2019(11)
- [5].科技企业成本管理及控制问题研究[J]. 财会学习 2020(08)
- [6].3D打印技术过程控制问题研究进展[J]. 信息记录材料 2020(01)
- [7].邮政企业内部会计控制问题及解决策略[J]. 大众投资指南 2018(07)
- [8].高校内部会计控制问题探讨[J]. 智富时代 2015(08)
- [9].建筑工程造价的动态管理及控制问题[J]. 建材与装饰 2020(18)
- [10].电力企业内部会计控制问题研究[J]. 财会学习 2016(23)
- [11].企业管理费用控制问题研究[J]. 大众投资指南 2020(22)
- [12].从网络“恶搞”现象谈舆论控制[J]. 才智 2014(01)
- [13].公路财务管理和财务控制问题研究[J]. 时代金融 2016(23)
- [14].煤炭企业内部会计控制问题与对策分析[J]. 现代工业经济和信息化 2014(18)
- [15].关于小型企业内部会计控制问题探讨[J]. 商 2015(37)
- [16].船舶制造企业生产管理控制问题的探讨[J]. 科技创新导报 2013(18)
- [17].探究建筑工程经济预算与成本的控制问题[J]. 营销界 2020(04)
- [18].控制问题与道家思想——“自然”三义及演变[J]. 人文杂志 2019(08)
- [19].探究建筑工程经济预算与成本的控制问题[J]. 科技经济导刊 2016(07)
- [20].财务信息中的内部会计控制问题探讨[J]. 新闻世界 2012(12)
- [21].民用建筑工程室内环境污染控制问题研究[J]. 中国西部科技 2009(14)
- [22].网络环境下内部会计控制问题探讨[J]. 现代企业 2017(05)
- [23].事业单位财务控制问题与措施[J]. 现代商业 2017(16)
- [24].关于小型企业内部会计控制问题探讨[J]. 经贸实践 2017(12)
- [25].中小企业的内部会计控制问题及对策研究[J]. 品牌 2014(11)
- [26].对企业的财务控制问题探讨[J]. 中国城市经济 2011(09)
- [27].关于小型企业内部会计控制问题探讨[J]. 现代经济信息 2016(21)
- [28].基于电力企业内部会计控制问题研究[J]. 财经界(学术版) 2014(35)
- [29].应用线性矩阵不等式解决时滞系统控制问题[J]. 计算机与数字工程 2014(03)
- [30].新型农村合作医疗基金监管及费用控制问题的探讨[J]. 才智 2012(08)