比較可能グラフ(comparability graph)とは、有限半順序集合の元を頂点とし、比較できる 2 元を辺で結んだグラフであり、各辺に向きを付けて $a\to b$ と $b\to c$ からいつも $a\to c$ が従うようにできる(推移的に向き付けられる)グラフと同じである。Gilmore と Hoffman の定理により、比較可能グラフであることは、奇数長のどの閉じた歩道も 1 つおきの 2 頂点を結ぶ辺(三角の弦)をもつことと同値であり、向きの強制を同値類(含意類)にまとめれば、どの弧も逆向きの弧と同じ類に入らないこととも同値である。二部グラフ、$P_4$ を含まないグラフ、区間グラフの補グラフは比較可能グラフで、長さ 5 以上の奇閉路と三角柱は比較可能グラフでなく、比較可能グラフとその補グラフはパーフェクトである。
比較可能グラフ(comparability graph)とは、有限の半順序集合の元を頂点とし、比較できる 2 元を辺で結んだグラフのことである。言い換えると、各辺に向きを付けて、$a\to b$ と $b\to c$ があればいつも $a\to c$ もあるようにできるグラフ(推移的に向き付けられるグラフ)である。
辺の向きを 1 本決めると、ほかの辺の向きが次々に強制される。$a\to b$ と向けた辺 $ab$ の隣に、$a$ と隣接しない $c$ で辺 $bc$ があれば、$b\to c$ とすると推移性から辺 $ac$ が要るので、$c\to b$ と向けるしかない。Gilmore と Hoffman は、この強制が矛盾を生まないことが推移的に向き付けられるための条件であることを、奇数長の閉路の「三角の弦」の言葉で示した(GH64 Theorem 1, p. 540)。この記事では、強制される向きを同値類にまとめてこの特徴づけを証明する。
| 問い | 答え |
|---|---|
| 何のグラフか | 有限半順序集合の比較可能な対を辺とするグラフ |
| 判定法 | 三角の弦のない奇数長の閉じた歩道がないこと(thm-cmp-main) |
| 例 | 二部グラフ、完全グラフ、$P_4$ を含まないグラフ、区間グラフの補グラフ |
| 例でないもの | $C_5$ などの長さ $5$ 以上の奇閉路、三角柱($C_6$ の補グラフ) |
| 性質 | 誘導部分グラフで閉じる。パーフェクトで、補グラフもパーフェクト |
この記事のグラフは、頂点が有限個の単純グラフ $G=(V,E)$ とする。相異なる $u,v$ が隣接することを $uv\in E$ と書く。
比較可能グラフの定義は 区間グラフ の記事の定義と同じである。$\prec$ があれば $T=\{(u,v)\mid u\prec v\}$ は推移的向き付けであり、逆に推移的向き付け $T$ があれば、$u\prec v\iff(u,v)\in T$ は狭義半順序である(非反射性は辺がループでないこと、$(u,v),(v,u)$ が同時に $T$ に入らないことは向き付けであることによる)。したがって 比較可能グラフであることと、推移的向き付けをもつことは同値である。狭義半順序を部分集合に制限すれば狭義半順序なので、比較可能グラフの誘導部分グラフは比較可能グラフである。
向きの強制を表す関係を導入する。$G$ の弧の全体を $\vec E=\{(u,v)\mid uv\in E\}$ とする。
弧 $(a,b),(a',b')\in\vec E$ について、
$$
a=a',\ b\ne b',\ bb'\notin E\quad\text{または}\quad b=b',\ a\ne a',\ aa'\notin E
$$
のとき $(a,b)\,\Gamma\,(a',b')$ と書く。$\Gamma$ で結ばれる弧を次々にたどって移れることで定まる $\vec E$ の同値関係を $\Gamma^*$ と書き、その同値類を 含意類 と呼ぶ(この記事での呼び名)。含意類 $A$ に対して $A^{-1}=\{(v,u)\mid(u,v)\in A\}$ も含意類である。
$(a,b)\,\Gamma\,(a,b')$ は「$a$ から出る 2 本の弧で、先の 2 頂点が隣接しない」ことを、$(a,b)\,\Gamma\,(a',b)$ は「$b$ に入る 2 本の弧で、元の 2 頂点が隣接しない」ことを表す。どちらも $a,b,b'$(または $a,a',b$)が誘導された道 $P_3$ をなす場合である。$\Gamma$ は対称なので $\Gamma^*$ は同値関係であり、$(a,b)\,\Gamma\,(a',b')$ と $(b,a)\,\Gamma\,(b',a')$ は同値なので $A^{-1}$ も含意類である。
$k\ge3$ とする。頂点の列 $v_0,v_1,\dots,v_{k-1}$ で、添字を $k$ を法として $v_iv_{i+1}\in E$($0\le i\le k-1$)となるものを、長さ $k$ の 閉じた歩道 という。同じ頂点が何度現れてもよい。辺 $v_iv_{i+2}$($0\le i\le k-1$、添字は $k$ を法とする)を、この歩道の 三角の弦 という。
$v_i=v_{i+2}$ のときは $v_iv_{i+2}$ は辺でない(ループはない)ので三角の弦ではない。長さ $3$ の閉じた歩道は三角形で、その辺 $v_0v_2$ が三角の弦になる。
道 $P_4$ を誘導部分グラフに含まないグラフは比較可能グラフである。
頂点数 $n$ についての帰納法による。$n=1$ なら明らかである。$n\ge2$ なら、誘導部分グラフ の記事の定理「$P_4$-free なグラフの分解」により、$G$ か $\overline G$ が連結でない。$V$ を空でない $V_1,V_2$ に分け、$G$ が連結でない場合は $V_1$ と $V_2$ の間に辺がなく、$\overline G$ が連結でない場合は $V_1$ と $V_2$ の間のすべての対が $G$ で隣接するようにできる。$G[V_1],G[V_2]$ は $P_4$ を含まないので、帰納法の仮定により推移的向き付け $T_1,T_2$ をもつ。前者の場合は $T_1\cup T_2$ が、後者の場合は $T_1\cup T_2\cup(V_1\times V_2)$($V_1$ の頂点から $V_2$ の頂点へすべて向ける)が $G$ の推移的向き付けである。後者の推移性は、$(a,b),(b,c)$ の 3 頂点が $V_1,V_2$ のどちらにあるかで場合を分ければ確かめられる:$a,b,c$ が同じ側なら $T_i$ の推移性、$a\in V_1$、$c\in V_2$ なら $(a,c)\in V_1\times V_2$ であり、それ以外の場合($a,c$ が同じ側で $b$ が反対側にある場合と、$a\in V_2$、$c\in V_1$ の場合)は、$(a,b),(b,c)$ のどちらかが $V_2$ から $V_1$ への弧になるが、そのような弧はないので起こらない。$\square$
三角柱では、同じ頂点を 2 度通らない奇閉路(長さ $3$ と $5$)はどれも三角の弦をもつ。たとえば $a_1a_2b_2b_3b_1$ は弦 $b_2b_1$ をもつ。三角の弦のない奇数長の閉じた歩道は、どれかの頂点を 2 度以上通る。GH64 の閉路も同じ頂点を何度か通ることを許している(pp. 539–540。同じ向きの辺を 2 度たどることは除く)。
主定理(thm-cmp-main)は、比較可能グラフであること、含意類が逆向きと交わらないこと、三角の弦のない奇数長の閉じた歩道がないことの同値である。1 と 3 の同値は、閉路の範囲の違い(ex-cmp-non の後の注意)を除けば GH64 の Theorem 1(p. 540、無限グラフも含む)にあたり、その十分性の証明は「強い道」で結ばれる辺に順に向きを付ける算法による。この記事の証明は別の道をとり、含意類の性質を 4 つの補題にまとめ、頂点の個数と辺の本数についての帰納法で推移的向き付けを組み立てる。
$T$ を $G$ の推移的向き付けとする。$(a,b)\in T$ かつ $(a,b)\,\Gamma\,(a',b')$ なら $(a',b')\in T$ である。したがって各含意類 $A$ について $A\subset T$ か $A\cap T=\emptyset$ である。
$a=a'$、$bb'\notin E$ の場合:$(b',a)\in T$ とすると、$(b',a),(a,b)\in T$ と推移性から $(b',b)\in T$ となり、$bb'\in E$ に反する。よって $(a,b')\in T$ である。$b=b'$、$aa'\notin E$ の場合も同様に、$(b,a')\in T$ なら $(a,b),(b,a')$ から $aa'\in E$ となって矛盾する。後半は前半を $\Gamma$ の鎖に沿って繰り返せばよい。$\square$
$a,b,c$ を互いに隣接する 3 頂点とし、$(b,c)$、$(a,b)$、$(a,c)$ の含意類をそれぞれ $A$、$C$、$B$ とする。$A\ne B$ かつ $A\ne C^{-1}$ なら、$A$ のすべての弧 $(x,y)$ について、$a\notin\{x,y\}$、$ax,ay\in E$、$(a,x)\in C$、$(a,y)\in B$ が成り立つ。
弧 $(x,y)$ についての主張を $P(x,y)$ と書く。$P(b,c)$ は仮定である。$A$ の弧は $(b,c)$ から $\Gamma$ を 1 歩ずつたどって得られるので、$P(x,y)$ と $(x,y)\,\Gamma\,(x',y')$ から $P(x',y')$ を示せばよい。
$x'=x$、$y\ne y'$、$yy'\notin E$ の場合。 $a$ は $y$ に隣接し $y'$ は $y$ に隣接しないので $a\ne y'$ である。$ay'\notin E$ とすると、$(a,x)\,\Gamma\,(y',x)$($x$ に入る 2 本の弧で、$a,y'$ は隣接しない)より $(y',x)\in C$、すなわち $(x,y')\in C^{-1}$ となる。$(x,y')\in A$ なので $A=C^{-1}$ となり仮定に反する。よって $ay'\in E$ であり、$(a,y)\,\Gamma\,(a,y')$ から $(a,y')\in B$ である。
$y'=y$、$x\ne x'$、$xx'\notin E$ の場合。 同様に $a\ne x'$ である。$ax'\notin E$ とすると $(a,y)\,\Gamma\,(x',y)$ より $(x',y)\in B$ となり、$(x',y)\in A$ から $A=B$ で仮定に反する。よって $ax'\in E$ であり、$(a,x)\,\Gamma\,(a,x')$ から $(a,x')\in C$ である。$\square$
どの含意類 $A$ も $A\cap A^{-1}=\emptyset$ をみたすとき、各含意類 $A$ は推移的である。すなわち $(a,b),(b,c)\in A$ なら $(a,c)\in A$ である。
$(a,b),(b,c)\in A$ とする。$a=c$ なら $(a,b),(b,a)\in A$ となり仮定に反するので $a\ne c$ である。$ac\notin E$ なら $(a,b)\,\Gamma\,(c,b)$ から $(c,b)\in A$ となり、$(b,c)\in A$ と合わせて仮定に反する。よって $ac\in E$ である。$(a,c)$ の含意類 $B$ が $A$ と異なるとすると、三角形 $a,b,c$ に lem-cmp-triangle を $C=A$ として当てられる($A\ne B$、$A\ne A^{-1}=C^{-1}$)。すると $a$ は $A$ のどの弧の端点でもないが、$(a,b)\in A$ に反する。よって $(a,c)\in A$ である。$\square$
含意類 $A$ の弧の端点の全体を $V(A)$ と書く。$V(A^{-1})=V(A)$ である。
任意の含意類 $A$ と、$V(A)$ に属さない頂点 $z$ について、$z$ は $V(A)$ のすべての頂点に隣接するか、どの頂点にも隣接しない。
$\Gamma$ で結ばれる 2 本の弧は端点を共有するので、$A$ の弧の辺を道に並べて $V(A)$ のどの 2 頂点も結べる。$z$ が $u\in V(A)$ に隣接し $w\in V(A)$ に隣接しないとすると、その道の上で隣り合う $u',w'$($u'w'$ は $A$ か $A^{-1}$ の弧の辺)で、$z$ が $u'$ に隣接し $w'$ に隣接しないものがある。$(w',u')$ が $A$ か $A^{-1}$ の弧であり、$z\ne w'$、$zw'\notin E$ なので $(w',u')\,\Gamma\,(z,u')$ となり、$(z,u')$ も同じ含意類に入る。これは $z\notin V(A)$ に反する。$\square$
有限グラフ $G$ について、次は同値である。
1 ⇒ 2。 推移的向き付け $T$ をとる。弧 $(a,b)$ と $(b,a)$ が同じ含意類 $A$ に入るとする。$T$ は $(a,b),(b,a)$ のちょうど一方を含むので $A\cap T\ne\emptyset$ であり、lem-cmp-forcing から $A\subset T$ となって、$(a,b),(b,a)$ がともに $T$ に入る。これは向き付けであることに反する。
2 と 3 の言い換え。 頂点の列 $v_0,v_1,v_2,\dots$ で、隣り合う 2 頂点が隣接し、各 $i$ について $v_i=v_{i+2}$ か $v_iv_{i+2}\notin E$ となるものに対し、弧を交互の向きに読んで
$$
\alpha_i=(v_i,v_{i+1})\ (i\ \text{が偶数}),\qquad \alpha_i=(v_{i+1},v_i)\ (i\ \text{が奇数})
$$
とおく。$i$ が偶数なら $\alpha_i,\alpha_{i+1}$ は $v_{i+1}$ に入る 2 本の弧、奇数なら $v_{i+1}$ から出る 2 本の弧で、もう一方の端点 $v_i,v_{i+2}$ は一致するか隣接しない。よって $\alpha_i=\alpha_{i+1}$ か $\alpha_i\,\Gamma\,\alpha_{i+1}$ である。
2 ⇒ 3。 三角の弦のない奇数長 $k$ の閉じた歩道 $v_0,\dots,v_{k-1}$ があるとし、添字を $k$ を法として列を延ばす。三角の弦がないので上の条件がみたされ、$\alpha_0\,\Gamma^*\,\alpha_k$ である。$k$ は奇数なので $\alpha_k=(v_{k+1},v_k)=(v_1,v_0)$ は $\alpha_0=(v_0,v_1)$ の逆向きであり、2 が成り立たない。
3 ⇒ 2。 弧 $(a,b)$ と $(b,a)$ が同じ含意類に入るとし、$\Gamma$ の鎖 $(a,b)=\beta_0\,\Gamma\,\beta_1\,\Gamma\cdots\Gamma\,\beta_m=(b,a)$ をとる。$v_0=a$、$v_1=b$ から始めて、$\beta_j$ を順に $\alpha_i$ として読めるように列を延ばす。$\alpha_i$ の次は、$i$ が偶数なら $v_{i+1}$ に入る弧、奇数なら $v_{i+1}$ から出る弧として読まれる。$\beta_j\,\Gamma\,\beta_{j+1}$ が共有する端点がこの読み方に合っていれば $v_{i+2}$ を $\beta_{j+1}$ のもう一方の端点とし、合っていなければ先に $v_{i+2}=v_i$ と 1 歩戻ってから($\alpha_{i+1}=\alpha_i$)同じことをする。最後に $(b,a)$ が偶数番目 $\alpha_j=(v_j,v_{j+1})$ として読まれたら、さらに $v_{j+2}=v_j$ と 1 歩戻る。こうして奇数 $j$ で $\alpha_j=(v_{j+1},v_j)=(b,a)$、すなわち $v_j=a=v_0$、$v_{j+1}=b=v_1$ となる。$v_1=b\ne a$ なので $j\ge3$ である。$v_0,\dots,v_{j-1}$ は長さ $j$ の閉じた歩道で、構成から各 $i$ について $v_i=v_{i+2}$ か $v_iv_{i+2}\notin E$ であり、$i=j-2,j-1$ の条件は $v_j=v_0$、$v_{j+1}=v_1$ により閉じた歩道の三角の弦の条件そのものである。よって三角の弦のない奇数長の閉じた歩道があり、3 が成り立たない。
2 ⇒ 1。 $\lvert V\rvert+\lvert E\rvert$ についての帰納法で示す。2 は誘導部分グラフに遺伝する。実際、誘導部分グラフ $H$ の $\Gamma$ の 1 歩は $G$ の $\Gamma$ の 1 歩でもある($H$ の頂点どうしの隣接は $G$ と同じ)ので、$H$ で $(a,b)$ と $(b,a)$ が同じ含意類に入れば $G$ でもそうなる。$E=\emptyset$ なら空の向き付けでよい。$E\ne\emptyset$ とし、含意類 $A$ を 1 つとって $M=V(A)$ とおく。$\lvert M\rvert\ge2$ である。
場合 1:$M\ne V$。 lem-cmp-module により、$M$ の外の頂点は $M$ の全体に隣接するか、どれにも隣接しない。$m_0\in M$ を固定し、$G_1=G[M]$、$G_2=G[(V\setminus M)\cup\{m_0\}]$ とおく。どちらも $G$ より頂点が少なく 2 をみたすので、帰納法の仮定から推移的向き付け $T_1,T_2$ をもつ。$\varphi(x)$ を $x\in M$ なら $m_0$、そうでなければ $x$ とし、$G$ の辺 $xy$ を、$x,y\in M$ なら $T_1$ に従って、そうでなければ $(\varphi(x),\varphi(y))\in T_2$ のときに $x\to y$ と向ける($\varphi(x)\varphi(y)$ は $G_2$ の辺である)。これを $T$ とする。$(x,y),(y,z)\in T$ とする。$T$ は向き付けなので $x\ne z$ である。
場合 2:$M=V$。 $\hat A=A\cup A^{-1}$ の辺を除いたグラフを $G'$ とする。$G'$ は頂点が同じで辺が少ない。
(a) $G'$ の含意類は、$G$ の含意類のうち $A,A^{-1}$ 以外のものと一致する。$G'$ の $\Gamma$ の 1 歩 $(p,x)\,\Gamma'\,(p,y)$ で $xy\in E$ となるものがあったとする($p$ に入る弧の場合も同様)。$xy\notin E'$ なので $xy\in\hat A$ であり、$px,py\notin\hat A$ である。三角形 $p,x,y$ の $(x,y)$ の含意類 $X\in\{A,A^{-1}\}$ は $(p,x),(p,y)$ の含意類 $C,B\notin\{A,A^{-1}\}$ と異なり、$X\ne C^{-1}$ でもある。lem-cmp-triangle により $p$ は $X$ の弧の端点にならず、$p\notin V(X)=V(A)=V$ となって矛盾する。よって $\Gamma'$ の 1 歩は $G$ の $\Gamma$ の 1 歩であり、逆に $\hat A$ に入らない弧の間の $\Gamma$ の 1 歩は $\Gamma'$ の 1 歩である。$A,A^{-1}$ 以外の含意類は $\Gamma$ で閉じているので、主張が従う。とくに $G'$ は 2 をみたし、帰納法の仮定から推移的向き付け $T'$ をもつ。
(b) $T=T'\cup A$ が $G$ の推移的向き付けであることを示す。$A\cap A^{-1}=\emptyset$ なので $A$ は $\hat A$ の各辺の一方の向きをちょうど含み、$T$ は向き付けである。$(x,y),(y,z)\in T$ とする。両方が $A$ にあれば lem-cmp-class により、両方が $T'$ にあれば $T'$ の推移性による。$(x,y)\in A$、$(y,z)\in T'$ とする。$xz\notin E$ なら $(x,y)\,\Gamma\,(z,y)$ から $(z,y)\in A$ となり $yz\notin\hat A$ に反するので、$xz\in E$ である。$(z,x)\in A$ なら lem-cmp-class から $(z,y)\in A$ となって同じく矛盾する。$(x,z)\in A$ ならよい。$xz\notin\hat A$ なら、$G'$ では $x,y$ が隣接しないので $(y,z)\,\Gamma'\,(x,z)$ であり、lem-cmp-forcing を $G'$ と $T'$ に当てて $(x,z)\in T'$ である。$(x,y)\in T'$、$(y,z)\in A$ の場合も、向きを逆にして同じ議論で $(x,z)\in T$ が得られる。$\square$
証明は、含意類を 1 つ選んで向きを決め、その辺を除くか $M$ を 1 点に縮めるかして残りに同じことを繰り返す手続きになっている。$A$ の代わりに $A^{-1}$ を選んでもよい。
要点:$P_4$ では含意類が 2 つで、その一方がそのまま推移的向き付けになる。$K_3$ では 6 本の弧がばらばらの含意類で、勝手に選ぶと推移的でなくなる。$C_5$ では $(0,1)$ と $(1,0)$ が同じ含意類に入る。
道 $P_4$($1-2-3-4$):$(1,2)\,\Gamma\,(3,2)\,\Gamma\,(3,4)$ で、含意類は $A=\{(1,2),(3,2),(3,4)\}$ と $A^{-1}$ である。$A$ は $1\to2\leftarrow3\to4$ という推移的向き付けである。
三角形 $K_3$:どの 2 頂点も隣接するので $\Gamma$ の 1 歩はない。$V(A)$ は 2 頂点で、証明の場合 1 が使われる。$1\to2\to3\to1$ と選ぶと推移的でないので、選んだ含意類の辺を除くか縮めるかして選び直す手順が要る。
$C_5$($0-1-2-3-4-0$):$\alpha_i$ の列 $(0,1),(2,1),(2,3),(4,3),(4,0),(1,0)$ が $\Gamma$ でつながる。
比較可能グラフ $G$ の半順序では、クリークは鎖、独立集合は反鎖である。パーフェクトグラフ定理 の記事の系「Mirsky の定理から Dilworth の定理へ」により、比較可能グラフはパーフェクトで、補グラフもパーフェクトである。$\chi(G)=\omega(G)$ は元を反鎖に分ける最小の個数が最長の鎖の長さに等しいこと(Mirskyの定理)、$\chi(\overline G)=\omega(\overline G)$ は元を鎖に分ける最小の個数が最大の反鎖の大きさに等しいこと(Dilworthの定理)にあたる。推移的向き付けが 1 つ分かれば最長の鎖は最長の有向道として求まるので、クリーク数と彩色数は向き付けから計算できる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-cmp-main の 3 で、同じ頂点を何度通ってもよいこと(単純な奇閉路に限る) | 三角柱 | 単純な奇閉路はすべて三角の弦をもつが、比較可能グラフでない |
| thm-cmp-main の 3 で、長さが奇数であること | $C_4$ | 比較可能グラフだが、閉じた歩道 $0,1,2,3$ は三角の弦をもたない |
| lem-cmp-class の仮定(2) | $C_5$ | $(0,1),(1,2)$ は同じ含意類に入るが、$02$ は辺でない |
| $P_4$ を含まないこと(prop-cmp-cograph) | $C_5$ | 比較可能グラフでない |
要点:各行で左の条件だけが外れていることを確かめる。
1 行目は ex-cmp-non の 2 とその後の注意による。長さ $5$ の単純な閉路は、三角柱から 1 頂点を除いた 5 頂点(三角形 1 つと辺 1 本)の中にあり、どれも三角形の辺を 2 本以上含むので三角の弦をもつ。
2 行目:$C_4$ は二部グラフなので比較可能グラフであり(ex-cmp-basic の 2)、$0$ と $2$、$1$ と $3$ は隣接しない。
3 行目:ex-cmp-classes の $C_5$ の列を 1 歩延ばすと $(1,0)\,\Gamma\,(1,2)$($0,2$ は隣接しない)なので、$(1,2)$ も $(0,1)$ と同じ含意類に入る。
4 行目:$0,1,2,3$ が誘導された $P_4$ をなし、比較可能グラフでないことは ex-cmp-non の 1 による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する