共查询到19条相似文献,搜索用时 46 毫秒
1.
求解单圈多部图的匹配算法 总被引:4,自引:0,他引:4
给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。 相似文献
2.
建立了二部图C=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到0(max(|V|,|E|,m|E|)). 相似文献
3.
无向简单图G的亏度(deficiency)是未被最大匹配所覆盖的顶点数;一个二部图G(A,B)具有正盈量(posidve surplus)(对A而言)当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数。对具有正盈量的二部图,刻画了其当亏度def(G)给定时达到最大匹配数下界的二部图,从而验证了此类二部图最大匹配数下界的紧性。 相似文献
4.
文章就三部图的匹配问题进行了研究,描述了K3 匹配的定义,提出2-匹配的概念,给出三部图存在K3 匹配的充要条件及有关三部图的2-匹配的性质,为解决复杂的指派问题奠定了一定的理论基础。 相似文献
5.
定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——"表单作业法". 相似文献
6.
k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件. 相似文献
7.
称图G的一个匹配M是导出的,如果M是由M所覆盖的顶点导出的子图的边集,分别给出二部图的一个匹配是导匹配的条件及存在一个最大匹配是导出匹配的条件。 相似文献
8.
求一个简单图的最大匹配与完美匹配问题在经济生产中有着重要的实际意义。将求二分图的完美匹配转化为简化邻接矩阵问题来解决,将一般简单图的最大匹配问题转化为关联矩阵问题或求对偶图的邻接矩阵中阶最大主子式所在的行(列)的序号集问题,这不仅使矩阵工具在图论中得到了充分运用,而且这种方法用起来方便,又便于计算机处理。 相似文献
9.
10.
11.
郭廷花 《太原师范学院学报(自然科学版)》2014,(2):26-28
提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向. 相似文献
12.
图的一个邻接对集是指由其互不相交的相邻边对构成的边的子集,且去掉这些相邻边对后,所得之图是连通的.本文提供了求最大邻接对集的一个有效算法,并指出此算法可以求图的最大亏格 相似文献
13.
一种改进的增字最大匹配算法 总被引:1,自引:0,他引:1
汉语自动分词技术是中文信息处理的关键技术,目前已经成为中文信息处理的瓶颈。介绍了目前几种常用的自动分词算法,在对各种分词算法进行研究的基础上,对现有的增字最大匹配法进行了进一步的改进,更加充分的体现了最大匹配法中的“长词优先”的原则,使分词系统在自动分词阶段有比目前的增字最大匹配法更好的效果。 相似文献
14.
15.
赵彤 《安庆师范学院学报(自然科学版)》2003,9(4):39-40
Hoffman在1998年解决了关于多重完全图的四顶点连通图的图设计问题。本文对其结果作了推广,给出了多重完全多部图的由三角形附带一条边所构成的简单图的图设计存在的充分和必要条件。 相似文献
16.
针对大多数谱方法不能够较好地处理不同大小点集匹配的问题,提出了一种基于线图Q-谱的点模式匹配算法.首先,对相关点集构造赋权完全图,再对每个点利用与其关联的前k条最短边来构造线图;然后,根据线图构造无符号Laplacian矩阵,对其进行谱分解,并利用谱分解所获得的特征值(Q-谱)来表示点的特征,通过这些特征计算点之间的匹... 相似文献
17.
基于网络最大流的立体匹配算法 总被引:5,自引:0,他引:5
为得到立体图像对的全局最优匹配,将视差搜索范围离散化,与图像坐标一起构成三维空间网络。恰当定义网络各边的容量,使之兼顾立体匹配的相容性和光滑性约束,将立体匹配转化为网络优化问题。通过求解网络的最大流和最小切割,获得全局最优的视差分布数据。实验表明,算法生成的视差数据不仅连续稠密而且保留了细节信息。 相似文献
18.
λKn(g)是一个λ重完全n部图,G为一个不带孤立点的简单图.一个(λKn(g),G)-设计是将λKn(g)划分成边互不相交的子图,使得每一个子图都和G同构.对一个五点六边图G的λ重多部图设计的存在性问题进行了研究,证明了(λKn(g),G)-设计存在的充要条件是λn(n-1)g2≡0(mod12),n≥3且ng≥5. 相似文献