単位区間グラフ(unit interval graph)とは、実数直線の長さ 1 の閉区間の有限族の交差グラフ、すなわち頂点に実数を対応させて差が 1 以下の 2 頂点を結んだグラフである。Roberts の定理により、単位区間グラフであることは、どの区間も他の区間を真に含まない区間表現をもつこと(固有区間グラフ)とも、爪 $K_{1,3}$ を誘導部分グラフに含まない区間グラフであることとも同値であり、さらに各頂点の閉近傍が連続するような頂点の並べ方をもつこととも同値である。この並べ方では極大クリークが連続な区間として読み取れる。爪は区間グラフだが単位区間グラフでなく、三角形の各頂点に葉を 1 つずつ付けた網は爪を含まない弦グラフだが区間グラフでない。
単位区間グラフ(unit interval graph)とは、実数直線の長さ $1$ の閉区間を頂点とし、交わる 2 つの区間を辺で結んだグラフのことである。各頂点に実数 $x_v$ を対応させ、$\lvert x_u-x_v\rvert\le1$ のときに辺を結んだグラフと言っても同じである。差が $1$ 以下の 2 つの値を「区別できない」とみる見方から、無差別グラフ(indifference graph)とも呼ばれる。
区間グラフ のうち、どの区間も他の区間を真に含まないように表せるものを 固有区間グラフ という。区間の長さをそろえることは、一見すると包含を避けることよりずっと強い要請に見える。しかし Roberts(1969)は、単位区間グラフ・固有区間グラフ・爪 $K_{1,3}$ を誘導部分グラフに含まない区間グラフの 3 つが同じクラスであることを示した(BW99 p. 1 の紹介による)。この記事では、極大クリークの並べ方を使ってこの定理を証明し、頂点の並べ方による 4 つ目の特徴づけを与える。
| 問い | 答え |
|---|---|
| 何のグラフか | 長さ $1$ の閉区間の有限族の交差グラフ |
| 同じクラス | 固有区間グラフ、爪を含まない区間グラフ(Roberts の定理) |
| 頂点の並べ方 | 各頂点の閉近傍が並べ方の中で連続するように並べられる |
| 例 | 道、完全グラフ、それらの非交和 |
| 例でないもの | 爪 $K_{1,3}$(区間グラフ)、$C_4$(爪を含まない)、網(弦グラフで爪を含まない) |
この記事のグラフは、頂点が有限個の単純グラフ $G=(V,E)$ とする。相異なる $u,v$ が隣接することを $uv\in E$ と書き、$N[v]$ を $v$ とその隣接頂点の集合(閉近傍)とする。区間表現・誘導部分グラフ・極大クリークの用語は 区間グラフ の記事に従う。閉区間 $I,J$ について、$I\subsetneq J$ のとき $J$ は $I$ を 真に含む という。
グラフ $G$ の区間表現 $(I_v)_{v\in V}$ について、
異なる頂点に同じ区間を対応させてもよい。長さの等しい閉区間 $[a,a+1]\subset[b,b+1]$ なら $a=b$ なので、単位区間表現は固有区間表現であり、単位区間グラフは固有区間グラフである。また $x_v$ を $I_v=[x_v,x_v+1]$ の左端とすれば、
$$
[x_u,x_u+1]\cap[x_v,x_v+1]\ne\emptyset\iff\lvert x_u-x_v\rvert\le1
$$
なので、単位区間グラフであることは、相異なる $u,v$ について $uv\in E\iff\lvert x_u-x_v\rvert\le1$ となる実数 $(x_v)_{v\in V}$ があることと同じである。区間表現を誘導部分グラフに制限すれば長さも包含も保たれるので、どちらのクラスも誘導部分グラフをとる操作で閉じている。
中心 $c$ と、互いに隣接しない 3 頂点 $x,y,z$ からなり、辺が $cx,cy,cz$ だけのグラフ $K_{1,3}$ を 爪(claw)という。$K_{1,3}$ と同型な誘導部分グラフをもたないグラフを 爪を含まない(claw-free)グラフという。
主定理の 4 つ目の条件は、頂点の並べ方の言葉で述べられる。
$G$ の頂点の並べ方 $v_1,v_2,\dots,v_n$ が、
$$
i< j< k\ \text{かつ}\ v_iv_k\in E\ \Longrightarrow\ v_iv_j\in E\ \text{かつ}\ v_jv_k\in E
$$
をみたすとき、これを 近傍の連続な並べ方 と呼ぶ(この記事での呼び名)。
名前の由来は次の言い換えにある。並べ方が近傍の連続な並べ方であることと、各頂点 $v_j$ の閉近傍 $N[v_j]$ が並べ方の中で連続する(ある $p\le j\le q$ について $N[v_j]=\{v_p,\dots,v_q\}$ となる)ことは同値である。 実際、条件があるとき、$k>j$ で $v_jv_k\in E$ なら、$j< l< k$ の $v_l$ に条件($i=j$ の場合)を当てて $v_jv_l\in E$ であり、左側も同様である。逆に閉近傍がすべて連続なら、$i< j< k$、$v_iv_k\in E$ のとき、$N[v_i]$ は $v_i,v_k$ を含むので $v_j$ を含み、$N[v_k]$ も $v_i,v_k$ を含むので $v_j$ を含む。
1:単位区間表現 $x_c,x_x,x_y,x_z$ があるとする。$x,y,z$ は $c$ に隣接するので $x_x,x_y,x_z\in[x_c-1,x_c+1]$ であり、互いに隣接しないのでどの 2 つの差も $1$ より大きい。小さい順に $s< t< u$ と並べると $u-s=(u-t)+(t-s)>2$ となり、長さ $2$ の区間に入ることに反する。
2:$C_4$ の各頂点の隣接頂点は互いに隣接しないが 2 個しかないので、爪の中心になれない。区間グラフでないことは 区間グラフ の Gilmore–Hoffman の定理(弦グラフであることが必要)による。
3:爪の中心は互いに隣接しない 3 頂点に隣接する必要がある。次数が $3$ 以上の頂点は $a_i$ だけで、その隣接頂点のうち 2 つ $a_j,a_k$ は隣接する。よって爪を含まない。区間表現 $(I_v)$ があるとする。$p_1,p_2,p_3$ は互いに隣接しないので $I_{p_1},I_{p_2},I_{p_3}$ は互いに交わらず、名前を付け替えて $I_{p_2}$ が他の 2 つの間にあるとしてよい。道 $p_1,a_1,a_3,p_3$ の隣り合う頂点の区間は交わるので、4 つの区間の和集合は区間であり、$I_{p_2}$ の左右の点を含むので $I_{p_2}$ を含む。よって $p_1,a_1,a_3,p_3$ のどれかが $p_2$ に隣接するが、$p_2$ に隣接するのは $a_2$ だけで矛盾である。$\square$
有限グラフ $G$ について、次は同値である。
1・2・3 の同値は Roberts による(BW99 p. 1)。BW99 の証明(THEOREM, p. 2)は、爪を含まない区間グラフの区間表現を、区間を伸ばして固有区間表現に直し、さらに左から順に区間の長さを $1$ にそろえる、という表現の変形による。以下の証明は別の道をとり、極大クリークの並べ方から 4 の並べ方を作り、その並べ方から単位区間表現を帰納的に組み立てる。
1 ⇒ 2 は def-uig-main の後で見た。
2 ⇒ 3。 固有区間グラフは区間グラフである。固有区間表現 $(I_v)$ をもつ $G$ が爪 $c;x,y,z$ を誘導部分グラフに含むとする。$I_x,I_y,I_z$ は互いに交わらないので、名前を付け替えて $I_y$ が $I_x$ と $I_z$ の間にあるとしてよい。$I_c$ は $I_x$ と $I_z$ に交わる区間なので、$I_x$ の点と $I_z$ の点の間をすべて含み、とくに $I_c\supset I_y$ である。$I_c$ は $I_y$ に交わらない $I_x$ にも交わるので $I_c\ne I_y$ であり、$I_c$ は $I_y$ を真に含む。これは固有区間表現であることに反する。
3 ⇒ 4。 $G$ は区間グラフなので、区間グラフ の Gilmore–Hoffman の定理(1 ⇒ 2)により、極大クリークの連続な並べ方 $K_1,\dots,K_m$ がある。各頂点 $v$ について
$$
\ell_v=\min\{i\mid v\in K_i\},\qquad r_v=\max\{i\mid v\in K_i\}
$$
とおき、$J_v=[\ell_v,r_v]$ とする。連続性から $v\in K_i\iff i\in J_v$ である。
段階 1:$uv\in E\iff J_u\cap J_v\ne\emptyset$。 $uv\in E$ なら $\{u,v\}$ を含む極大クリーク $K_i$ があり、$i\in J_u\cap J_v$ である。逆に整数 $i\in J_u\cap J_v$ があれば $u,v\in K_i$ なので隣接する($J_u\cap J_v\ne\emptyset$ なら $\max(\ell_u,\ell_v)$ がそのような整数である)。
段階 2:$\ell_v< \ell_u$ かつ $r_u< r_v$ となる $u,v$ はない。 そのような $u,v$ があるとする。$\ell_u\in J_v$ なので $u,v\in K_{\ell_u}$ で、$uv\in E$ である。$u\notin K_{\ell_v}$ なので、$K_{\ell_v}$ の極大性から、$K_{\ell_v}\cup\{u\}$ はクリークでなく、$u$ に隣接しない $x\in K_{\ell_v}$ がある。同様に、$u$ に隣接しない $z\in K_{r_v}$ がある。$x,z$ は $v$ と同じ極大クリークに属するので $v$ に隣接し、$u$ に隣接する $v$ とは異なる。段階 1 から $J_x\cap J_u=\emptyset$ で、$\ell_x\le\ell_v< \ell_u$ なので $r_x< \ell_u$ である。同様に $\ell_z> r_u$ である。よって $r_x< \ell_u\le r_u< \ell_z$ で $J_x\cap J_z=\emptyset$、すなわち $x,z$ は隣接しない。したがって $v$ を中心とし $x,u,z$ を葉とする爪が誘導部分グラフとして現れ、仮定に反する。
段階 3:並べ方。 頂点を $(\ell_v,r_v)$ の辞書式の順に並べる。すなわち $\ell$ の小さい順に並べ、$\ell$ が等しい頂点は $r$ の小さい順に並べる($(\ell,r)$ も等しい頂点の順は任意)。こうして得た $v_1,\dots,v_n$ について $\ell_i=\ell_{v_i}$、$r_i=r_{v_i}$ と書く。$i< j< k$、$v_iv_k\in E$ とする。$\ell_i\le\ell_j\le\ell_k$ であり、段階 1 と $\ell_i\le\ell_k$ から $\ell_k\le r_i$ である。
4 ⇒ 1。 頂点の個数 $n$ についての帰納法で、次の強い主張を示す:近傍の連続な並べ方 $v_1,\dots,v_n$ をもつグラフに対し、実数 $x_1< x_2< \cdots< x_n$ で、$i\ne k$ について
$$
\lvert x_i-x_k\rvert\ne1,\qquad v_iv_k\in E\iff\lvert x_i-x_k\rvert< 1
$$
となるものがある。$\lvert x_i-x_k\rvert\ne1$ なので「$<1$」は「$\le1$」と同じであり、$I_{v_i}=[x_i,x_i+1]$ が単位区間表現になる。
$n=1$ なら $x_1=0$ でよい。$n\ge2$ とする。$v_1,\dots,v_{n-1}$ は $G-v_n$ の近傍の連続な並べ方なので、帰納法の仮定から $x_1< \cdots< x_{n-1}$ がとれる。$g=\min\{i\mid i=n\ \text{または}\ v_iv_n\in E\}$ とおく。$g\le i< n$ なら $v_iv_n\in E$ である。実際 $i=g$ なら $g$ の定め方による。$g< i< n$ なら、$v_gv_n\in E$ に def-uig-order の条件($g< i< n$)を当てて $v_iv_n\in E$ である。よって $v_iv_n\in E\iff g\le i\le n-1$ である。
$x_n$ を次の開区間から選ぶ。
$$
L=\max\bigl(x_{n-1},\ x_{g-1}+1\bigr)< x_n< U=x_g+1 .
$$
ここで $g=1$ なら $x_{g-1}+1$ の項は除き、$g=n$ なら $U=+\infty$ とする。この区間は空でない。$x_{g-1}< x_g$ であり、$g\le n-1$ なら $v_{n-1}=v_g$ であるか、$v_gv_{n-1}\in E$($v_gv_n\in E$ に条件を当てる)なので、帰納法の仮定から $x_{n-1}-x_g< 1$ だからである。さらに $x_n-x_i=1$ となる有限個の値を避けて $x_n$ を選ぶ。
このとき $x_n> x_{n-1}$ である。$g\le i\le n-1$ なら $0< x_n-x_i\le x_n-x_g< 1$、$i\le g-1$ なら $x_n-x_i\ge x_n-x_{g-1}> 1$ なので、$v_iv_n\in E\iff\lvert x_n-x_i\rvert< 1$ が成り立つ。$i,k< n$ の組についての条件は帰納法の仮定のとおりである。$\square$
証明の 4 ⇒ 1 は、並べ方を与えれば単位区間表現を左から順に $1$ 回ずつの選択で作る手続きになっている。3 ⇒ 4 と 4 ⇒ 1 を合わせると、爪を含まない区間グラフの極大クリークの連続な並べ方から、頂点の並べ方を経て単位区間表現が得られる。
ex-uig-basic の 4 のグラフで、並べ方 $1,2,3,4,5$ から始める。$x_1=0$。頂点 $2$ は $g=1$ なので $0< x_2< 1$、$x_2=0.5$ とする。頂点 $3$ は $g=2$($1$ と隣接せず $2$ と隣接)なので $\max(0.5,\,0+1)< x_3< 1.5$、$x_3=1.2$ とする。頂点 $4$ は $g=2$ なので $\max(1.2,\,1)< x_4< 1.5$、$x_4=1.4$ とする。頂点 $5$ は $g=3$ なので $\max(1.4,\,0.5+1)< x_5< 2.2$、$x_5=2.1$ とする。こうして ex-uig-basic の 4 の値が再現される。
近傍の連続な並べ方では、極大クリークが並べ方の中の連続な区間として読み取れる。
$v_1,\dots,v_n$ を $G$ の近傍の連続な並べ方とする。
1:$p\le j< j'\le q$ とする。$p< j$ なら、$v_pv_q\in E$ に def-uig-order の条件を当てて $v_jv_q\in E$ である($j=p$ ならそのまま)。$j'< q$ なら、$v_jv_q\in E$ にもう一度条件を当てて $v_jv_{j'}\in E$ であり、$j'=q$ なら $v_jv_q\in E$ そのものである。
2:極大クリーク $K$ の番号の最小を $p$、最大を $q$ とすると、$v_p,v_q\in K$ なので $v_pv_q\in E$(または $p=q$)であり、1 から $\{v_p,\dots,v_q\}$ は $K$ を含むクリークである。$K$ の極大性から等号が成り立つ。最小の番号 $p$ が同じ 2 つの極大クリークは $\{v_p,\dots,v_q\}$ と $\{v_p,\dots,v_{q'}\}$ の形で、一方が他方を含むので一致する。$\square$
したがって、並べ方が与えられていれば、各 $p$ について $v_p$ に隣接する最後の頂点 $v_q$ を求めれば、極大クリークはすべてこうして得る $n$ 個以下の集合 $\{v_p,\dots,v_q\}$ の中に現れ、クリーク数 $\omega(G)$ は $q-p+1$ の最大値である。区間グラフ と同じく $\chi(G)=\omega(G)$ であり、並べ方の順に貪欲に塗れば $\omega(G)$ 色で塗れる。
準順序との関係。 単位区間表現 $(x_v)$ について、$u\prec v$ を $x_u+1< x_v$(区間 $I_u$ が $I_v$ より完全に左にある)で定めると、$\prec$ は狭義半順序で、比べられない相異なる 2 頂点がちょうど隣接する 2 頂点である。このように数の差が $1$ を超えるかどうかで定まる半順序を セミオーダー(semiorder)という。補グラフ $\overline G$ はその比較可能グラフである。区間が完全に左にあることで定まる半順序を 区間順序(interval order)という。BW99 は、主定理を比較不能グラフに当てて、セミオーダーであることと、区間順序で、$3$ 元の鎖と $1$ 元の鎖の非交和 $\mathbf 1+\mathbf 3$ を含まないことが同値であることを系として述べている(COROLLARY, p. 2。セミオーダーの特徴づけは Scott と Suppes による(同 p. 1))。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 爪を含まない(thm-uig-main の 3) | 爪 $K_{1,3}$ | 区間グラフだが単位区間グラフでない |
| 区間グラフである(thm-uig-main の 3) | $C_4$ | 爪を含まないが単位区間グラフでない |
| 区間グラフを弦グラフに弱める | 網 $N$ | 弦グラフで爪を含まないが単位区間グラフでない |
| 辞書式の順の第 2 の鍵(3 ⇒ 4 の段階 3) | 道 $a-b-c$ を $b,a,c$ の順に並べる | $\ell$ の小さい順だが近傍の連続な並べ方でない |
要点:各行で左の条件だけが外れていることを確かめる。
1〜3 行目は ex-uig-non-examples とその証明による。網が弦グラフであることは、閉路が三角形 $a_1a_2a_3$ だけであることによる。
4 行目:極大クリークは $K_1=\{a,b\}$、$K_2=\{b,c\}$ で、$(\ell,r)$ は $a=(1,1)$、$b=(1,2)$、$c=(2,2)$ である。$b,a,c$ は $\ell$ の小さい順だが、$\ell$ の等しい $a,b$ を $r$ の大きい $b$ から並べている。$b$ と $c$ は隣接し、間の $a$ は $c$ に隣接しないので、def-uig-order の条件が満たされない。辞書式の順 $a,b,c$ は近傍の連続な並べ方である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する