|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 頂 ： [いただき] 【名詞】 1. (1) crown (of head) 2. summit (of mountain) 3. spire 4. (2) easy win for one 5. (3) something received ・ 頂点 ： [ちょうてん] 【名詞】 1. top 2. summit ・ 被覆 ： [ひふく] (n,vs) insulation ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
頂点被覆問題（ちょうてんひふくもんだい）は計算複雑性理論における問題の一つであり、 NP完全に属する問題の内のひとつ。 == 内容 == 頂点被覆問題はグラフ G(V,E)（Vは頂点、Eは辺）と k < |V| となる整数 k が与えられたとき、以下のような V の部分集合 V' を探索する問題である。 :問題 グラフ G(V,E) の各枝 e について端点のいずれか少なくとも一方が、V' に含まれるような V の部分集合 V' のうち、|V'| = k となるものが存在するかを求めよ。 また|V'|の最小値を求める問題は最小頂点被覆問題といい、こちらはNP困難に属する問題になる。 頂点被覆問題は、独立集合問題と深く関係している。n 個の頂点のグラフに対して、大きさ k の頂点被覆が存在することと、大きさ n-k の独立頂点集合が存在することは、同値だからである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「頂点被覆問題」の詳細全文を読む スポンサード リンク
|