比較可能グラフは理想グラフ

比較可能グラフが理想グラフであることを示します．

比較可能グラフとは？

比較可能グラフは順序集合によって定義される無向グラフなので，まず初めに順序集合から定義します．また，集合 $X$ 上の二項関係を $\le \subseteq X^2$ として，任意の $x,y \in X$ に対して， $(x, y) \in \le$ を $x \le y$ として書くことにします．

集合 $X$ ， $X$ 上の二項関係 $\le$
定義. 順序(order)
$\le$ が順序であるとは次を満たすこと
　1. 反射性(reflexivity) : 任意の $x \in X$ に対して， $x \le x$
　2. 推移性(transitivity) : 任意の $x, y, z \in X$ に対して， $x \le y$ かつ $y \le z$ ならば $x \le z$
　3. 反対称性(antisymmetry) : 任意の $x, y \in X$ に対して， $x \le y$ かつ $y \le x$ ならば $x = y$

組 $P = (X, \le)$ のことを順序集合(ordered set) と呼びます．順序集合の表現方法の1つにネットワーク表現があります．これは， $X$ を頂点集合， $\le$ を弧集合として得られる有向グラフです．

例）順序集合のネットワーク表現
順序集合 $P = (X, \le)$
・　 $X = \{a, b, c, d, e\}$
・　 $\le = \{(a, b), (a, e), (c, b), (c, d), (c, e), (d, e), (a, a), (b, b), (c, c), (d, d), (e, e)\}$
f:id:tatanaideyo:20180504001935p:plain:w300
各頂点には反射性から自己ループが存在し，反対称性から異なる2頂点間の間に異なる2つの弧が存在することはありません．また重要な性質として有向閉路は存在しません．

命題.　順序集合のネットワーク表現に有向閉路は存在しない．

証明：順序集合 $P = (X, \le)$ に有向閉路 $v_0, v_1, \ldots v_k, v_0$ が存在すると仮定する．このとき， $v_0 \le v_1$ かつ $v_1 \le v_2$ から推移性により $v_0 \le v_2$ となり，繰返し行うと任意の $1 \le i \le k$ に対して $x_0 \le v_i$ が成り立つ．よって $v_k \le v_0$ かつ $v_0 \le v_k$ となり反対称性に矛盾する． ❏

順序集合 $P = (X, \le)$ の 比較可能グラフ(comarability graph) とは，無向グラフで $P$ のネットワーク表現から自己ループを取り除き，弧の向き付けを無くして無向辺にしたものです．
上の例の比較可能グラフは次のようになります．
f:id:tatanaideyo:20180504005949p:plain:w300

逆に，無向グラフで推移性と反対称性を満たすような向き付けが存在するとき，その無向グラフを比較可能グラフとして定義する方法もあります．無向グラフが比較可能グラフであるかは多項式時間で判定可能で，もし比較可能グラフであるならばそのような向き付けも多項式時間で与えることができます（本当？）．

理想グラフとは？

理想グラフ(perfect graph)はクリーク数と染色数によって定義されるグラフクラスなので，初めにクリーク数と染色数の説明からしていきます．
無向グラフ $G = (V, E)$ のクリークとは，頂点部分集合 $X \subseteq V$ でどの $X$ の2頂点も辺で隣接しているものをいいます． $G$ のクリークの頂点数の最大値を $G$ のクリーク数と呼び $\omega(G)$ で表します．
次に， $G$ の $k$ 彩色とは，各頂点を $k$ 色の中から1色選び塗り，どの隣接する2頂点も異なる色で塗られているような塗り方のことです． $G$ の $k$ 彩色が存在するような最小の $k$ のことを $G$ の染色数と呼び $\chi(G)$ で表します．
一般の無向グラフでは染色数とクリーク数の間に弱双対性が成り立ちます．すなわち，任意の無向グラフ $G$ に対して， $\omega(G) \le \chi(G)$ となります．ただし，強双対性が成り立つとは限りません（ $\omega(G) < \chi(G)$ となるグラフ $G$ が存在する）．強双対性が成り立つグラフクラスに二部グラフなどがあるのですが，理想グラフはそれよりも強い性質が成り立つグラフクラスとして定義されます．弱双対性の証明が気になる方は [1] を参照してください．

無向グラフ $G = (V, E)$
定義. 理想グラフ(perfect graph)
$G$ が理想グラフであるとは，任意の $X \subseteq V$ に対して， $\omega(G[X]) = \chi(G[X])$ が成り立つことである
ここで， $G[X]$ は $X$ によって誘導される部分グラフのことである．

比較可能グラフは理想グラフ

ここでは任意の比較可能グラフが理想グラフであることを証明します．比較可能グラフはその向き付けも与えられているものとして同一視して証明していきます．ここでの証明は [2] を参考にしています．

比較可能グラフ $G = (V, E)$ ， $X \subseteq V$
補題1.　 $X$ が有向道であるための必要十分条件は $X$ がクリークであること
証明： $\Rightarrow)$ $X$ の有向道を $v_1, v_2, \ldots, v_{|X|}$ とする．このとき，比較可能グラフの推移性から任意の $1 \le i < j \le |X|$ に対して， $v_i v_j \in E$ となる．したがって， $X$ は $G$ のクリークである．
$\Leftarrow)$ $G$ はDAG(有向閉路が存在しない)なので $G[X]$ において入次数0の頂点が存在する．それを $v_1 \in X$ とし，ある $i < |X|$ に対して，帰納的に $X_i = v_1, \ldots , v_i$ が有向道であるとする．ここで， $G[X - X_i]$ において $G$ がDAGであることから，入次数0の頂点が存在してそれを $v \in X - X_i$ とする．このとき， $X$ がクリークであり，帰納法の仮定から $v_i$ を選ぶ時に $G[X - X_{i-1}]$ において $v_i$ は入り次数が0であることから， $v_i v \in E$ となる．したがって， $v_1, \ldots, v_i, v$ は有向道となる． ❏

各頂点 $v \in V$ に対して， $L(v)$ を $v$ を始点とする最長有向道の長さとする．このとき次の補題が成り立つ．

比較可能グラフ $G = (V, E)$ , $u, v \in V$
補題2.　 $L(u) \le L(v) \Rightarrow uv \notin E$
証明 : $uv \in E$ と仮定する． $v$ を始点とする長さ $L(v)$ の任意の有向道 $P = v, v_1, v_2, \ldots, v_k$ を考える．このとき， $u \notin P$ である．もし， $u \in P$ ならば $v, v_1, \ldots, u, v$ として有向閉路が存在し $G$ がDAGであることに矛盾する．したがって， $u \notin P$ となるので，長さ $L(v) + 1$ の有向道 $u, v, v_1, v_2, \ldots, v_k$ が存在する．これは， $L(u) \le L(v)$ に矛盾するので補題が成り立つ．

系. 　 $L(u) = L(v) \Rightarrow uv \notin E$ かつ $vu \notin E$
証明 : 仮定から $L(u) \le L(v)$ かつ $L(u) \ge L(v)$ となり，補題2から $uv \notin E$ かつ $vu \notin E$ となる．　❏

定理.　比較可能グラフは理想グラフである
証明 : $G = (V, E)$ を比較可能グラフとして，頂点部分集合 $X \subseteq V$ を考える．
$X$ を $L$ によって分割する．すなわち， $C_i = \{v \in X \mid L(v) = i\}$ として， $X$ の分割を $\mathcal{C} = (C_1, C_2, \ldots, C_k)$ とする．このとき，補題1から $G[X]$ の最長有向道の長さとクリーク数が等しくなるので $k = \omega(G[X])$ となる．また，系から各 $C_i$ の頂点間に辺が存在しないので $C_i$ の頂点を同じ色で塗ると $\omega(G[X])$ 彩色が得られる．したがって， $\omega(G[X]) \ge \chi(G[X])$ となる．
染色数とクリーク数の弱双対性から $\omega(G[X]) \le \chi(G[X])$ となるので， $\omega(G[X]) = \chi(G[X])$ となる．　❏

まとめ

比較可能グラフの向き付けが与えられているときに， $L(v)$ の計算は動的計画法で $L(v) = \max\{L(u) + 1 \mid vu \in E\}$ として線形時間で計算することができます．したがって，補題1と定理から比較可能グラフのクリーク数と染色数が線形時間で求めることができます．
性質から良いアルゴリズムが設計できるのは良いですね．

参考文献

[1] 岡本吉央. ``グラフとネットワーク第10回彩色：数理'' , http://dopal.cs.uec.ac.jp/okamotoy/lect/2017/gn/lect10.pdf (2018年5月4日アクセス)
[2] Amit Kumar. ``Lecture3: Comparability Graphs'',
http://www.cse.iitd.ernet.in/~naveen/courses/CSL851/arpit.pdf (2018年5月4日アクセス)