运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
2期
17-24
,共8页
运筹学%导出匹配%导出匹配覆盖%NP-完备%多项式可解
運籌學%導齣匹配%導齣匹配覆蓋%NP-完備%多項式可解
운주학%도출필배%도출필배복개%NP-완비%다항식가해
Operations research%induced matching%induced matching cover%NP-complete%polynomially solvable
设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-导出匹配覆盖问题多项式可解.
設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-導齣匹配覆蓋問題多項式可解.
설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-도출필배복개문제다항식가해.
Let G be a graph and M1, M2,…, Mk are k induced matchings of G. We say{M1,M2,…,Mk}is a k-induced-matching cover of G if V(M1)∪V(M2)∪…∪ V(Mk)=V(G). The k-induced-matching cover problem asks whether a given graph G has a k-induced-matching cover or not. This paper shows that 2-induced-matching cover problem of graphs with diameter 6 and 3-induced-matching cover problem of graphs with diameter 2 are NP-complete, and 2-induced-matching cover problem of graphs with diameter 2 is polynomially solvable.
