共查询到20条相似文献,搜索用时 78 毫秒
1.
如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。 相似文献
2.
k-部图G指图的顶点集V(G)被剖分成k个子集,使每一条边所关联的两个顶点不在同一个子集之中.主要研究了完全多部图的导出匹配可扩性,给出了完全多部图是导出匹配可扩图的充要条件. 相似文献
3.
称图G的一个匹配M是导出的,如果M是由M所覆盖的顶点导出的子图的边集,分别给出二部图的一个匹配是导匹配的条件及存在一个最大匹配是导出匹配的条件。 相似文献
4.
称图G的一个匹配M是导出的,如果M是由M所覆盖的顶点导出的子图的边集.分别给出二部图的一个匹配是导出匹配的条件及存在一个最大匹配是导出匹配的条件. 相似文献
5.
从导出匹配可扩图的定义、结构出发,研究了拟轮图的性质, 构造了一类新的导出匹配可扩图Γn. 主要结果如下:(1)判定具有奇数个顶点的图几乎导出匹配可扩性是co-NP-完全的. (2)Γn中的任何一个图均是边数为5n-6的导出匹配可扩的拟轮图. 相似文献
6.
设图G是有2n个顶点的简单图,如果删去G的任意k条边后得到的图是导出匹配可扩的,则称G是k-边可删的导出匹配可扩图.给出了4-正则、不包含K1,4作为导出子图、1-边可删的导出匹配可扩图的完全刻画. 相似文献
7.
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.
研究直径是2的图和直径是3的树的生成母图的导出匹配可扩性; 给出了一类导出匹配可扩的拟轮图, 并研究了直径是3的树加边的导出匹配可扩性. 相似文献
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.
申世昌 《东北师大学报(自然科学版)》2006,38(4):41-44
设G是简单图,用μ(G,x)表示图G的匹配多项式,若μ(G,x)=μ(H,x),则称G与H是匹配等价的,记为H~G.若H~G可导出H G,则称图G是匹配惟一的.在此基础上研究了T形树的匹配惟一性,证明了T(m,m 1,m 2),T(m,m 1,m 3)(m≥1)及补图是匹配惟一的. 相似文献
12.
设图G没有孤立点.图G的匹配覆盖数,记为mc(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{Δ0(G),Δ0(G) 1},其中Δ0(G)是指使得图G的某个顶点有l个一度邻点的l的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法. 相似文献
13.
证明了图族m2P2∪m3P3∪[∪i≥2m2iP2i]∪dD4∪[∪j≥3njCj]∪tT1,2,3∪sT1,2,4匹配唯一。当且仅当dm2=dm3=n3t=n3n5s=n15t=n5n9s=mknk 1=0(k≥2),其中m2,m3,m2i(i≥2),d,nj(j≥3),t,s都是非负整数。 相似文献
14.
魏岭 《青海师范大学学报(自然科学版)》2004,(3):9-10
本文证明了图κK1∪m2P2∪m3P3∪[∪↑i≥2m2ipi]∪dD4∪tT1、2、3∪sT1、2、4匹配唯一当且仅当dm2=dm3=0,其中κ、m2、m3、m2i(i≥2)、d、t、s都是非负整数。 相似文献
15.
16.
图的完美对集计数理论是图论研究的重要内容之一,此问题的研究具有很强的计算机科学、物理学和化学的应用背景,是一个有生机和活力的研究领域,也是快速发展的组合数学理论中许多重要思想的源泉.构造了一类3-正则新图2-3-nC6,用嵌套递推的方法,得到了图2-3-nC6的完美对集数的一个递推关系,再解出这个递推式的通解,从而得到了这个图的完美对集数计算公式.最后又给出这个图完美对集数计算公式的一个组合证明. 相似文献
17.
18.
给出了一个二分图G =(V1 ,V2 ;E)有一个支撑子图包含一个指定长度的圈和一个对集的度条件 .并且证明了若 |V1 |=|V2 |=n =2k ,则G有一个 2 因子恰有一个 8 圈和k 2个 4 圈或恰有k个 4 圈 . 相似文献
19.
龚和林 《上海师范大学学报(自然科学版)》2005,34(2):33-36
设G的色多项式为P(G,λ)=λ^ko(λ-1)^k1…(λ—m 1)^km-1(λ-m)…(λ—n 1),其中,m≤n,且ki=1或2(i=0,1,…,m-1),且k0≤k1≤…≤km-1.本文给出了几类由上述形式色多项式决定的广义树,并证明了{{Kn,Km},{Kr}}是一个完全类当且仅当r=m-1或m. 相似文献
20.
用划分,求和,再递推的方法给出了四类图完美匹配数目的显式表达式.所给方法可以计算出许多二分图所有完美匹配的数目. 相似文献