k.t.
kohsk****@msc*****
2003年 3月 31日 (月) 20:13:54 JST
高橋(k)です。
かな〜り、どうでもいい話になってますが、ちょっと面白いので。
> > > > >色の印番号が現在の頂点番号に等しいなら、色は印付けられているとみなさ
> れ
> > > る。
> > > > >これは各頂点のために印を置き直さねばならない厄介事から守る。
> > >
> > > >これはどういうことなんだろう?
> >
> > > 意味通りませんよね。直訳したらこうなったのですが、おかしいです。
> > > もう少し意訳するよう努力してみます。
> >
> > いや、これは訳は悪くなくて、どう訳してもこんな感じになると思いますが、原
> > 文読んでも意味が解らなかったという。。。
> > 後でちょいと分析してみようかと、たくらんでます。
>
> 手元の本にビジングの定理というのがあり、グラフＧはΔ(G)+1 (最大次数+1)色で
> 彩色可能であるというものです。つまり頂点数==色数の時は、もしかしたら色を
> 付け直すことによりもっと少ない色数で塗ることが可能であるかもしれないが、
> そういう面倒は避けようという事ではないかと思いました。
>
> 頂点数==色数となるような場合があるとすれば、彩色し始めのごく初期の頃に
> 起きるのではないかと思います。後はおおむね頂点数＞色数となると思います。
constructing_algorithm.html のサンプルを考えてみました。
多分、そんなややこしいことではなくて、
// 隣接頂点の全ての色を印付ける
typename GraphTraits::adjacency_iterator ai, aend;
for (tie(ai, aend) = adjacent_vertices(current, G); ai != aend; ++ai)
mark[color[*ai]] = i;
ここで、vector mark の値を、その時点で着色される頂点のインデックスにして
るわけですね。
size_type smallest_color = 0;
while (smallest_color < max_color && mark[smallest_color] == i)
++smallest_color;
で、ここで、一番目の比較はいいとして、配列markがどうなっていたら、印付け
されていると判断するかというと、やっぱりその時点で着色される頂点のインデッ
クスと等しかったらなんですね。
markの添字はいわゆる、色インデックスですから、一見markの値はboolで十分な
気もしますが、boolにすると、次の頂点に入るたびにmarkをfalseなりにする必
要がある=各頂点のために印を置き直す必要がある、と。
でも、着色される頂点のインデックスを記し付けフラグとして使えば、その必要
がない、というそれだけの話ではないかと思います。次の頂点にうつったときに、
既存のmark配列の値の最大値は i-1 であるか、或いは初期値
numeric_limits_max(max_color)
なので、markのリセットが必要ないんですね。なるほどなあ、という感じです。
--
TAKAHASHI, kohske
kohsk****@msc*****
takah****@cog*****
http://talepan.virtualave.net/