貪欲彩色
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
同じグラフにおいて2種類の頂点の順序付けをしたときの貪欲彩色。うまく順序付けすれば2-彩色可能だが、貪欲彩色では n / 2 {\displaystyle n/2} 色まで費やすことがある。 貪欲法では、頂点に所定の順序 v 1 {\displaystyle v_{1}} ,…, v n {\displaystyle v_{n}} を設定し、 v i {\displaystyle v_{i}} に対して v 1 {\displaystyle v_{1}} ,…, v i − 1 {\displaystyle v_{i-1}} までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数 χ ( G ) {\displaystyle \chi (G)} による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が n 個の crown graph は2-彩色的だが、貪欲彩色では n / 2 {\displaystyle n/2} 色を必要とすることがある。 頂点を次数が小さくなる順序でソートすれば、貪欲彩色で使う最大色数は max i min { d ( x i ) + 1 , i } {\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}} となり、最悪でもそのグラフの最大次数より1つだけ大きい色数になる。このヒューリスティックを Welsh–Powell アルゴリズムとも呼ぶ。他にも、アルゴリズム実行中に動的に頂点の順序を決定していくヒューリスティックもあり、最も多くの異なる色と隣接している頂点を次の頂点として選ぶという方法もある。他にも様々なヒューリスティクスを採用したアルゴリズムがあり、これらを総称して逐次彩色 (sequential coloring) アルゴリズムと呼ぶこともある。
※この「貪欲彩色」の解説は、「グラフ彩色」の解説の一部です。
「貪欲彩色」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
- 貪欲彩色のページへのリンク
