检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

最大匹配图的围长(英文)

运筹学学报 2001年第1期5卷 13-20页

作者：刘岩林诒勋黄玉琴王世英山东大学数学院济南250100 郑州大学系统科学与数学系郑州450052

将一个图的所有最大匹配作为顶点集，称两个最大匹配相邻，若它们之一通过交换一条边得到另一个，由此所得图为该图的最大匹配图．本文研究了最大匹配图的围长，从而给出了最大匹配图是树或完全图的条件．

关键词：最大匹配最大匹配图围长图顶点集树完全图

在线全文

学校读者我要写书评

暂无评论

最大匹配问题的粘贴DNA算法

计算机科学 2013年第12期40卷 127-132,140页

作者：吴雪宋晨阳张楠朱煜陈志华华东理工大学信息科学与工程学院上海200237 上海通用识别技术研究所上海201112

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的... 详细信息

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。

关键词： DNA计算最大匹配粘贴模型

基于图论最大匹配的非Manhattan版面阅读顺序

在线全文

学校读者我要写书评

暂无评论

计算机工程 2006年第2期32卷 32-33,47页

作者：贾娟陈堃銶周东浩北京大学计算机科学技术研究所文字信息处理技术国家重点实验室北京100871 IBM中国有限公司北京100027

非Manhattan版面中,区域形状不规则及空间关系复杂使得确定合乎视觉脉络的无歧义的文字阅读顺序成为排版及版面理解过程中的一个难点。针对此问题,建立了新的版面布局模型,提出了基于图论最大匹配理论的阅读顺序确定算法。已成功运用于... 详细信息

非Manhattan版面中,区域形状不规则及空间关系复杂使得确定合乎视觉脉络的无歧义的文字阅读顺序成为排版及版面理解过程中的一个难点。针对此问题,建立了新的版面布局模型,提出了基于图论最大匹配理论的阅读顺序确定算法。已成功运用于专业中日文排版系统,取得了满意的效果,并对更深入研究文档图像理解具有十分重要的理论和实践意义。

关键词：最大匹配非Manhattan版面阅读顺序空间关系

最大匹配数为|V(G)|+4的Eta图的结构

在线全文

学校读者我要写书评

暂无评论

数学的实践与认识 2019年第9期49卷 138-146页

作者：杨春侠吴丽镐华南理工大学广州学院计算机工程学院广东广州510800

一个奇圈上加两条奇长的悬挂路组成的图形,称为Eta图.从Eta图的构造出发,研究了最大匹配数为|V(G)|+4的Eta图,得到了10种满足条件的结构.

关键词：悬挂路 Eta图最大匹配

在线全文

学校读者我要写书评

暂无评论

最大匹配的路变换图

运筹学学报 2019年第2期23卷 104-112页

作者：刘岩雷梦霞黄晓娴华南师范大学数学科学学院广州510631

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵... 详细信息

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

关键词：最大匹配路变换图因子临界图有正赢量的二部图

在线全文

学校读者我要写书评

暂无评论

最大匹配问题的分子信标计算模型

合肥工业大学学报（自然科学版） 2013年第11期36卷 1400-1403页

作者：杨静殷志祥陈明强黄凯峰安徽理工大学理学院安徽淮南232001 安徽理工大学化学工程学院安徽淮南232001 淮南职业技术学院信息与电气系安徽淮南232001

目前利用DNA计算求解图与组合优化中探索和开发新的分子结构是研究的一个热点,而分子信标具有结构简单、灵敏度高、易于检测及反应迅速等优点。最大匹配问题是一个著名的NP-完全问题,文章利用分子信标给出最大匹配问题的DNA计算模型。... 详细信息

目前利用DNA计算求解图与组合优化中探索和开发新的分子结构是研究的一个热点,而分子信标具有结构简单、灵敏度高、易于检测及反应迅速等优点。最大匹配问题是一个著名的NP-完全问题,文章利用分子信标给出最大匹配问题的DNA计算模型。该模型具有编码简单、耗材低、空间利用率高、操作时间短及易于检测等特点,同时拓展了DNA计算解决问题的方法和应用领域。

关键词： DNA计算分子信标最大匹配 NP-完全问题分子信标探针

在线全文

学校读者我要写书评

暂无评论

基于二部图最大匹配的动态负载均衡算法

高技术通讯 2020年第8期30卷 798-804页

作者：周磊孟利民周立鹏蒋维浙江工业大学信息工程学院杭州310023 浙江树人大学信息科技学院杭州310015

负载均衡算法是服务器集群的核心技术之一,其关键在于如何将任务均衡地分配至各个服务器,为此提出了一种基于二部图最大匹配的动态负载均衡算法。该算法以服务器所执行任务的任务量与实际完成时间的比值作为服务器的负载指标,并将负载... 详细信息

负载均衡算法是服务器集群的核心技术之一,其关键在于如何将任务均衡地分配至各个服务器,为此提出了一种基于二部图最大匹配的动态负载均衡算法。该算法以服务器所执行任务的任务量与实际完成时间的比值作为服务器的负载指标,并将负载指标实时反馈给集群系统中的管理服务器。根据待分配任务的任务量和期望完成时间以及各个服务器的负载指标,构建服务器与任务的二部图,并采用Edmonds的匈牙利算法求解二部图的最大匹配,最后按匹配结果将任务实时发送至对应服务器。实验结果表明,该算法拥有较好的负载均衡效果且更快地完成所有任务。

关键词：动态负载均衡任务分配服务器集群二部图最大匹配

具有|V(G)|+2个最大匹配的因子临界图G

在线全文

学校读者我要写书评

暂无评论

数学物理学报（A辑） 2009年第2期29卷 486-493页

作者：刘岩杨春侠华南师范大学数学科学学院广州510631 广东工业大学华立学院广州510000

在连通图G中,如果对任意的v∈V(G),G-v有完美匹配,则称G是因子临界图.该文刻画了具有|V(G)|+2个最大匹配的因子临界图.进而,刻画了一些特殊的双因子临界图.

关键词：最大匹配因子临界图双临界图.

在线全文

学校读者我要写书评

暂无评论

最大匹配计数问题与一些特殊图的结构

最大匹配计数问题与一些特殊图的结构

作者：杨春侠华南师范大学

学位级别：硕士

设G是一个简单图，具有顶点集合V(G)和边集合E(G)。在连通图G中，如果对任意的v∈V(G)，G-v有完美匹配，则称G是因子临界图。一个因子临界图有奇数个顶点且最小度不小于二度。如果对于任意的两个顶点x，y∈V(G)，G-x-y都有完美匹配，则... 详细信息

设G是一个简单图，具有顶点集合V(G)和边集合E(G)。在连通图G中，如果对任意的v∈V(G)，G-v有完美匹配，则称G是因子临界图。一个因子临界图有奇数个顶点且最小度不小于二度。如果对于任意的两个顶点x，y∈V(G)，G-x-y都有完美匹配，则称G是二因子临界图。显然G是一个二因子临界图的充分必要条件是(?)v∈V(G)，G-v是一个因子临界图。若图G的任意导出子图都不与K同构，则称G是一个无爪图。一个立方图是一个所有顶点都是三度点的图。图的最大匹配计数和完美匹配计数问题是图论和组合最优化中的一个重要分支，它有着广泛的应用。例如，在化学领域，二部图的完美匹配数是[3，4]中所研究的Kekulé结构计数。但是由[2]知：一般图(甚至二部图)的完美匹配计数问题是NP-困难问题，所以最大匹配的计数问题也是困难的。2005年，刘岩刻画了最大匹配数m(G)=|V(G)|+1的因子临界图的结构，本文的第二章在刘岩老师所做的结果的基础上进一步刻画了最大匹配数m(G)=|V(G)|+2的因子临界图的结构。第三章给出了一类特殊图-不含K-e的无爪立方图的完美匹配数。本文的主要结果如下： Theorem2.10。设G是一个有c个块的因子临界图，则m(G)=|V(G)|+2当且仅当 1、除了一个块H，G的所有其他块是奇圈。其中H是一个eta图E(l，l，l，l)，满足l=2，长度为l的路是G的悬挂路。长度为l的路的两个端点被G的一条长度为2的悬挂路相连。或者H是一个theta图Θ(l，l，l)，满足l=4和d(v)=d(v)=2，此处长度为l的路是uvvvv。或者 2、G中除了两个块H和H之外所有块均是奇圈。H和H分别是theta图Θ(l，l，l)和Θ(l′，l′，l′)，满足l=l′=2，H的长度为l的路和H的长度为l′的路均是G的悬挂路。 Theorem3.2。设G 2-连通且G是一个不含k-e的n阶无爪立方图，则n=6k，k≥1为整数，且G的完美匹配数为2。

关键词：最大匹配因子临界图二因子临界图完美匹配无爪图立方图