Brooksの定理++
無向グラフGの頂点を適当に順序付けして、辺の両端がなら、へ方向付けした有向グラフをHとする。
Hの最大出次数のとき、Gはk+1彩色可能で、これはBrooksの定理を含んで、より上限を押さえるとおもってるんだけど、既知なのかがわからん。
これは既知だった。これはk-degenerate graph(縮退)というらしい。
Degeneracy (graph theory) - Wikipedia
証明自体はたぶん正しいとおもう。
n頂点からなる単純な無向グラフをとし、に頂点を一つ追加したグラフをとする。
の彩色数の時、は、の次数により次のいずれかとなる。
証明については下記リンク先を参照*1
kousuke.hatenablog.com
これは結局、グラフに1点追加したとき、彩色数は2つも3つも上がらないし、接続する次数が彩色数未満なら確実に上がらないし、全点に接続すれば1上がるし、その間はよくわからんということに他ならない。ただ、グラフGをある空間から別の空間に頂点を一つずつ移動していくようなオペレーションを考えれば、移動先の彩色数と移動する頂点の辺の片側(移動先側)だけ見ていればよい、そうすればおよそ上限がわかってくるよということになる。
単純な無向グラフGの頂点集合Vを順序付ける写像fを用意する。
である頂点をと書くことにする。
無向グラフGから有向グラフHへの変換をとする。
hはfにより辺の向き(i > jならi -> jの方向)が一意に決まることを示している(つもり)。
としからを除く差集合をと書く。
のによる誘導部分グラフを、またからを除く部分グラフをと書く。
頂点vでの次数、出次数をそれぞれ、最大次数、最大出自数についてはと書く。に対しては、,である。
最初の式を書きなおすと以下のようになる。とする。
後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。
n = 0のとき、なので、はで彩色可能なことがわかる。
さてをを満たす数列とすれば、ステップ関数を使用して、もうすこし精度よく上限を求めることができる。
計算量はHに対してででき、上限は最悪でもで抑えることができる。
いままでの内容を例としてまとめるとこんな感じになる。(n=4の時の図)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
0 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 4 | |
0 | 1 | 2 | 3 | 2 | 2 | 2 | 3 | - | |
3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | - | |
3 | 4 | 3 | 7 | 4 | 3 | 3 | 3 | - | |
7 | 7 | 7 | 7 | 4 | 3 | 3 | 3 | - | |
0 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 4 |
まずブルックスの定理での彩色数の上限がなのに対して、で抑えられていることがわかる。
次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。また実際に彩色数も上がっていないことがわかる。
結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。
例えば、頂点を次数降順でソートするととなるが一番次数の大きい頂点はでその出次数はとなり、彩色数を0から1にするだけになる。むしろ重要なのは次数降順の場合、となるような部分グラフで全体の彩色数を求められるということだとおもう。
頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。
現在、厳密に彩色数を求める計算量はらしいけど、頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。
そこで重要になるのが、ヒューリスティックな方法で、今回の例ではが彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。
貪欲彩色のWelsh-Powellのアルゴリズムに比べると実際に彩色するかしないかの違いがある。ただ単に彩色数を近似したいときは今回紹介したほうが便利で、実際に彩色した結果がほしいのであればWelsh-Powellの方が便利。
となった時点で、いったん厳密な彩色数を求めてを更新して、もう一度となった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。
その他
例えば、ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。
シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。
位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。
追記
Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。
また上記の近似解kを使ってgales-sharpleyの変形で外部性のある安定結婚問題として解くとk以下の彩色が求められる。
計算量はだとおもうけどこれは少し怪しい(で収束するかが微妙)。
外部性があってもDA方式(受入保留方式/gales-sharpleyのアルゴリズム)で安定マッチング(ペア安定マッチング)はあることがわかっているけど、グループ安定性を満たさない、耐戦略性を満たさないというのが下記論文に書いてある。