|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 頂 ： [いただき] 【名詞】 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
グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には固定パラメータ容易性 (fixed-parameter tractability) があり、パラメータ化計算量理論の中心問題の1つである。 最小頂点被覆問題は、整数計画問題に定式化でき、その双対問題は最大マッチング問題である。 == 定義 == グラフ ''G'' の頂点被覆とは頂点の集合 ''C'' であり、''G'' の各辺は ''C'' 内の少なくとも1つの頂点と接合する。このとき集合 ''C'' は ''G'' の辺を「被覆 (cover)」すると言う。次の図は2つのグラフの頂点被覆の例を表したものである（集合 ''C'' は赤で示されている）。 : 最小頂点被覆 (minimum vertex cover) は、最も小さい大きさの頂点被覆である。頂点被覆数 (vertex cover number) は最小頂点被覆の大きさである。次の図は2つのグラフの最小頂点被覆の例を表したものである。 : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「頂点被覆」の詳細全文を読む スポンサード リンク
|