完全被覆問題
頂点の集合をV、辺の集合を E = {(i,j)| i,j ⊆ V} とすると、無向グラフGは G = (V,E) と書ける。グラフGの被覆 (matching) Mとは、(i,j), (r,s) ⊆ M ならばi, j, r, sが全て異なる頂点となる、という条件を満たすEの部分集合のことである。頂点の集合Vの要素の数が2k個で、被覆 (matching) Mがk個の要素を持つ場合、Mは完全 (perfect) であるという。