共查询到20条相似文献,搜索用时 15 毫秒
1.
导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性 总被引:8,自引:0,他引:8
图G的一个匹配M是导出的,若M是图G的一个导出子图。图G是导邮匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得M≥r”是NP-完全的。⑵对直径为2的图以及直径为3的偶图,问题“确定一个给定图是否为导出匹配可扩的”是CO-NP完全的;而对完全多部图而言,问题“ 相似文献
2.
LU Xiao-xu PEI Ming YAO Wei-li ZHOU Ju.Department of Mathematics Zhengzhou University Zhengzhou China .College of Mathematics Information Science Henan University Kaifeng China 《数学季刊》2004,19(1):95-100
An induced matching M in a graph G is a matching such that V(M) induces a 1-regular subgraph of G. The induced matching number of a graph G, denoted by I M(G), is the maximum number r such that G has an induced matching of r edges. Induced matching number of Pm×Pn is investigated in this paper. The main results are as follows:(1) If at least one of m and n is even, then IM(Pm×Pn=[(mn)/4].(2) If m is odd, then 相似文献
3.
给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的. 相似文献
4.
5.
6.
7.
8.
对一个图G,设μ(G,x)表示它的匹配多项式,M(G,x)表示μ(G,x)的最大实数根.令Г_1={G|M(G,x)<2}和Г2={G|M(G,x)≤2}.给出了Г_i(i=1,2)中的两个图G和H匹配等价的充要条件. 相似文献
9.
证明了若M(G)为图G的匹配多面体,M1,M2为M(G)的两个距离为d的顶点,则M1,M2间有d条内部不相交的最短路. 相似文献
10.
Let G be a graph that admits a perfect matching M.A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G.The cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.In this paper,by applying the Ztransformation graph(resonance graph)we show that for any polyomino with perfect matchings and any even polygonal chain,their forcing spectra are integral intervals.Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks.Forcing spectra of two extremal chains are determined. 相似文献
11.
1.IntroductionIn[1],Alavietal.gavethefollowingdecompositionconjecture.Conjecture.LetGbeagraphwith("1')edges.ThentheedgesetofGcanbedecomposedintonsetsgeneratinggraphsGI,G2,'IG.suchthatIE(Gi)I=i(fori=1,2,',n)andGiisisomorphictoasubgraphofGi 1fori=1,2,'.)n--1.AgraphGthatcanbedecomposedasdescribedinConjecturewillbesaidtohaveanAscendingSubgraphDecomposition(AlsoabbreviatedasASD).ThesubgraphsGIIG2,',G.aresaidtobemembersofsuchadecomposition.Furthermore,ifeachGiisastar(matching,pat… 相似文献
12.
13.
A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable. 相似文献
14.
INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS 总被引:3,自引:0,他引:3
原晋江 《数学物理学报(B辑英文版)》2006,26(4):577-584
It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical. 相似文献
15.
双输人匹配排队系统是通常排队系统的一种推广.本文对该系统考察了L2-策略休假和服务台可修的两个重要因素.其中假定系统有两个不同的Poisson输入,两类顾客按1:1作成一批进行服务,服务台的寿命服从指数分布,服务时间,修理时间和休假时间都服从一般连续型分布,利用向量马氏过程方法,得到了该排队系统的一些重要的稳态排队论指标和可靠性指标. 相似文献
16.
Z. I. Borevich 《Mathematical Notes》1969,6(2):567-569
Let K be a field of nonzero characteristic p2, let G be a finite p-group, and let M be a nondegenerate finite-dimensional symplectic space over K with the matching structure of a Gmodule. It is proven that if M is a free K [G]-module then there exists in M a normal basis with a canonical Gram matrix.Translated from Matematicheskie Zametki, Vol. 6, No. 2, pp. 181–185, August, 1969. 相似文献
17.
In solving discrete time queueing models by numerical techniques, the computational requirements (computer memory and time) are a practical limitation and are particularly dependent on the number of discrete time intervals required in the discrete distribution chosen to match the general service distribution. This paper shows that the minimum number of points required for matching to the first two moments depends on the size of the discrete interval relative to the mean and also on the coefficient of variation. Equations and graphs are provided that will enable the OR practitioner to select the discrete distribution to be used as an approximation. Additionally, it is concluded that discrete time modelling, using these approximations to model service time, now provides a practical means to model both steady-state measures and transient behaviour of M/G/c, M(t)/G/c and M(t)/G/c(t) queueing systems on a personal computer. 相似文献
18.
Groupoid的诱导表示 总被引:1,自引:1,他引:0
设G为第二可数局部紧有Haar系的Groupoid, H为子Groupoid闭于G,则可得Groupoid H\G2,我们证明了C*(H)与C*(H\G2)是Morita等价的,从而回答了[1]中的问题.利用此非本原双模及定义C*(G)到M(C*(H\G2))的映射,得到了由C*(H)到C*(G)的诱导表示.特别在群丛情形,我们定义了C*(H)→M(C*(G))的映射,并具体得到了诱导表示的积分形式的表达式. 相似文献
19.
选择搭配参数a,b,利用权函数方法,可得核为K(m,n)的级数算子T的不等式:||T((a))||p,β(a,b) ≤ M(a,b)||(a)||p,α(a,b),(a) ={am}一般地,M(a,b)并不是T:lap(a,b)→lβp(a,b)的算子范数,针对非齐次核K(m,n)=G(mλ1/nλ2)(λ1λ2>0)... 相似文献
20.
小直径图的导出匹配覆盖 总被引:1,自引:1,他引:0
设G是一个图,而M1,M2,…,Mk是G的k个导出匹配.称{M1,M2,…,Mk}是图G的一个k-导出匹配覆盖,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解. 相似文献