|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 最 ： [さい] 1. (n,pref) the most 2. the extreme ・ 最小 ： [さいしょう] 【名詞】 1. smallest 2. least ・ クリーク ： [くりーく] 【名詞】 1. (1) cleek (golf) 2. (2) creek 3. (P), (n) (1) cleek (golf)/(2) creek ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 被覆 ： [ひふく] (n,vs) insulation ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
計算量理論において、最小のクリーク被覆（クリークひふく、）を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はリチャード・カープによるオリジナルの21問題の一つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"（「組合せ論的問題間の還元可能性」）に示されている。 クリーク被覆問題（クリーク分割問題と呼ぶこともある）とは、与えられたグラフの頂点集合を ''k''-個のクリークへ分割できるかどうかを決定する問題である。頂点集合の ''k''-個の集合への分割が与えられたとき、その各集合がクリークを成すかどうかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの ''k''-彩色可能性からの帰着である。これを見るには、まずグラフ ''G'' の ''k''-彩色可能性をその補グラフ ''G''′ に関する事実に翻訳すればよい。このとき ''G'' の ''k''-個のクリークへの分割は ''G''′ の ''k''-個の独立集合への分割を求めることに対応する（各集合にそれぞれ別の一つの色を塗ることで ''k''-彩色ができたことになる）。 この問題と関連して、クリーク辺被覆問題というのは、与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 == 参考文献 == * * A1.2: GT19, pg.194. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最小クリーク被覆問題」の詳細全文を読む スポンサード リンク
|