共查询到20条相似文献,搜索用时 0 毫秒
1.
定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——"表单作业法". 相似文献
2.
最大公因数与最小公倍数的矩阵求法 总被引:3,自引:0,他引:3
本文通过讨论,给出一个求两个整数的最大公因数和最小公倍数的矩阵求法。经过整数矩阵的初等变换,可在一个整数矩阵上同时求得(m,n)与[m,n]。这个方法有助于求解整数的标准分解式。 相似文献
3.
4.
王世英 《郑州大学学报(理学版)》2002,34(4):15-18,25
设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配,则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配,并令T=S-V(M)。对连通的非二部的n-可扩图G(n≥2),得到以下结果:(1)若r≤n且|T|≥2,则|V(G)|≥2(n r |T|--1)。(2)若r≤n-2且|T|≥2,则|V(G)|≥2(n r |T|)。(3)若|V(G)|≤4n-2,则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。 相似文献
5.
6.
匹配理论是图论中一个重要的分支,已被广泛地应用于许多领域,如组合优化、线性规划、人工智能和矩阵论等.给出一个求解多部图的最大匹配算法,并用仿真例子说明其实用性和有效性,此算法为解决复杂的指派问题开辟了新途径. 相似文献
7.
陈燕 《南京师大学报(自然科学版)》2000,23(2):21-24
讨论了简单平面三角剖分图中各生成两部子图的最大次的取值范围,否定了郁星星提出的生成两部子图最大次的上界为常数的猜想,并且得到了下面的主要结果。(1)设G是简单平面三角剖分图,当n=3时,a0(G)=1;当n=4时,a0(G)=a1(G)=a2(G)=1;当n≥5时,有2≤a0(G)≤a1(G)≤a2(G)≤「△(G)/」,且下界a0(G)-2能达到。⑵若l是不小于3的整数,则(a)存在简单平面三角 相似文献
8.
在二元多项式矩阵中引入初等行变换的概念,利用分式域和本原多项式的概念讨论了二元多项式最大公因式的求解方法,给出了利用矩阵初等变换求解多个二元多项式最大公因式的一般方法. 相似文献
9.
建立了二部图C=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到0(max(|V|,|E|,m|E|)). 相似文献
10.
设G=(y,E)是n阶简单连通图,D(G)和A(G)分别表示图G的度对角矩阵和邻接矩阵,则L(G)=D(G)-A(G)称为G的拉普拉斯矩阵利用图的度序列,平均二次度和图的公共邻点数结合非负矩阵谱理论给出了L(G)的最大特征值的一些上界. 相似文献
11.
用划分,求和,再递推的方法给出了四类图完美匹配数目的显式表达式.所给方法可以计算出许多二分图所有完美匹配的数目. 相似文献
12.
滕桂兰 《天津大学学报(自然科学与工程技术版)》1997,30(5):631-635
证明了一个n阶非负实矩阵可分解为某些n阶置换矩阵的线性组合的定理,由此得到了k-正则偶图的对集矩阵的分解定理,这些定量衣其证明给出了k-正则偶图的完美匹配的构造方法,并举例说明对集矩阵的分解不是唯一的。 相似文献
13.
二部图匹配强迫数的谱 总被引:1,自引:0,他引:1
王洪伟 《山东大学学报(理学版)》2009,44(12):30-35
改进了Riddle 的尾点法, 得到自然数k属于二部图匹配强迫数谱的必要条件, 给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。 相似文献
14.
林翠琴 《清华大学学报(自然科学版)》1999,39(10):2
完全图Kn 中若存在一族k-匹配,使得Kn 中任一对独立边恰属于λ个k-匹配,则称Kn 存在MATCH(n,k,λ)-设计; 同样定义完全二部图Kn, n的匹配设计。综述研究这两种匹配设计所采用的组合设计和图论方法及作者新近提出的矩阵方法,简述这一课题的研究成果及未解决的问题。 相似文献
15.
无向简单图G的亏度(deficiency)是未被最大匹配所覆盖的顶点数;一个二部图G(A,B)具有正盈量(posidve surplus)(对A而言)当且仅当对A的任何非空集合X所包含的顶点数一定小于其邻集所包含的顶点数。对具有正盈量的二部图,刻画了其当亏度def(G)给定时达到最大匹配数下界的二部图,从而验证了此类二部图最大匹配数下界的紧性。 相似文献
16.
设G是一简单无向图,A(G)为G的邻接矩阵,D(G)为G的顶点度对角矩阵,Q(G)=D(G)—A(G)称为G的拟拉普拉斯矩阵,本文研究Q(G)的永久式,得到perQ(G)的两个表示公式及perQ(G)的一些下界。 相似文献
17.
二分图的Laplace矩阵的最大特征值 总被引:1,自引:0,他引:1
殷剑宏 《合肥工业大学学报(自然科学版)》2004,27(8):952-955
图的Laplace矩阵的谱,在物理、化学和计算机等学科有着广泛应用。但是,求图的Laplace矩阵的谱,是很不容易的。文章通过分析二分图的结构,研究了二分图的Laplace矩阵的特点,利用非负矩阵的经典理论和图论方法,导出了一般二分图的Laplace矩阵的最大特征值的界值。 相似文献
18.
完美匹配树的计数公式 总被引:3,自引:0,他引:3
魏均斌 《华南师范大学学报(自然科学版)》2002,(1):61-63
证明完美匹配树的一些相关性质与定理,并利用Polya计数定理得到了完美匹配树的计数公式。 相似文献
19.
20.
张和平 《兰州大学学报(自然科学版)》1996,32(3):7-11
图的完善匹配或1-因子指覆盖子其所有顶点的独立边集。对含有完善匹配的平面二部图,其所有完美区通过某旋转变换形成层次组织结构。可用有向根树或半格表示。建立了平面二部图的完善匹配集合上新有向根树结构并可通过算法来生成。 相似文献