Brooksの定理++ - 高温処理済みコースケ

無向グラフGの頂点を適当に順序付けして、辺の両端 $i, j$ が $i \lt j$ なら、 $i \leftarrow j$ へ方向付けした有向グラフをHとする。
Hの最大出次数 $\Delta_+(H) = k$ のとき、Gはk+1彩色可能で、これはBrooksの定理を含んで、より上限を押さえるとおもってるんだけど、~~既知なのかがわからん~~。

これは既知だった。これはk-degenerate graph(縮退)というらしい。
Degeneracy (graph theory) - Wikipedia

証明自体はたぶん正しいとおもう。

n頂点からなる単純な無向グラフを $G$ とし、 $G$ に頂点 $v$ を一つ追加したグラフを $G'$ とする。
$G$ の彩色数 $\chi(G) = k$ の時、 $\chi(G')$ は、 $v$ の次数 $d(v)$ により次のいずれかとなる。

$\chi(G')=\begin{cases} k+1 & ( d(v) = n ) \\ k+1 \text{ or } k & ( d(v) \ge k )\\ k & ( d(v) \lt k ) \end{cases}$

証明については下記リンク先を参照*1
kousuke.hatenablog.com

これは結局、グラフに1点追加したとき、彩色数は2つも3つも上がらないし、接続する次数が彩色数未満なら確実に上がらないし、全点に接続すれば1上がるし、その間はよくわからんということに他ならない。ただ、グラフGをある空間から別の空間に頂点を一つずつ移動していくようなオペレーションを考えれば、移動先の彩色数と移動する頂点の辺の片側(移動先側)だけ見ていればよい、そうすればおよそ上限がわかってくるよということになる。

単純な無向グラフGの頂点集合Vを順序付ける写像fを用意する。
$f: \{ \> i \in \mathbb{N}_0 \> | \> i \lt |V| \> \} \rightarrow V$

$f(i)=v$ である頂点を $v_i$ と書くことにする。

無向グラフGから有向グラフHへの変換を $h: G \rightarrow H$ とする。

$h: \{ \> \{u,v\} \in E \> \} \rightarrow \{ \> (v_{src}, v_{dst}) \in V \times V \> | \> src \gt dst \>\}$

hはfにより辺の向き(i > jならi -> jの方向)が一意に決まることを示している(つもり)。
$V_n = \{ v_0, v_1, \dots, v_{n-1}\}$ とし $V$ から $V_n$ を除く差集合 $V \setminus V_n$ を ${V_n}^c$ と書く。

$G,\> H$ の $V_n$ による誘導部分グラフ $G[V_n] ,\> H[V_n]$ を $G_n ,\> H_n$ 、また $G ,\> H$ から $G_n, H_n$ を除く部分グラフ $G \setminus G_n, H \setminus H_n$ を ${G_n}^c,\> {H_n}^c$ と書く。

頂点vでの次数、出次数をそれぞれ $d(v),d_+(v)$ 、最大次数、最大出自数については $\Delta(G),\Delta_+(H)$ と書く。 ${G_n}^c,\> {H_n}^c$ に対しては、 $\Delta({G_n}^c)=\max \{ \> d(v), v \in {V_n}^c \> \}$ , $\Delta_+({H_n}^c)=\max \{ \> d_+(v), v \in {V_n}^c \> \}$ である。

最初の式を書きなおすと以下のようになる。 $\chi(G_n)=k$ とする。

$\chi(G_{n+1}) - \chi(G_n) = \begin{cases} 1 & (d_+(v_n) = n)\\ 1 \text{ or } 0 & (d_+(v_n) \ge k)\\ 0 & (d_+(v_n) \lt k) \end{cases}$

後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。

$\chi(G_n) > \Delta_+({H_n}^c) \Rightarrow \chi(G_n) = \chi(G)$

n = 0のとき、 ${H_n}^c = H$ なので、 $G$ は $\Delta_+(H)+1$ で彩色可能なことがわかる。

さて $\chi_{n}$ を $\chi_{n} \ge \chi(G_n)$ を満たす数列とすれば、ステップ関数 $u(x)$ を使用して、もうすこし精度よく上限を求めることができる。

$\begin{cases} \chi_{n+1} - \chi_{n} = u(d_+(v_n) - \chi_{n}) \\ \chi_0 = 0 \\ \end{cases}$

$u(x)=\begin{cases} 1 & (x \ge 0) \\ 0 & (x \lt 0) \end{cases}$

計算量はHに対して $O(|V|)$ ででき、上限は最悪でも $\Delta_+(H)+1$ で抑えることができる。

いままでの内容を例としてまとめるとこんな感じになる。(n=4の時の図)
f:id:tinsep19:20170320145321p:plain

$n$	0	1	2	3	4	5	6	7	8
$\chi(G_n)$	0	1	2	3	4	4	4	4	4
$d_+(v_n)$	0	1	2	3	2	2	2	3	-
$\Delta_+({H_n}^c)$	3	3	3	3	3	3	3	3	-
$d(v_n)$	3	4	3	7	4	3	3	3	-
$\Delta({G_n}^c)$	7	7	7	7	4	3	3	3	-
$\chi_n$	0	1	2	3	4	4	4	4	4

まずブルックスの定理での彩色数の上限が $\chi(G) \le 8(= \Delta(G)+1)$ なのに対して、 $\chi(G) \le 4(= \Delta_+(H)+1)$ で抑えられていることがわかる。

次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。また実際に彩色数も上がっていないことがわかる。

結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。
例えば、頂点を次数降順でソートすると $d(v_n) = \Delta({G_n}^c) \ge \Delta_+({H_n}^c)$ となるが一番次数の大きい頂点は $v_0$ でその出次数は $d_+(v_0) = 0$ となり、彩色数を0から1にするだけになる。むしろ重要なのは次数降順の場合、 $\chi(G_n) \gt d(v_n)$ となるような部分グラフ $G_n$ で全体の彩色数を求められるということだとおもう。

頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。

現在、厳密に彩色数を求める計算量は $O(2^nn)$ らしいけど、頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。

そこで重要になるのが、ヒューリスティックな方法で、今回の例では $\chi_n$ が彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。

貪欲彩色のWelsh-Powellのアルゴリズムに比べると実際に彩色するかしないかの違いがある。ただ単に彩色数を近似したいときは今回紹介したほうが便利で、実際に彩色した結果がほしいのであればWelsh-Powellの方が便利。

$\chi_n > d(v_n)$ となった時点で、いったん厳密な彩色数を求めて $\chi_n$ を更新して、もう一度 $\chi_n > d(v_n)$ となった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。

その他

例えば、ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。

シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。
位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。

追記

Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。

また上記の近似解kを使ってgales-sharpleyの変形で外部性のある安定結婚問題として解くとk以下の彩色が求められる。
計算量は $O(k^2(|V| + |E|))$ だとおもうけどこれは少し怪しい( $k^2$ で収束するかが微妙)。