|
完全被覆 (perfect matching) に関する問題の多くは組合せ論やグラフ理論などの離散数学と関わりがある。 ==定義== 頂点の集合をV、辺の集合を E = とすると、無向グラフGは G = (V,E) と書ける。グラフGの被覆 (matching) Mとは、(i,j), (r,s) ⊆ M ならばi, j, r, sが全て異なる頂点となる、とういう条件を満たすEの部分集合のことである。頂点の集合Vの要素の数が2k個で、被覆 (matching) Mがk個の要素を持つ場合、Mは完全 (perfect) であるという。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「完全被覆問題」の詳細全文を読む スポンサード リンク
|