正確なアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
k-彩色の判定を力まかせ探索で行う場合、n 個の頂点に k 色を割り当てる k n {\displaystyle k^{n}} の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では k = 1 , … , n − 1 {\displaystyle k=1,\ldots ,n-1} の全ての k について同じ作業をすることになり、小さいグラフ以外では現実的でない。 動的計画法と最大独立集合の数の制約を利用するとk-彩色可能性の判定は時間および空間計算量 O ( 2.445 n ) {\displaystyle O(2.445^{n})} で行える。包除原理と高速ゼータ変換のためのYatesのアルゴリズムを使えば、k-彩色可能性の判定は任意のkについて O ( 2 n n ) {\displaystyle O(2^{n}n)} の時間で行える。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ O ( 1.3289 n ) {\displaystyle O(1.3289^{n})} および O ( 1.7504 n ) {\displaystyle O(1.7504^{n})} の時間で判定できる。
※この「正確なアルゴリズム」の解説は、「グラフ彩色」の解説の一部です。
「正確なアルゴリズム」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
ウィキペディア小見出し辞書の「正確なアルゴリズム」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 正確なアルゴリズムのページへのリンク
