论文摘要
在组合最优化中,装填与覆盖占据一个非常重要的位置.给定一个图,一组边不交的集合称为匹配,一组与图中所有边都关联的顶点的集合称为顶点覆盖.通过这两个概念,两个重要的最优化问题—最大匹配问题（P类问题）和最小顶点覆盖问题（NP-难问题）—对组合最优化的发展起到了巨大的推动作用.经典的K¨onig定理断言,在二部图中,匹配中边的最大数目等于顶点覆盖中顶点的最小数目.本文考虑K¨onig定理的推广形式,探求边装填和带权重的顶点覆盖的关系及在特殊图论结构中的多项式时间算法设计和复杂性分析,刻画使得最大最小关系成立的图论结构.带权重的顶点覆盖问题是经典的NP-难问题,本文通过引入边覆盖的概念,对带权重的顶点覆盖问题提供下界.推广了K¨onig定理,得到了在二部图中,对任意的正整数权重函数,最大边装填中边的数目等于最小顶点覆盖中顶点权重之和.并据此设计了多项式时间算法精确求解了二部图上的最大边装填问题和最小带权重顶点覆盖问题.最后,本文刻画了对任意正整数函数,上述两个最优化问题的最优值刚好取等号的图论结构.本文的结论为一般的装填与覆盖问题提供了新思路,有助于类似问题的算法设计,结构刻画和最大最小关系证明.
论文目录
文章来源
类型: 硕士论文
作者: 张宇姣
导师: 陈智斌
关键词: 定理,二部图,边装填与顶点覆盖,多项式时间算法,最大最小关系
来源: 昆明理工大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 昆明理工大学
分类号: O157.5
DOI: 10.27200/d.cnki.gkmlu.2019.000398
总页数: 46
文件大小: 3374K
下载量: 9
相关论文文献
- [1].一种增量式约简方法求解最小顶点覆盖问题[J]. 计算机应用研究 2018(12)
- [2].3度图的最小顶点覆盖问题的多项式时间算法[J]. 数学理论与应用 2014(03)
- [3].化学反应优化算法求解最小顶点覆盖问题[J]. 小型微型计算机系统 2015(02)
- [4].一种求解平面图的最小顶点覆盖算法[J]. 计算机系统应用 2010(09)
- [5].图的最小顶点覆盖问题的链置换模型[J]. 佳木斯大学学报(自然科学版) 2018(02)
- [6].奖励收集顶点覆盖问题的一个2-近似算法[J]. 北京化工大学学报(自然科学版) 2014(02)
- [7].树上限制性k-node multi-multiway cut 问题的近似算法[J]. 洛阳理工学院学报(自然科学版) 2020(03)
- [8].改进的最小顶点覆盖问题的贪婪算法[J]. 内蒙古师范大学学报(自然科学汉文版) 2012(02)
- [9].顶点覆盖问题线性内核算法[J]. 计算机研究与发展 2008(S1)
- [10].加权最小顶点覆盖的加权分治算法[J]. 小型微型计算机系统 2015(05)
- [11].最小顶点覆盖问题的加权分治算法[J]. 运筹与管理 2015(05)
- [12].最小顶点覆盖快速降阶算法[J]. 小型微型计算机系统 2008(07)
- [13].分层算法求解竞赛图上的最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2012(01)
- [14].Series-Parallel图上最小权顶点覆盖3-路问题的有效算法[J]. 北京化工大学学报(自然科学版) 2019(01)
- [15].图顶点覆盖问题决策神经网络模型[J]. 计算机学报 2009(08)
- [16].最少顶点覆盖问题的研究[J]. 中国新通信 2014(13)
- [17].DNA计算图的最小顶点覆盖问题[J]. 襄樊职业技术学院学报 2008(01)
- [18].一种混合化学反应优化算法求解最小顶点覆盖问题[J]. 计算机应用研究 2016(09)
- [19].次模函数近似算法求最小弱顶点覆盖[J]. 北京化工大学学报(自然科学版) 2011(01)
- [20].图的最小顶点覆盖的粘贴DNA计算模型[J]. 首都师范大学学报(自然科学版) 2013(01)
- [21].基于DNA步行者求解最小顶点覆盖问题的计算模型[J]. 广州大学学报(自然科学版) 2020(01)
- [22].单个飞机噪声事件最小顶点覆盖模型的机场噪声监测点分布方法[J]. 噪声与振动控制 2012(03)
- [23].基于DNA自组装模型解决图的最小顶点覆盖问题[J]. 安徽理工大学学报(自然科学版) 2015(03)
- [24].基于邻接矩阵与关联矩阵解决最大匹配等问题[J]. 贵阳学院学报(自然科学版) 2015(02)
- [25].最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用 2011(01)
- [26].基于自组装纳米颗粒探针的最小顶点覆盖问题的DNA计算模型[J]. 长春师范大学学报 2017(12)
- [27].三正则图上的P_3顶点覆盖问题[J]. 杭州电子科技大学学报(自然科学版) 2019(05)
- [28].基于混合优化算法的网络流量有效测量点选择[J]. 计算机应用研究 2009(04)
- [29].模糊环境下的最小权顶点覆盖问题[J]. 计算机应用研究 2012(01)
- [30].粘贴模型在两类特殊问题中的改进算法研究[J]. 计算机科学 2012(S3)
标签：定理论文; 二部图论文; 边装填与顶点覆盖论文; 多项式时间算法论文; 最大最小关系论文;