16.4 グリーディ彩色アルゴリズム 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム
- 点彩色問題の位置
- 点彩色問題および辺彩色問題に関係する定理
- 問題の難しさを与える定理
- 与えられた単純グラフの辺彩色数が3であるか決定する決定問題はNP-完全である
- 与えられた平面的グラフの(点)彩色数が3であるか決定する決定問題はNP-完全である
- 問題の容易さを与える情報
- 上述のNP-完全性をのべた定理から次のことが言える
- 与えられたグラフの(点)彩色数・辺彩色数が3未満であるかどうかを判定して、3未満であるときに、実際に最適な彩色をすることは、線形時間で可能である
- 上述のNP-完全性をのべた定理から次のことが言える
- 特殊なグラフにおける定理
- 2部グラフ(Mathematicaの記事はこちら)
- 2部グラフGにおける辺彩色数はGの点の最大次数に等しい
- 2部グラフの点彩色数は2(2点彩色グラフを2部グラフの定義としてもよいことから明らか)
- 多変量組み合わせ関連解析における考え方はこちら
- パーフェクトグラフ(Mathematicaの記事はこちら)
- パーフェクトグラフに対しては、点彩色問題・最大重み安定集合問題・最大重みクリーク問題が強多項式時間で解ける(これら3問題は一般グラフに対してNP-困難である)
- 平面的グラフ(Mathematicaの記事はこちら)
- 2部グラフ(Mathematicaの記事はこちら)
- 彩色数と彩色のためのアルゴリズム
- 具体的には
- 与えられたグラフが2部か否か、パーフェクトか否か、平面的か否かを判定し、いずれかの判定が是であったら、それぞれの教える彩色数の最小のものが、最小近似解であり、いずれでもなければ、グラフの最大次数kについてk+1を最小近似解とすればよさそうだ
- グリーディ彩色アルゴリズムのソース(ここで用いているGraph classはこちら)
- 問題の難しさを与える定理
public static int[] GreedyColoring(Graph g){
int[] ret = new int[g.numV];
for(int i=0;i<ret.length;i++){
ret[i]=g.numV-1;
}
for(int i=0;i<ret.length;i++){
int[] tmp = new int[i];
for(int j=0;j<i;j++){
if(g.adjMatrix[i][j]==1){
tmp[j]=ret[j];
}else{
tmp[j]=g.numV-1;
}
}
int[] checker= new int[g.numV];
for(int j=0;j<checker.length;j++){
checker[j]=j;
}
for(int j=0;j<tmp.length;j++){
if(tmp[j]<g.numV){
checker[tmp[j]]=g.numV-1;
}
}
int tmpmin=checker[0];
for(int j=1;j<checker.length;j++){
if(tmpmin>checker[j]){
tmpmin=checker[j];
}
}
ret[i]=tmpmin;
}
return ret;
}