翻訳と辞書 |
最小クリーク被覆問題[くりーくひふく] 計算量理論において、最小のクリーク被覆(クリークひふく、)を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はリチャード・カープによるオリジナルの21問題の一つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。 クリーク被覆問題(クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を ''k''-個のクリークへ分割できるかどうかを決定する問題である。頂点集合の ''k''-個の集合への分割が与えられたとき、その各集合がクリークを成すかどうかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの ''k''-彩色可能性からの帰着である。これを見るには、まずグラフ ''G'' の ''k''-彩色可能性をその補グラフ ''G''′ に関する事実に翻訳すればよい。このとき ''G'' の ''k''-個のクリークへの分割は ''G''′ の ''k''-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の一つの色を塗ることで ''k''-彩色ができたことになる)。 この問題と関連して、クリーク辺被覆問題というのは、与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 == 参考文献 ==
* * A1.2: GT19, pg.194.
抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「最小クリーク被覆問題」の詳細全文を読む
スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|