圖的導(dǎo)出匹配覆蓋.pdf

1、本文所討論的圖均為有限的簡(jiǎn)單圖.對(duì)于任意圖G，V(G)和E(G)分別表示它的頂點(diǎn)集和邊集.對(duì)頂點(diǎn)集X∈V(G)，令EG(X)={uv∈E(G)：u，v∈X}.X的鄰點(diǎn)集NG(X)定義為NG(X)={y∈V(G)\X：存在x∈X使得xy∈E(G)}.X的懸掛鄰集N0(X)定義為N0(X)={y∈NG(X)：d(y)=1}.對(duì)任意頂點(diǎn)v，v的懸掛度定義為d0(v)=|N0(v)|.對(duì)于M∈E(G)，令V(M)={v∈V(G)：存在一個(gè)頂點(diǎn)x

2、∈V(G)使得vs∈M}.如果M∈E(G)，X()V(G)使得X()V(M)，我們稱M覆蓋X.如果M()E(G)，且對(duì)任意不同的邊e，f∈M，V(e)∩V(f)=Φ，則稱M是圖G的一個(gè)匹配.若匹配M滿足V(M)=V(G)，則稱M是圖G的完美匹配.若匹配M滿足EG(V(M))=M，則稱M是圖G的導(dǎo)出匹配. 集合X的一個(gè)k-劃分是指一個(gè)k-元組(X1，X2，…，Xk)使得X1，X2，…，Xk是滿足∪Xi=X的X的互不相交的子集.如果

3、G是有完美匹配的連通圖，假設(shè)(V1，V2，…，Vk)是V(G)的一個(gè)k-劃分.我們說(shuō)(V1，V2，…，Vk)是G的一個(gè)k-導(dǎo)出匹配劃分，如果對(duì)每一個(gè)i(1≤i≤k)而言，G[Vi]是G的一個(gè)1-正則導(dǎo)出子圖.G的導(dǎo)出匹配劃分?jǐn)?shù)定義為使得G有k-導(dǎo)出匹配劃分的最小整數(shù)k，記為imp(G). 設(shè)M1，M2，…，Mk是G的k個(gè)導(dǎo)出匹配，若V(M1)∪…∪V(Mk)=V(G)，則稱{M1，M2，…，Mk}是G的一個(gè)k-導(dǎo)出匹配覆蓋.G的

4、導(dǎo)出匹配覆蓋數(shù)定義為使得G有k-導(dǎo)出匹配覆蓋的最小整數(shù)k，記為imc(G). 如果G是頂點(diǎn)數(shù)至少為3的樹(shù).我們記△0(G)=max{d0(u)：u∈V(G)}，△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.在本文中，我們主要研究了以下兩個(gè)部分：(1)樹(shù)和3-正則無(wú)爪圖的導(dǎo)出匹配覆蓋；(2)圖的導(dǎo)出匹配覆蓋問(wèn)題的計(jì)算復(fù)雜性. 第二章討論了樹(shù)和3-正則無(wú)爪圖的導(dǎo)出匹配覆蓋，主要得到以下結(jié)果

5、：定理1設(shè)G是頂點(diǎn)數(shù)至少為3的樹(shù).則imc(G)∈{*0(G)，△*0(G)+1，△*0(G)+2}，其中△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.進(jìn)一步，如果△*0(G)＞△0(G)，則imc(G)∈{△*0(G)，△*0(G)+1}.定理2設(shè)G是3-正則無(wú)爪圖，則imc(G)∈{2，3}. 第三章研究了圖的導(dǎo)出匹配覆蓋問(wèn)題的計(jì)算復(fù)雜性，主要結(jié)果如下：定理3直徑為6的圖的2-導(dǎo)出匹配覆蓋

6、問(wèn)題是NP-完備的.定理4直徑為2的圖的3-導(dǎo)出匹配覆蓋問(wèn)題是NP-完備的.定理5設(shè)G是直徑為2的圖.令X={x∈V(G)：dG(x)=2}.則imc(G)=2當(dāng)且僅當(dāng)下列兩個(gè)條件之一成立：(1)imp(G)=2；(2)imp(G)≠2，且存在這樣的頂點(diǎn)x∈X使得(G-{x})∪K+E0，記為G1，滿足imp(G1)=2，其中K是空?qǐng)D，|V(K)|=2，K∩V(G)=Φ，E0={(y，z)：y∈NG(x)，z∈K}. 最后還給出