本文所讨论的图均为有限的简单图.对于任意图G，V(G)和E(G)分别表示它的顶点集和边集.对顶点集X∈V(G)，令EG(X)={uv∈E(G)：u，v∈X}.X的邻点集NG(X)定义为NG(X)={y∈V(G)X：存在x∈X使得xy∈E(G)}.X的悬挂邻集N0(X)定义为N0(X)={y∈NG(X)：d(y)=1}.对任意顶点v，v的悬挂度定义为d0(v)=|N0(v)|.对于M∈E(G)，令V(M)={v∈V(G)：存在一个顶点x∈V(G)使得vs∈M}.如果M∈E(G)，X()V(G)使得X()V(M)，我们称M覆盖X.如果M()E(G)，且对任意不同的边e，f∈M，V(e)∩V(f)=Φ，则称M是图G的一个匹配.若匹配M满足V(M)=V(G)，则称M是图G的完美匹配.若匹配M满足EG(V(M))=M，则称M是图G的导出匹配. 集合X的一个k-划分是指一个k-元组(X1，X2，…，Xk)使得X1，X2，…，Xk是满足∪Xi=X的X的互不相交的子集.如果G是有完美匹配的连通图，假设(V1，V2，…，Vk)是V(G)的一个k-划分.我们说(V1，V2，…，Vk)是G的一个k-导出匹配划分，如果对每一个i(1≤i≤k)而言，G[Vi]是G的一个1-正则导出子图.G的导出匹配划分数定义为使得G有k-导出匹配划分的最小整数k，记为imp(G). 设M1，M2，…，Mk是G的k个导出匹配，若V(M1)∪…∪V(Mk)=V(G)，则称{M1，M2，…，Mk}是G的一个k-导出匹配覆盖.G的导出匹配覆盖数定义为使得G有k-导出匹配覆盖的最小整数k，记为imc(G). 如果G是顶点数至少为3的树.我们记△0(G)=max{d0(u)：u∈V(G)}，△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.在本文中，我们主要研究了以下两个部分：(1)树和3-正则无爪图的导出匹配覆盖；(2)图的导出匹配覆盖问题的计算复杂性. 第二章讨论了树和3-正则无爪图的导出匹配覆盖，主要得到以下结果：定理1设G是顶点数至少为3的树.则imc(G)∈{*0(G)，△*0(G)+1，△*0(G)+2}，其中△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.进一步，如果△*0(G)＞△0(G)，则imc(G)∈{△*0(G)，△*0(G)+1}.定理2设G是3-正则无爪图，则imc(G)∈{2，3}. 第三章研究了图的导出匹配覆盖问题的计算复杂性，主要结果如下：定理3直径为6的图的2-导出匹配覆盖问题是NP-完备的.定理4直径为2的图的3-导出匹配覆盖问题是NP-完备的.定理5设G是直径为2的图.令X={x∈V(G)：dG(x)=2}.则imc(G)=2当且仅当下列两个条件之一成立：(1)imp(G)=2；(2)imp(G)≠2，且存在这样的顶点x∈X使得(G-{x})∪K+E0，记为G1，满足imp(G1)=2，其中K是空图，|V(K)|=2，K∩V(G)=Φ，E0={(y，z)：y∈NG(x)，z∈K}. 最后还给出了直径为2的图的2-导出匹配覆盖问题的多项式时间算法.