以前取り上げたウェルシェ・パウエルのアルゴリズムについて補足。
その後の有限数学の授業で、
（１）ウェルシェ・パウエルのアルゴリズムで塗ると、彩色数より大きくなってしまう例を挙げよ。
（２）さらに、彩色数で塗れるようにアルゴリズムを改良せよ。
という問題が出されたんですよ。
まず（１）の例を見つけるのが結構大変だったのですが、例えば次のような例があります。
G:単純グラフ
V(G)={a,b,c,d,e,f}
E(G)={ac,cd,db,be,ef,fa}
（ようは、a-c-d-b-e-f-aと一周するグラフです。）
このとき、a,c,d,b,e,fの順に塗っていけば２色で塗り分けられるのですが、a,b,c,d,e,fの順に塗っていくと３色必要になってしまいます。
（実際、まずaを1で塗った後、bは周りに使われている色がないので1で塗られ、続いてcは2、dはcとbに隣接しているので、3で塗られます。）
つまり、同じ次数内で塗る順序をきちんと指定してやらないと余分に色を使ってしまうことがあると予想できます。
なら、そもそも高い次数から塗っていくのは後から塗るとより条件が厳しくなるから、というところに注目して、同じ次数の点でも、その隣接している点で既に塗られている点の数が多い順に塗っていけば大丈夫なんじゃないかな、と考えたわけです。
先ほどのグラフも、この考え方を導入すればちゃんと塗れますしね。
ということで、実装したのが以下のColGraph2。
package ColGraph2;
#--------------------------------------------------
# ColGraph2
#
# =スーパークラス=
# ColGraph
#
# =フィールド=
# color
# 色の配列へのリファレンス
#
# matrix
# グラフを意味する２次元配列へのリファレンス
#
# painted
# 隣接する点で既に塗られている点の数の配列
# へのリファレンス
#
# =メソッド=
# new();
# インスタンスを作成する。
# 引数はフィールドの配列のリファレンス。
#
# input_new();
# インスタンスを作成する。
# 標準入力からフィールドを作る。
#
# talk_new();
# インスタンスを作成する。
# 対話型でフィールドを作る。
#
# check();
# グラフの行列になっているかをチェックする。
# なっていないときには0を返す。
#
# num();
# グラフの点の数を返す。
#
# dim(line)
# グラフの行の次数を返す。
#
# get_line(line);
# グラフの行の配列のリファレンスを返す。
#
# print();
# グラフの行列を表示する。
#
# set_color(num, color);
# numの点の色をcolorにする。
#
# get_color(num);
# numの点の色を取得する。
#
# add_painted(num);
# numの点のpaintedを1増やす。
#
# get_painted(num);
# numの点のpaintedの値を得る。
#
# print_color();
# colorの配列を出力する。
#
# paint();
# 改良版のウェルシェ・パウエルのアルゴリズムで
# 彩色していく。
#
#--------------------------------------------------
use ColGraph;
@ISA = 'ColGraph';
#----------------------------------------
# メソッドの実装
#----------------------------------------
sub new{
}
sub add_painted{
}
sub get_painted{
}
sub paint(){
}
1;
ちょっと解説すれば、paintedというフィールドを加え、そこに自分と隣接する点で既に塗られているものが何個あるのか、という情報を加えてあります。
それで、塗る頂点の順番を次数だけで決めるのでなく、まず次数別の配列にした後、その配列内でさらにpaintedの大きい順に塗る、というアルゴリズムにしました。
このアルゴリズムでさっきのグラフはちゃんと塗れるようになったんですけれど、これでもうまく塗れないグラフが実験をするうちに現れてきました。
次のようなヤツです。（グラフの行列で表します。）
0 1 1 0 0 0 1 1
1 0 1 1 0 0 0 1
1 1 0 1 1 0 0 0
0 1 1 0 1 1 0 0
0 0 1 1 0 1 1 0
0 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1
1 1 0 0 0 1 1 0
なんかきれいな行列ですよね（＾＾）
８つの頂点をまずa-b-c-d-e-f-g-h-aと結び、そのあとa-c-e-g-aと一つ飛ばしで結んだのと、b-d-f-h-bとやはり一つ飛ばしで結んだものとを加えたのになっています。（うまく並べると平面グラフになっています。）
で、これを先ほどのColGraph2を使ったプログラムに入れてやると、５色で塗り分けられます。
けれど、このグラフは平面グラフですから、４色で塗れるわけで、彩色数よりも多い数を使ってしまっています。
（ちなみにColGraphを使ったものだと４色で塗り分けられます。なんとも不思議なことに、Perlのハッシュのキーの整列の仕方はこの塗り方にちょうどよくなっていました。）
そんなこんなで、どうにかうまい具合に改良できないかなぁ、とここ数日悶々と考えていたのですが、そのうちにそもそも次数の高い順に塗っていけばOKという思い込みを壊す例が出てきました。
どんなのかというと、次のようなヤツです。
0 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0
これもなかなかきれいですｗ
頂点a,b,c,d,e,f,g,hで、aとhを結ぶように
a-b-e-h
a-c-f-h
a-d-g-h
となっているグラフです。
このグラフは２部グラフなので（a,e,f,gとb,c,d,hに分かれる）、２色で塗り分けられるのですが、次数の高い順に塗っていこうとすると、まずaとhが次数3なのでそれぞれが1で塗られ、その後b,c,dは2で塗られますが、e,f,gはすでに1と2が使われてしまっているので3で塗られてしまいます。
この例が出てきたので、もはや次数の高い順に塗っていき、あとは同じ次数内でどういった順番で塗ればいいのか、という問題では済まなくなってしまっています。
それこそ全部の点を相手にして、どういった順番で塗っていくのが正しいのか、という問題になってしまってますから、「グラフをどういった順序で塗っていくべきか」という問題と同じレベルになってしまい、このアルゴリズムを使っても問題が簡単になっていません。
ということで、ウェルシェ・パウエルのアルゴリズムじゃない方法で塗れないかなぁ、というのがここ数日ずっと考えていることです。
上で見たとおりウェルシェ・パウエルのアルゴリズムで問題となるのが閉路を含む場合であるのは明らかなので、最小の閉路をまず探し、その閉路の中で彩色をしていくのがいいんじゃないかなぁ、と考えています。
その方法をとった場合、問題となるのは、ではそういった閉路をどういった順番で塗っていくのか（奇サイクル（小）→奇サイクル（大）→偶サイクルの順、長さの順など）ということと、その閉路内で、どういった順番に塗っていくようにすればいいのか、ということです。
この２つについていろいろなパターンを今考えているのですが、なかなかうまい解決策が見つかっていないのが現状です。
一応、どの頂点の次数も２以上のグラフにおいて、任意の点で、その点をスタート＆ゴールとする最小の閉路を見つけるアルゴリズムは思いついたので（まぁ、再帰呼び出しみたいなことをオブジェクトにおいてやるわけですが）、あとは上の２つの点を解決できればうまく行きそうな気がします。
余談。
例で一番最後に出したグラフ、確かに平面グラフだけれど、この平面グラフを持つような地図ってホントに存在するのかなぁ、と考えると、これが結構難しい。
答えを言ってしまえば存在するのだけれど（なんとなれば、円の直径を３等分して、そのそれぞれを直径とするような円を作図すればいい）、地図⇒平面グラフに表せる、は正しいとしても、平面グラフ⇒対応する地図が存在する、というのはちょっと怪しいかも。もう少し条件を厳しく出来そうな気もします。
その後の有限数学の授業で、
（１）ウェルシェ・パウエルのアルゴリズムで塗ると、彩色数より大きくなってしまう例を挙げよ。
（２）さらに、彩色数で塗れるようにアルゴリズムを改良せよ。
という問題が出されたんですよ。
まず（１）の例を見つけるのが結構大変だったのですが、例えば次のような例があります。
G:単純グラフ
V(G)={a,b,c,d,e,f}
E(G)={ac,cd,db,be,ef,fa}
（ようは、a-c-d-b-e-f-aと一周するグラフです。）
このとき、a,c,d,b,e,fの順に塗っていけば２色で塗り分けられるのですが、a,b,c,d,e,fの順に塗っていくと３色必要になってしまいます。
（実際、まずaを1で塗った後、bは周りに使われている色がないので1で塗られ、続いてcは2、dはcとbに隣接しているので、3で塗られます。）
つまり、同じ次数内で塗る順序をきちんと指定してやらないと余分に色を使ってしまうことがあると予想できます。
なら、そもそも高い次数から塗っていくのは後から塗るとより条件が厳しくなるから、というところに注目して、同じ次数の点でも、その隣接している点で既に塗られている点の数が多い順に塗っていけば大丈夫なんじゃないかな、と考えたわけです。
先ほどのグラフも、この考え方を導入すればちゃんと塗れますしね。
ということで、実装したのが以下のColGraph2。
package ColGraph2;
#--------------------------------------------------
# ColGraph2
#
# =スーパークラス=
# ColGraph
#
# =フィールド=
# color
# 色の配列へのリファレンス
#
# matrix
# グラフを意味する２次元配列へのリファレンス
#
# painted
# 隣接する点で既に塗られている点の数の配列
# へのリファレンス
#
# =メソッド=
# new();
# インスタンスを作成する。
# 引数はフィールドの配列のリファレンス。
#
# input_new();
# インスタンスを作成する。
# 標準入力からフィールドを作る。
#
# talk_new();
# インスタンスを作成する。
# 対話型でフィールドを作る。
#
# check();
# グラフの行列になっているかをチェックする。
# なっていないときには0を返す。
#
# num();
# グラフの点の数を返す。
#
# dim(line)
# グラフの行の次数を返す。
#
# get_line(line);
# グラフの行の配列のリファレンスを返す。
#
# print();
# グラフの行列を表示する。
#
# set_color(num, color);
# numの点の色をcolorにする。
#
# get_color(num);
# numの点の色を取得する。
#
# add_painted(num);
# numの点のpaintedを1増やす。
#
# get_painted(num);
# numの点のpaintedの値を得る。
#
# print_color();
# colorの配列を出力する。
#
# paint();
# 改良版のウェルシェ・パウエルのアルゴリズムで
# 彩色していく。
#
#--------------------------------------------------
use ColGraph;
@ISA = 'ColGraph';
#----------------------------------------
# メソッドの実装
#----------------------------------------
sub new{
my ($class, $ref) = @_;
my $painted;
my $obj = $class-＞SUPER::new($ref);
foreach(1..$obj-＞num()){
push @$painted, 0;
}
$obj-＞{painted} = $painted;return $obj;
}
sub add_painted{
my ($self, $num) = @_;
++($self-＞{painted}-＞[$num-1]);}
sub get_painted{
my ($self, $num) = @_;
return $self-＞{painted}-＞[$num-1];}
sub paint(){
my $class = shift @_;
my %struct;
#次数をキーとするハッシュに点を振り分ける
foreach(1..$class-＞num()){
my $dim = $class-＞dim($_);
#キーが存在しない場合は空の配列リファレンスを作成
unless(exists $struct{$dim}){
$struct{$dim} = [];
}
#点をハッシュの指す配列に入れる
push @{$struct{$dim}}, $_;
}
#次数の高い順に塗っていく
foreach my $num (sort {$b＜=＞$a} keys %struct){
my $nums = $struct{$num};
#paintedの高い順に塗っていく
while(1){
my $color = 1;
my $flag = 0;
my $line;
#塗っていないのがなければループを抜ける
unless(@$nums){
last;
}
#あれば、paintedの一番高いものを取得
else{
@$nums = sort {
$class-＞get_painted($b) ＜=＞ $class-＞get_painted($a)
} @$nums;
$line = shift @$nums;
}
#色を探す
while(1){
#隣接している点で同じ色がないかチェック
foreach(1..$class-＞num()){
if($class-＞get_line($line)-＞[$_-1] == 1){
if($class-＞get_color($_) == $color){
$flag = 1;
last;
}
}
}
#同じ色があった場合次の色で試す
if($flag){
++$color;
$flag = 0;
next;
}
#なかった場合ループを抜ける
else{
last;
}
}
#見つけた色をセット
$class-＞set_color($line, $color);
#隣接している点のpaintedを1増やす
foreach(1..$class-＞num()){
if($class-＞get_line($line)-＞[$_-1] == 1){
$class-＞add_painted($_);
}
}
}
}
}
1;
ちょっと解説すれば、paintedというフィールドを加え、そこに自分と隣接する点で既に塗られているものが何個あるのか、という情報を加えてあります。
それで、塗る頂点の順番を次数だけで決めるのでなく、まず次数別の配列にした後、その配列内でさらにpaintedの大きい順に塗る、というアルゴリズムにしました。
このアルゴリズムでさっきのグラフはちゃんと塗れるようになったんですけれど、これでもうまく塗れないグラフが実験をするうちに現れてきました。
次のようなヤツです。（グラフの行列で表します。）
0 1 1 0 0 0 1 1
1 0 1 1 0 0 0 1
1 1 0 1 1 0 0 0
0 1 1 0 1 1 0 0
0 0 1 1 0 1 1 0
0 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1
1 1 0 0 0 1 1 0
なんかきれいな行列ですよね（＾＾）
８つの頂点をまずa-b-c-d-e-f-g-h-aと結び、そのあとa-c-e-g-aと一つ飛ばしで結んだのと、b-d-f-h-bとやはり一つ飛ばしで結んだものとを加えたのになっています。（うまく並べると平面グラフになっています。）
で、これを先ほどのColGraph2を使ったプログラムに入れてやると、５色で塗り分けられます。
けれど、このグラフは平面グラフですから、４色で塗れるわけで、彩色数よりも多い数を使ってしまっています。
（ちなみにColGraphを使ったものだと４色で塗り分けられます。なんとも不思議なことに、Perlのハッシュのキーの整列の仕方はこの塗り方にちょうどよくなっていました。）
そんなこんなで、どうにかうまい具合に改良できないかなぁ、とここ数日悶々と考えていたのですが、そのうちにそもそも次数の高い順に塗っていけばOKという思い込みを壊す例が出てきました。
どんなのかというと、次のようなヤツです。
0 1 1 1 0 0 0 0
1 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 0
これもなかなかきれいですｗ
頂点a,b,c,d,e,f,g,hで、aとhを結ぶように
a-b-e-h
a-c-f-h
a-d-g-h
となっているグラフです。
このグラフは２部グラフなので（a,e,f,gとb,c,d,hに分かれる）、２色で塗り分けられるのですが、次数の高い順に塗っていこうとすると、まずaとhが次数3なのでそれぞれが1で塗られ、その後b,c,dは2で塗られますが、e,f,gはすでに1と2が使われてしまっているので3で塗られてしまいます。
この例が出てきたので、もはや次数の高い順に塗っていき、あとは同じ次数内でどういった順番で塗ればいいのか、という問題では済まなくなってしまっています。
それこそ全部の点を相手にして、どういった順番で塗っていくのが正しいのか、という問題になってしまってますから、「グラフをどういった順序で塗っていくべきか」という問題と同じレベルになってしまい、このアルゴリズムを使っても問題が簡単になっていません。
ということで、ウェルシェ・パウエルのアルゴリズムじゃない方法で塗れないかなぁ、というのがここ数日ずっと考えていることです。
上で見たとおりウェルシェ・パウエルのアルゴリズムで問題となるのが閉路を含む場合であるのは明らかなので、最小の閉路をまず探し、その閉路の中で彩色をしていくのがいいんじゃないかなぁ、と考えています。
その方法をとった場合、問題となるのは、ではそういった閉路をどういった順番で塗っていくのか（奇サイクル（小）→奇サイクル（大）→偶サイクルの順、長さの順など）ということと、その閉路内で、どういった順番に塗っていくようにすればいいのか、ということです。
この２つについていろいろなパターンを今考えているのですが、なかなかうまい解決策が見つかっていないのが現状です。
一応、どの頂点の次数も２以上のグラフにおいて、任意の点で、その点をスタート＆ゴールとする最小の閉路を見つけるアルゴリズムは思いついたので（まぁ、再帰呼び出しみたいなことをオブジェクトにおいてやるわけですが）、あとは上の２つの点を解決できればうまく行きそうな気がします。
余談。
例で一番最後に出したグラフ、確かに平面グラフだけれど、この平面グラフを持つような地図ってホントに存在するのかなぁ、と考えると、これが結構難しい。
答えを言ってしまえば存在するのだけれど（なんとなれば、円の直径を３等分して、そのそれぞれを直径とするような円を作図すればいい）、地図⇒平面グラフに表せる、は正しいとしても、平面グラフ⇒対応する地図が存在する、というのはちょっと怪しいかも。もう少し条件を厳しく出来そうな気もします。