比較可能グラフ

同義語:comparability graph推移的に向き付け可能なグラフtransitively orientable graph

概要

比較可能グラフ(comparability graph)とは、有限半順序集合の元を頂点とし、比較できる 2 元を辺で結んだグラフであり、各辺に向きを付けて $a\to b$ と $b\to c$ からいつも $a\to c$ が従うようにできる(推移的に向き付けられる)グラフと同じである。Gilmore と Hoffman の定理により、比較可能グラフであることは、奇数長のどの閉じた歩道も 1 つおきの 2 頂点を結ぶ辺(三角の弦)をもつことと同値であり、向きの強制を同値類(含意類)にまとめれば、どの弧も逆向きの弧と同じ類に入らないこととも同値である。二部グラフ、$P_4$ を含まないグラフ、区間グラフの補グラフは比較可能グラフで、長さ 5 以上の奇閉路と三角柱は比較可能グラフでなく、比較可能グラフとその補グラフはパーフェクトである。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 半順序集合, 誘導部分グラフ, 補グラフ

比較可能グラフ(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$ と書く。

比較可能グラフと推移的向き付け
  1. $V$ の上の狭義半順序 $\prec$(非反射的かつ推移的な関係)で、相異なる任意の $u,v$ について
    $$ uv\in E\iff u\prec v\ \text{または}\ v\prec u $$
    となるものがあるとき、$G$ を 比較可能グラフ という。補グラフ $\overline G$ が比較可能グラフであるとき、$G$ を 比較不能グラフ(cocomparability graph)という。
  2. $G$ の各辺 $uv$ に向き $u\to v$ か $v\to u$ のちょうど一方を選んだものを 向き付け という。向き付け $T$ を、向きを付けた辺(弧)$(u,v)$ の集合とみる。$(a,b),(b,c)\in T$ ならいつも $(a,c)\in T$ となるとき、$T$ を 推移的向き付け という。

比較可能グラフの定義は 区間グラフ の記事の定義と同じである。$\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$ が三角の弦になる。

例

比較可能グラフの例
  1. 完全グラフ $K_n$ は全順序 $1\prec2\prec\cdots\prec n$ の比較可能グラフである。
  2. 二部グラフ は、部 $X,Y$ について $X$ のすべての頂点から $Y$ の頂点へ向けると、長さ $2$ の有向道がないので推移的向き付けになる。とくに偶数長の閉路 $C_{2k}$ と木は比較可能グラフである。
  3. 区間グラフの補グラフ:区間表現 $(I_v)$ について $u\prec v$ を「$I_u$ が $I_v$ より完全に左にある」で定めると、交わらない区間の対がちょうど比較可能な対になる(区間グラフ の Gilmore–Hoffman の定理の 1 ⇒ 3)。区間グラフは比較不能グラフである。
  4. 置換グラフ:$\{1,\dots,n\}$ の置換 $\pi$ について、$i< j$ かつ $\pi(i)>\pi(j)$ となる対 $\{i,j\}$(反転)を辺とするグラフ $G_\pi$ は、$i\prec j\iff i< j,\ \pi(i)>\pi(j)$ で比較可能グラフになる。$\prec$ が推移的なのは、$i< j< k$、$\pi(i)>\pi(j)>\pi(k)$ から $i< k$、$\pi(i)>\pi(k)$ が従うからである。補グラフの辺は $i< j$ かつ $\pi(i)<\pi(j)$ の対なので、同様に $\overline{G_\pi}$ も比較可能グラフである。
$P_4$ を含まないグラフ

道 $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$

比較可能グラフでないもの
  1. 奇閉路 $C_{2k+1}$($k\ge2$):頂点 $0,1,\dots,2k$ を順にたどる閉じた歩道は、$i$ と $i+2$ が隣接しないので三角の弦をもたない。長さは奇数なので、thm-cmp-main の 3 が成り立たない。
  2. 三角柱:三角形 $a_1a_2a_3$ と $b_1b_2b_3$ に辺 $a_1b_1,a_2b_2,a_3b_3$ を加えた $6$ 頂点のグラフ($C_6$ の補グラフ)。長さ $7$ の閉じた歩道
    $$ a_1,\ a_2,\ b_2,\ b_3,\ a_3,\ a_1,\ b_1 $$
    は三角の弦をもたない($v_0,\dots,v_6$ と番号を付けると、$v_iv_{i+2}$ は $a_1b_2,\ a_2b_3,\ b_2a_3,\ b_3a_1,\ a_3b_1,\ b_1a_2$ で、どれも辺でなく、残る $v_5$ と $v_7=v_0$ はどちらも $a_1$ である)。よって thm-cmp-main により比較可能グラフでない。$C_6$ は二部グラフなので比較可能グラフであり、比較可能グラフの全体は補グラフをとる操作で閉じていない。

三角柱では、同じ頂点を 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. $G$ は比較可能グラフである。
  2. どの弧 $(a,b)$ も、逆向きの弧 $(b,a)$ と同じ含意類に入らない。すなわち、どの含意類 $A$ も $A\cap A^{-1}=\emptyset$ をみたす。
  3. 奇数長のどの閉じた歩道も三角の弦をもつ。

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$ である。

  • 3 頂点がすべて $M$ にあれば、$T_1$ の推移性による。
  • $x,y\in M$、$z\notin M$ なら、$z$ は $y$ に隣接するので $M$ の全体に隣接し、$xz\in E$ である。$(y,z)\in T$ は $(m_0,z)\in T_2$ を意味するので、$(x,z)\in T$ である。$y,z\in M$、$x\notin M$ の場合も同様である。
  • $x,z\in M$、$y\notin M$ なら、$(m_0,y),(y,m_0)\in T_2$ となるので起こらない。
  • 残りの場合は、$(x,y),(y,z)$ のどちらも $M$ の外の端点をもち、$x,z$ の少なくとも一方は $M$ の外にある。よって $(\varphi(x),\varphi(y)),(\varphi(y),\varphi(z))\in T_2$、$\varphi(x)\ne\varphi(z)$ で、$T_2$ の推移性から $(\varphi(x),\varphi(z))\in T_2$ である。$x,z$ の一方だけが $M$ にあるとき、他方は $m_0$ に隣接するので $M$ の全体に隣接する。いずれにしても $xz\in E$ で、$(x,z)\in T$ である。

場合 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 による。

歴史と広がり

  • Gilmore–Hoffman の論文。 GH64 は、比較可能グラフの特徴づけ(Theorem 1, p. 540)と、それを使った区間グラフの特徴づけ(Theorem 2, p. 545)を、無限グラフも含めて与えた。比較可能グラフの特徴づけには別の証明があることも述べている(p. 539)。十分性の証明は、比較可能グラフの辺に推移的な向きを付ける簡単な算法を与える(p. 539)。
  • 区間グラフとの関係。 区間グラフは、弦グラフであって補グラフが比較可能グラフであるものとして特徴づけられる(区間グラフ の Gilmore–Hoffman の定理)。単位区間グラフ の補グラフは、区間が長さ $1$ のときの「完全に左にある」という半順序の比較可能グラフである。
  • 教科書での位置。 Die25 は、比較可能グラフがパーフェクトであることを演習としている(Exercise 43, p. 151)。

関連項目

参考文献

[1]
P. C. Gilmore; A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian Journal of Mathematics, 1964, pp. 539–548(p. 539:別証明と算法への言及、p. 539:閉路の定義、p. 540:三角の弦の定義・Theorem 1、p. 545:Theorem 2)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する