|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 最 ： [さい] 1. (n,pref) the most 2. the extreme ・ 最大 ： [さいだい] 【名詞】 1. greatest 2. largest 3. maximum ・ 独 ： [どいつ] (n) Germany ・ 独立 ： [どくりつ] 1. (adj-na,n,vs) independence (e.g., Ind. Day) 2. self-support ・ 集 ： [しゅう] 【名詞】 1. collection ・ 集合 ： [しゅうごう] 1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m) ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
最大独立集合問題（さいだいどくりつしゅうごうもんだい）は、グラフ理論において、与えられたグラフ G(V,E) に対して、頂点集合 V'⊆V のうち V' 内の頂点間に枝が存在しないようなもの（独立集合）で大きさが最大のものを求める問題。最大安定集合問題とも言う。この問題は、NP困難であることが知られている。 この問題は、補グラフに対する最大クリーク問題と等価である。また、独立集合に含まれない頂点は頂点被覆をなし、逆も成り立つので、最小頂点被覆問題とも等価である。 近似アルゴリズムについても、基本的に最大クリーク問題と同じである。グラフの頂点数を n とするとき、近似度 O(n / (log n)^2) が達成されている。また、P=NP が成り立たないとき、任意の ε>0 について、近似度 n^(1/2-ε) の近似アルゴリズムが存在しないことが示されている。NP=ZPPが成り立たない場合、近似度 n^(1-ε) の近似アルゴリズムが存在しないことも示されている。 グラフの最大次数を制限した場合は、以下の結果が知られている。 *次数2: 多項式時間アルゴリズムが存在 *次数3: 1.2-近似アルゴリズムが存在。近似度の下限 1.0071 *次数4: 1.4-近似アルゴリズムが存在。近似度の下限 1.0136 *次数5: 1.6-近似アルゴリズムが存在。近似度の下限 1.0149 ==関連項目== *NP困難 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最大独立集合問題」の詳細全文を読む スポンサード リンク
|