|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 支配 ： [しはい] 1. (n,vs) rule 2. control 3. direction ・ 配 ： [はい] 1. (n,vs) disposition 2. distribution 3. arrangement ・ 集 ： [しゅう] 【名詞】 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
支配集合問題（しはいしゅうごうもんだい）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ ''G''(''V'', ''E'') の頂点集合 ''V''′ (⊆ ''V'') で、''V''′ に属さない全ての頂点 ''v'' について、''v'' の隣接頂点のいずれか一つが ''V''′ に属するような ''V''′ （支配集合）のうち、最小のものを求める問題。 この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|''V''| の解を得ることができる。また、ある定数 ''c'' > 0 について、''c'' log|''V''| 近似アルゴリズムが存在しないことも示されている。 しかし、平面グラフに対しては、PTAS が存在することも知られている。 == 関連項目 == *NP完全 *アルゴリズム 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「支配集合問題」の詳細全文を読む スポンサード リンク
|