共查询到19条相似文献,搜索用时 78 毫秒
1.
2.
3.
k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件. 相似文献
4.
从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图. 相似文献
5.
设图G是有2n个顶点的简单图,如果删去G的任意k条边后得到的图是导出匹配可扩的,则称G是k-边可删的导出匹配可扩图.给出了4-正则、不包含K1,4作为导出子图、1-边可删的导出匹配可扩图的完全刻画. 相似文献
6.
n-正则(n-2)-边可删的导出匹配可扩图 总被引:1,自引:0,他引:1
设图G是有2n个顶点的简单图,如果对于E(G)的任一满足|F|=k的子集F,G-F均为导出匹配可扩的,则称图G是k-边可删的导出匹配可扩图.证明了n-正则(n-2)-边可删的导出匹配可扩图只有Kn,n,其中n≠4k,k≥3. 相似文献
7.
8.
直径为2的无爪图的导出匹配可扩性 总被引:1,自引:0,他引:1
如果简单图G的每一个导出匹配都包含在它的一个完美匹配中,称图G是导出匹配可扩的,简称为IM-可扩的。研究了直径为2的无爪图的导出匹配性,证明了一个直径为2的无爪图G是IM-可扩的充分必要条件是:对任意满足|M|≤3的导出匹配M,G—V(M)没有奇分支。因而,直径为2的无爪图的IM-可扩性问题是多项式可解的。 相似文献
9.
文章定义了强k-Helly性质,并给出了它的充要条件.根据此充要条件,当k固定时,导出了检验一个超图是否具有强k-Helly性质的多项式算法. 相似文献
10.
称一个简单图G是导出匹配可扩的,缩写为IM-可扩的,如果G的每一个导出匹配都包含在一个完善匹配中,研究导出匹配可扩图的度和条件,主要结果如下:(1)若图G有2n个顶点,且对于G中每一对不相邻的顶点u和v,d(u)+d(v)≥2「4n/3」-1,则G是出匹配可扩的;(2)若G是一有个有2n个顶点的无爪图,且对于G中每一对不相邻的顶点u和v,d(u)+d(v)≥2n+3,则G是导出匹配可扩的。同时,说 相似文献
11.
12.
王世英 《山西大学学报(自然科学版)》2002,25(4):295-297
设 G是一个有限的简单连通图及其具有一个最大匹配 M*。 G称为是 n-可扩的 (1≤ n≤ |M*|- 1)如果 G的任一基数为 n的匹配都能扩充到 G的一个最大匹配 .特别地 ,当 G没有完美匹配时 ,我们把 G称为 n-准可扩的 .在这篇文章里 ,我们研究了 n-准可扩图的一些性质 相似文献
13.
研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的. 相似文献
14.
15.
循环图C2n(1,3)的2-偶匹配可扩性 总被引:1,自引:0,他引:1
设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的. 相似文献
16.
17.
18.
本文采用定性分析和理论计算相结合的方法,预测了我国到本世纪末的煤炭出口总量、流向和流量,测算结果对外贸、煤炭、航运和造船等部门有实际参考价值。 相似文献
19.
实施出口退税通常是一国政府提升本国出口商品竞争能力,扩大出口额的有效手段。从出口退税政策对我国出口贸易增长所发挥的作用进行深入研究,可以看出出口退税与出口额之间的长期均衡关系。以2004年1月新政策的实施为标志,通过实证研究,可以显示出出口退税对出口贸易所产生的深远影响。 相似文献