共查询到19条相似文献,搜索用时 203 毫秒
1.
设G是一个具有二分类(X,Y)的偶图且M是G的一个完美对集。文章证明:G是1_可扩图当且仅当G有如下耳朵分解G=e+P1+P2+…+Pr使得e∈M并且每个Pi是起始和终止边都在E(G)\M中的M_交错路。文章还给出一个有效算法判定一个偶图是否1_可扩图并找出该图的耳朵分解。 相似文献
2.
图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性. 相似文献
3.
循环图C_(2n)(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-偶匹配可扩性的. 相似文献
4.
5.
称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V(M)]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM(G),我们证明了Cn×P2是2-偶匹配可扩的。 相似文献
6.
翟绍辉 《厦门大学学报(自然科学版)》2007,46(4):457-460
如果图G中有n-匹配并且对任意一个n-匹配M,G中都有一个分数完美匹配f使得对于任意e∈M,f(e)=1成立,那么G被称为是分数n-可扩图.马英红等首先引出此概念,并给出分数n-可扩图和极大分数n-可扩图的刻画.本文分别刻画了分数n-可扩二部图和极小分数n-可扩图,研究了k-因子临界图和分数n-可扩图之间的关系并利用图的binding数和最小度给出了分数n-可扩图的两个充分条件. 相似文献
7.
王世英 《山西大学学报(自然科学版)》2002,25(4):295-297
设 G是一个有限的简单连通图及其具有一个最大匹配 M*。 G称为是 n-可扩的 (1≤ n≤ |M*|- 1)如果 G的任一基数为 n的匹配都能扩充到 G的一个最大匹配 .特别地 ,当 G没有完美匹配时 ,我们把 G称为 n-准可扩的 .在这篇文章里 ,我们研究了 n-准可扩图的一些性质 相似文献
8.
徐允庆 《信阳师范学院学报(自然科学版)》1988,(4)
G为连通简单图,A是G的邻接矩阵,ρ(A)是A的谱半径。当G为偶图时,ρ(A)≤e~(1/2)(e是G中边的个数),等号成立当且仪当G为完全偶图;当G为完全多重图即G=K_(m_1,m_2,…,m_n)时,等号成立当且仅当m_1=m_2=…=m_n。 相似文献
9.
研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的. 相似文献
10.
《曲阜师范大学学报》2017,(1)
称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,而该文完全刻画了偶数阶3度连通循环图的偶匹配可扩性. 相似文献
11.
12.
翟绍辉 《厦门理工学院学报》2010,18(1):18-20,23
设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性. 相似文献
13.
设G是一个简单图,任意e∈E(G),定义e=uv在G中的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。 相似文献
14.
15.
设图G=(X,Y,E)是二分图, g,f是定义在V(G)上的正整值函数, 且对任意的x∈V(G)有g(x)<f(x), 证明了: 如果图G是(mg,mf-1)-图, M是G的任一含有m条边的对集, 则存在图G的一个(g,f)-因子F, 使F包含M任意给定的一条边, 并且不包含其他的m-1条边; 二分图G是(2m-1)-边连通的(mf)-图, 则图G有一个f-因子包含任意给定的一条边, 并且不包含任意其他的m-1条边. 相似文献
16.
若图G的每个极小H-覆盖都是它的最小H-覆盖,则称图G为H-等可覆盖的.得出了M2-等可覆盖图的必要条件,并刻画了以下几类特殊M2-等可覆盖图的特征:匹配、路、圈、完全图、完全二部图、轮图和扇图. 相似文献
17.
图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2]. 相似文献
18.
指出一个二分图G称为一个(g,f) 消去的二分图,如果图G的任何边不属于它的一个(g,f) 因子;一个二分图G称为一个(g,f) 2 消去的二分图,如果图G的任何两条边不属于它的一个(g,f) 因子.给出了一个二分图是(g,f) 消去和(g,f) 2 消去的二分图的一个充要条件. 相似文献
19.
设P(G,λ)表示简单图G的色多项式。简单图H称为与G是色等价的(记作H ̄G),如果P(H,λ)=P(G,λ)。简单图类L称为色正规图类,若对任意H,G∈L使H ̄G都有H与G同构。 相似文献