|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ クリーク ： [くりーく] 【名詞】 1. (1) cleek (golf) 2. (2) creek 3. (P), (n) (1) cleek (golf)/(2) creek ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を とするとき、近似度 が達成されているのみである。また、P = NP が成り立たないとき、任意の について、近似度 の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 の近似アルゴリズムが存在しないことも示されている。 ==脚注== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最大クリーク問題」の詳細全文を読む スポンサード リンク
|