首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到15条相似文献,搜索用时 31 毫秒
1.
导出匹配可扩偶图的度条件   总被引:3,自引:0,他引:3  
原晋江  刘岩 《河南科学》1999,17(1):7-12
称简单图G为导出匹配可扩图,若G的任一导出匹配均含于G的完美匹配中。本文给出了导出匹配的可扩偶图的一些度条件。  相似文献   

2.
称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.  相似文献   

3.
图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性.  相似文献   

4.
循环图C_(2n)(1,3)的2-偶匹配可扩性   总被引:1,自引:0,他引:1  
惠志昊  李建民 《河南科学》2010,28(10):1230-1232
设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.  相似文献   

5.
从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图.  相似文献   

6.
设G是含有完美匹配的简单图.称G是偶匹配可扩的,如果G中导出子图是偶图的匹配M都可以扩充为G的完美匹配.研究了在偶匹配可扩图中删去两个顶点后该图的性质.这些性质对于偶匹配可扩图的进一步研究会有帮助.  相似文献   

7.
闫运生 《河南科学》2011,29(2):139-140
k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件.  相似文献   

8.
简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u=u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.  相似文献   

9.
称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V(M)]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM(G),我们证明了Cn×P2是2-偶匹配可扩的。  相似文献   

10.
本文讨论了n-可扩偶图的一个极值问题,证明了任意具有p≥2(n+1)个顶点、q条边的有完美匹配的偶图是n-可扩的充分条件是q≥p/2(p/2-1)+n+1。  相似文献   

11.
研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的.  相似文献   

12.
直径为2的无爪图的导出匹配可扩性   总被引:1,自引:0,他引:1  
如果简单图G的每一个导出匹配都包含在它的一个完美匹配中,称图G是导出匹配可扩的,简称为IM-可扩的。研究了直径为2的无爪图的导出匹配性,证明了一个直径为2的无爪图G是IM-可扩的充分必要条件是:对任意满足|M|≤3的导出匹配M,G—V(M)没有奇分支。因而,直径为2的无爪图的IM-可扩性问题是多项式可解的。  相似文献   

13.
研究直径是2的图和直径是3的树的生成母图的导出匹配可扩性; 给出了一类导出匹配可扩的拟轮图, 并研究了直径是3的树加边的导出匹配可扩性.  相似文献   

14.
设G是一个连通二分图,G=(X,Y;E),本文主要证明了当|X|=|Y|,若δ(G)≥2n+1(1≤n≤|X|2,n∈N),且对G的任两个距离3的顶点u,v有d(u)+d(v)≥|X|+2n时,G是2n-可扩充的  相似文献   

15.
建立了二部图C=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到0(max(|V|,|E|,m|E|)).  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号