Chromatic Polynomial と Acyclic Orientation - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ

SRM717 の Hard で出題されて気になったので書き留めておきます。

Chromatic Polynomial について

まず、無向グラフの頂点から色への対応を彩色、隣接する頂点が同じ色にならないような彩色のことを正しい彩色ということにします。これはこの記事限定用語です。

以下無向グラフ $G$ を $\lambda$ 色で正しい彩色する場合の数を $\chi(G,\lambda)$ と表します。

Chromatic Polynomial はこの $\chi(G,\lambda)$ のことです。

これは、色数 $\lambda$ の多項式になります。

まずはこの多項式を具体的に構成しましょう。

$\chi(G,\lambda)$ は以下の性質を持ち、また逆に、以下の性質を持つ関数は $\chi(G,\lambda)$ となります。

$G_0$ を 1 頂点からなるグラフとすると $\chi(G_0,\lambda) = \lambda$
$G$ の連結成分を $G_1,...,G_c$ とすると、 $\chi(G,\lambda) = \Pi \chi(G_i,\lambda)$
$G$ の任意の辺 $e$ について、 $\chi(G,\lambda) = \chi(G \backslash e,\lambda) - \chi(G/e,\lambda)$

ここで、 $G \backslash e$ は $G$ から辺 $e$ を取り除いたグラフのこととします。

一方、 $G / e$ は辺 $e$ を縮約して、両端の頂点を 1 つに潰したグラフのこととします。

以下、 $\chi(G,\lambda)$ がこの 3 つの性質を持つことを示しましょう。

1 は、1 頂点のグラフを $\lambda$ 色で塗り分ける通り数なので $\lambda$ 通りです。

2 は、それぞれの連結成分ごとに独立に塗り分けられるので、場合の数はそれらの積になります。

3 は少し難しいです。

$e = \{u, v\}$ とします。

$G$ の正しい彩色は、 $G \backslash e$ の正しい彩色となっています。（条件がより緩いため）

逆に $G \backslash e$ の正しい彩色を考えましょう。この彩色はほとんどが $G$ の正しい彩色となっています。

どのような彩色がダメかというと、 $u$ と $v$ を同じ色に塗るようなもの (*) です。このような彩色はいくつあるでしょうか。

(*) を満たすような彩色 $\sigma$ を一つ取ります。

$G / e$ の彩色 $\sigma'$ として、 $u$ と $v$ を縮約してできた頂点の色を $\sigma(u) ( = \sigma(v) )$ で塗り、それ以外の頂点を $\sigma$ と同じ色塗りとしたものをとります。

$\sigma$ が $G \backslash e$ の正しい彩色であることから、 $\sigma'$ は $G / e$ の正しい彩色であることがわかります。

また、少し考えれば、 $G / e$ の正しい彩色 $\sigma'$ と、 $G$ の不正な彩色 $\sigma$ のこの対応は 1 対 1 対応になっていることが分かります。

よって、 $\chi(G \backslash e,\lambda)$ から $\chi(G / e,\lambda)$ だけ取り除いてやればよいので、 $\chi(G,\lambda) = \chi(G \backslash e,\lambda) - \chi(G/e,\lambda)$ が成り立ちます。

以上より示されました。

逆に、3 つの性質を満たす関数があると、帰納的に $\chi(G,\lambda)$ と一致することが分かります。

また、以上の性質から、 $\chi(G,\lambda)$ が多項式になることも分かると思います。

Acyclic Orientation と Chromatic Polynomial について

向き付け (Orientation) とは、無向グラフの辺を向き付けて有向グラフにする操作とします。

Acyclic Orientation はその名の通り、サイクルが存在しないような向き付けのことです。

実は、Chromatic Polynomial と Acyclic Orientation は深く関係しています。

まず、 $\chi(G,\lambda)$ に別の解釈を与えましょう。

前の章では、彩色 $\sigma$ を、頂点から色への関数としていましたが、今回は色に番号をつけて、頂点から $\{1, 2, ..., \lambda \}$ への関数とします。

こうしたとき、 $\chi(G,\lambda)$ は以下の条件を満たす、彩色 $\sigma$ と向き付け $O$ の組の数となります。

$O$ によってサイクルは生じない
$O$ によって $u \rightarrow v$ と向き付けられたとすると、 $\sigma(u) > \sigma(v)$

正しい彩色 $\sigma$ が与えられると、値が大きい方から小さい方に向けなければいけないので、向き付けは一意に定まります。

逆に、上記の条件を満たしているとき、辺の両端の値は異なるので、彩色は正しい彩色となっています。

よって、正しい彩色と上記の条件を満たす組は一対一対応しているので、どちらも場合の数は $\chi(G,\lambda)$ となります。

次に、少し変えた以下のような条件を満たす彩色 $\sigma$ と向き付け $O$ の組の数 $\overline{\chi}(G,\lambda)$ を考えます。

$O$ によってサイクルは生じない
$O$ によって $u \rightarrow v$ と向き付けられたとすると、 $\sigma(u) \ge \sigma(v)$

2 の条件を満たすとき $O$ は $u$ に適合するということにします。

条件を満たす組のことを正しい組ということにします。また、彩色 $\sigma$ が固定されているとき、サイクルを生じない $\sigma$ に適合する向き付けのことを正しい向き付けということにします。

$G$ の頂点数を $N$ とすると、実は、 $\overline{\chi}(G,\lambda) = (-1)^{N} \chi(G,-\lambda)$ (**) が成り立つということを示すのがこの章の山場です。

この式は、 n 個のものを m 個に分ける組み合わせの数 $\binom {n}{k}$ と重複組み合わせ $\binom {n+k-1}{k}$ の関係 $\binom {n+k-1}{k} = (-1)^{k} \binom {-n}{k}$ に相当するらしいです。

たしかに $\overline{\chi}$ の条件の方は重複組み合わせ感ありますが、この類推がどこまで深い対応を示しているのかは正直よく分かっていません。

それでは (**) を示していきましょう。

前の章と同様に、 $\overline{\chi}(G,\lambda)$ を具体的に構成していきます。

$G_0$ を 1 頂点からなるグラフとすると $\overline{\chi}(G_0,\lambda) = \lambda$
$G$ の連結成分を $G_1,...,G_c$ とすると、 $\overline{\chi}(G,\lambda) = \Pi \overline{\chi}(G_i,\lambda)$
$G$ の任意の辺 $e$ について、 $\overline{\chi}(G,\lambda) = \overline{\chi}(G \backslash e,\lambda) + \overline{\chi}(G/e,\lambda)$

以上の式が成り立てば、示したい (**) が帰納的に成立することが少し考えれば分かります。

$G/e$ は頂点数が $G$ より 1 小さいので 3 の符号が反転していることに注意してください。

1 と 2 については前の章と全く同じです。

ここでもやはり 3 が難しいです。

$e = \{u, v\}$ とします。

まず、 $G$ の正しい組について、向き付けの $e$ を取り除いたものは $G \backslash e$ において正しい組になっています。

逆を考えます。

$(\sigma,O)$ を $G \backslash e$ の正しい組とします。

$\sigma$ は $G$ の彩色にもなっていることを注意してください。

$G$ の向き付けとして、 $O$ に $u \rightarrow v$ を加えたもの $O_1$ と $O$ に $v \rightarrow u$ を加えたもの $O_2$ を考えます。

$(\sigma, O_1)$ と $(\sigma, O_2)$ の少なくとも一方は $G$ の正しい組であって、どちらもが正しいような場合はちょうど $\overline{\chi}(G/e,\lambda)$ 通りであることを示します。

(i) $\sigma(u) > \sigma(v)$ のとき

このとき $e$ の向きから $O_2$ は $\sigma$ に適合しません。

一方、 $O_1$ は適合し、サイクル $v \rightarrow w_1 \rightarrow ... \rightarrow u \rightarrow v$ があったとすると、 $\sigma(v) \ge \sigma(w_1) \ge ... \ge \sigma(u) > \sigma(v)$ と矛盾が生じるので、サイクルはありません。

よって、この場合は $O_1$ のみが正しい向き付けです。

(ii) $\sigma(v) > \sigma(u)$ のとき

この場合は (i) と同様に $O_2$ のみが正しい向き付けです。

(iii) $\sigma(u) = \sigma(v)$ のとき

この場合は、 $O_1$ と $O_2$ の両方が $\sigma$ に適合します。

仮に $O_1$ と $O_2$ の両方がサイクルを生じるとします。

それぞれのサイクルを $v \rightarrow w_1 \rightarrow ... \rightarrow u \rightarrow v$ と $u \rightarrow w'_1 \rightarrow ... \rightarrow v \rightarrow u$ とすると、 $G \backslash e$ と $O$ において、 $v \rightarrow w_1 \rightarrow ... \rightarrow u \rightarrow w'_1 \rightarrow ... \rightarrow v$ というサイクルが生じてしまいます。（頂点は重複してしまうかもしれませんが特に問題ないことがわかります。）

これは、 $O$ がサイクルを生じないという仮定と矛盾するので、 $O_1$ と $O_2$ の少なくとも一方はサイクルを生じず、正しい向き付けとなります。

(iii) においてどちらも正しい向き付けとなるような場合が $\overline{\chi}(G/e,\lambda)$ 通りであることを示します。

$(\sigma,O_1)$ と $(\sigma,O_2)$ がどちらも $G$ において正しい組となるような $(\sigma,O)$ と $G / e$ の正しい組は一対一に対応することが以下のように分かります。

$G / e$ の彩色 $\sigma'$ として、 $u$ と $v$ を縮約してできた頂点の値を $\sigma(u) ( = \sigma(v) )$ とし、それ以外の頂点を $\sigma$ と同じ値としたものをとります (***)。

$e$ をどちらの向きにしても $O$ は $G$ でサイクルは生じないので、 $O$ は $G / e$ でサイクルを生じません。

また、 $O$ が $G \backslash e$ で $\sigma$ に適合してるので、 $G / e$ では $\sigma'$ に適合しています。

よって、 $(\sigma', O)$ は $G / e$ において正しい組であることがわかります。

逆に、 $G / e$ の正しい組 $(\sigma',O)$ をとり、 $\sigma'$ に(***) の逆の対応をさせた $\sigma$ を考えると、 $O$ は $G \backslash e$ で $\sigma$ に適合しています。

$O$ が $G / e$ でサイクルを生じないので、 $e$ をどちらの向きにしても $G$ でサイクルは生じません。

よって、重複して数えなければならない場合が $\overline{\chi}(G/e,\lambda)$ の要素と一対一に対応し、 $\overline{\chi}(G,\lambda) = \overline{\chi}(G \backslash e,\lambda) + \overline{\chi}(G/e,\lambda)$ となることが分かります。

以上より示されました。

$\lambda = 1$ のときを考えると、向き付けが正しいことと、サイクルが生じないことが同値なので、無向グラフの Acyclic Orientation の数は $\overline{\chi}(G,1) = (-1)^{N} \chi(G,-1)$ となることが分かります。