Harary图的偶匹配可扩性 被引量：6

1

作者 李建民 惠志昊 《河南大学学报（自然科学版）》 CAS 北大核心 2010年第2期127-129,共3页

对Harary图的偶匹配可扩性进行了研究,得到结论:对于任意的n>1,仅当n=2,3时H3,2n是BM可扩图;对于任意的n(n≥3),H4,2n均不是BM可扩图;对于任意的n(n≥3),当n=3,4时,H5,2n是BM-可扩图;当n≥5时H5,2n不是BM可扩图;对于任意的n(n>3),... 对Harary图的偶匹配可扩性进行了研究,得到结论:对于任意的n>1,仅当n=2,3时H3,2n是BM可扩图;对于任意的n(n≥3),H4,2n均不是BM可扩图;对于任意的n(n≥3),当n=3,4时,H5,2n是BM-可扩图;当n≥5时H5,2n不是BM可扩图;对于任意的n(n>3),r≥6时,Hr,2n是BM-可扩图等等. 展开更多

关键词 HARARY图 完美匹配 偶匹配 偶匹配可扩图

下载PDF 职称材料

哈林图的偶匹配可扩性(英文) 被引量：6

2

作者 惠志昊 赵飚 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2009年第5期493-496,共4页

称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V(M)]是偶图.称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中.本文的主要结果是:哈林图H=(T∪C)是偶匹配可扩的当且仅当它的特征树T同构于K... 称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V(M)]是偶图.称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中.本文的主要结果是:哈林图H=(T∪C)是偶匹配可扩的当且仅当它的特征树T同构于K1,3、K1,5或者K1,7. 展开更多

关键词 偶匹配 偶匹配可扩的 哈林图

下载PDF 职称材料

循环图C_(2n)(1,(2n+1)/3)的匹配可扩性 被引量：3

3

作者 惠志昊 张厚超 赵飚 《数学的实践与认识》 北大核心 2015年第23期300-304,共5页

称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.根据循环图的性质研究了图C_(2n)(1,(2n+1)/3)的匹配可扩性,证明了对于任意的n(n≥4),C_(2n)(1,(2n+1)/3)是3-偶匹配可扩的.

关键词 完美匹配 偶匹配可扩的 k-偶匹配可扩的 循环图

原文传递

C_n×P_2的2-偶匹配可扩性(英文)

4

作者 李建民 惠志昊 《科技信息》 2009年第5期224-225,共2页

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

关键词 偶匹配 偶匹配可扩的 n-偶匹配可扩的

下载PDF 职称材料

偶匹配可扩性的极图问题(英文) 被引量：1

5

作者 王秀梅 尚卫苹 林诒勋 《运筹学学报》 CSCD 2010年第1期23-30,共8页

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.

关键词 运筹学 图论 匹配 偶匹配 偶匹配可扩图

下载PDF 职称材料

书本图的偶匹配可扩性(英文) 被引量：1

6

作者 郭梦夏 惠志昊 《计算机与数字工程》 2013年第3期346-347,398,共3页

该文得出的主要结论是:书本图Bm是偶匹配可扩的当且仅当书本图Bm同构于B1或者B2.并且书本图Bm是基本的。

关键词 偶匹配 偶匹配可扩性 书本图

下载PDF 职称材料

关于偶匹配可扩图中删去两个点(英文)

7

作者 王秀梅 董云达 林诒勋 《河南科学》 2007年第3期361-363,共3页

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

关键词 匹配 偶匹配 偶匹配可扩

下载PDF 职称材料

蛛网图的偶匹配可扩性(英文)

8

作者 郭梦夏 邓天炎 金剑行 《广西师范学院学报（自然科学版）》 2012年第4期21-24,共4页

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

关键词 偶匹配 偶匹配可扩性 蛛网图

下载PDF 职称材料

无爪双临界偶匹配可扩图的结构(英文)

9

作者 惠志昊 赵飚 《科技信息》 2008年第6期140-141,共2页

图G是有完美匹配的简单连通图.称图G是偶匹配可扩的,是指G的每一个偶匹配都可以扩充成为G的一个完美匹配.在本章中,我们得到若干无爪双临界偶匹配可扩图的结构性质。

关键词 偶匹配 偶匹配可扩的 双临界

下载PDF 职称材料

3度循环图的偶匹配可扩性

10

作者 惠志昊 《曲阜师范大学学报（自然科学版）》 CAS 2017年第1期26-28,共3页

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,而该文完全刻画了偶数阶3度连通循环图的偶匹配可扩性.

关键词 完美匹配 偶匹配 偶匹配可扩的 循环图

下载PDF 职称材料

偶匹配可扩图的度和连通度条件(英文)

11

作者 张文勇 李晓玲 赵飚 《新疆大学学报（自然科学版）》 CAS 2010年第4期408-412,共5页

称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那... 称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的. 展开更多

关键词 偶匹配可扩图 完美匹配 度和 连通度

下载PDF 职称材料

循环图C_(2n)(1,3)的2-偶匹配可扩性 被引量：7

12

作者 惠志昊 李建民 《河南科学》 2010年第10期1230-1232,共3页

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2... 设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的. 展开更多

关键词 循环图 完美匹配 偶匹配 k-偶匹配可扩图

下载PDF 职称材料

Harary图的k-偶匹配可扩性 被引量：4

13

作者 惠志昊 杨雨 《洛阳师范学院学报》 2011年第8期17-19,共3页

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n... 设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等. 展开更多

关键词 HARARY图 完美匹配 偶匹配 k-偶匹配可扩图

下载PDF 职称材料

几类特殊图的匹配可扩性 被引量：1

14

作者 惠志昊 曹欣杰 《计算机与数字工程》 2013年第12期1889-1890,1955,共3页

如果图G的每一个偶匹配都可以扩充为G的一个完美匹配,则称图G是偶匹配可扩的。论文主要刻画了图Cm×Pn、Pm×Pn和双轮图的匹配可扩性,从而为研究这些图的可扩性奠定了基础。

关键词 匹配 完美匹配 偶匹配 k-偶匹配可扩

下载PDF 职称材料

循环图C_(2n)(1,2n/3)的2-偶匹配可扩性 被引量：2

15

作者 曹欣杰 惠志昊 《计算机与数字工程》 2012年第9期34-35,共2页

文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n>3),C2n(1,2n/3)是2-偶匹配可扩性的。

关键词 完美匹配 偶匹配可扩 k-偶匹配可扩 循环图

下载PDF 职称材料

循环图C_(2n)(1,4)的偶匹配可扩性

16

作者 惠志昊 《平顶山学院学报》 2017年第2期1-2,共2页

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

关键词 完美匹配 偶匹配可扩 k-偶匹配可扩 循环图

下载PDF 职称材料

步长为1和4的循环图的k-偶匹配可扩性

17

作者 惠志昊 《计算机与数字工程》 2017年第11期2097-2098,2196,共3页

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C_(2n)(1,4)的k-偶匹配可扩性。

关键词 完美匹配 偶匹配可扩 k-偶匹配可扩 循环图

下载PDF 职称材料