区間グラフ

同義語:interval graph

概要

区間グラフ(interval graph)とは、実数直線の閉区間の有限族を頂点とし、交わる 2 つの区間を辺で結んだグラフのことである。Gilmore と Hoffman の定理により、有限グラフが区間グラフであることは、長さ $4$ 以上の閉路がすべて弦をもち(弦グラフ)、補グラフが比較可能グラフであることと同値であり、極大クリークを各頂点を含むものが連続するように一列に並べられることとも同値である。区間グラフは左端点の順の貪欲法でクリーク数と同じ色数で彩色でき、パーフェクトグラフの基本的な例である。

$$\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}} $$

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

区間グラフ(interval graph)とは、実数直線の区間を頂点とし、交わる 2 つの区間を辺で結んだグラフのことである。講義の時間割で「時間が重なる講義どうしを結ぶ」とできるグラフ、遺伝子の断片の重なり方を表すグラフが典型である。
区間グラフかどうかは、区間を探さなくてもグラフの言葉だけで判定できる。Gilmore と Hoffman は、区間グラフであることが「長さ $4$ の閉路がすべて弦をもち、補グラフの辺に向きを付けて半順序にできる」ことと同値であることを示した(GH64 Theorem 2, p. 545)。証明の鍵は、極大クリークを一列に並べて、各頂点を含む極大クリークが連続するようにできることである。

問い答え
何のグラフか実数直線の閉区間の有限族の交差グラフ
判定法(Gilmore–Hoffman)弦グラフで、補グラフが比較可能グラフ
構造極大クリークを、各頂点を含むものが連続するように並べられる
彩色左端点の順に塗る貪欲法で、クリーク数と同じ色数で塗れる
区間グラフでない例$C_4$、辺を細分した爪(星 $K_{1,3}$ の各辺に頂点を 1 つ入れた木)

定義

この記事のグラフは、頂点が有限個の単純グラフ $G=(V,E)$ とする。相異なる $u,v$ が隣接することを $uv\in E$ と書き、$\overline G$ を補グラフ、$W\subset V$ について $G[W]$ を $W$ の誘導部分グラフとする。クリーク・極大クリーク・クリーク数 $\omega(G)$ は クリーク の記事の定義のとおりとし、$\chi(G)$ は彩色数である。$k\ge3$ について $C_k$ は $k$ 頂点の閉路グラフである。

区間グラフ

グラフ $G=(V,E)$ に対し、各頂点 $v$ に実数直線の有界閉区間 $I_v=[a_v,b_v]$($a_v\le b_v$)を対応させ、相異なる任意の $u,v\in V$ について
$$ uv\in E\iff I_u\cap I_v\ne\emptyset $$
となるようにできるとき、$G$ を 区間グラフ(interval graph)といい、$(I_v)_{v\in V}$ を $G$ の 区間表現 という。

異なる頂点に同じ区間を対応させてもよい。区間表現 $(I_v)$ を $W\subset V$ に制限すれば $G[W]$ の区間表現になるので、区間グラフの誘導部分グラフは区間グラフである(誘導部分グラフ の記事の言葉では、区間グラフの全体は遺伝的な族である)。
判定法に現れる 2 つのグラフの族を定義する。閉路の 弦 とは、閉路の上で隣り合わない 2 頂点を結ぶ辺のことである。

弦グラフと比較可能グラフ
  1. 長さ $4$ 以上のどの閉路も弦をもつグラフを 弦グラフ(chordal graph)という。これは、$k\ge4$ のどの $C_k$ も誘導部分グラフとして含まないことと同じである(Die25 §5.5, p. 140)。
  2. 頂点の集合 $V$ の上の狭義半順序 $\prec$(非反射的かつ推移的な関係)で、相異なる任意の $u,v$ について
    $$ uv\in E\iff u\prec v\ \text{または}\ v\prec u $$
    となるものがあるとき、$G$ を 比較可能グラフ(comparability graph)という(GH64 p. 539)。辺 $uv$ に $u\prec v$ の向き $u\to v$ を付けると、推移的な向き付けが得られる。

区間グラフの構造を最もよく表すのは、極大クリークの並べ方である。

極大クリークの連続な並べ方

グラフ $G$ の極大クリークの全体を一列に並べた $K_1,K_2,\dots,K_m$ が、各頂点 $v$ について
$$ \{\,i\mid v\in K_i\,\}\ \text{が連続する整数の集合} $$
となるとき、これを極大クリークの 連続な並べ方 という。すなわち、$v\in K_i$ かつ $v\in K_k$、$i< j< k$ なら $v\in K_j$ である。

例

道・星・完全グラフ
  1. 道 $P_n$(頂点 $1,\dots,n$、辺 $\{i,i+1\}$)は、$I_i=[i,i+1]$ とおけば区間グラフである。極大クリークは $n-1$ 本の辺で、$\{1,2\},\{2,3\},\dots,\{n-1,n\}$ の順が連続な並べ方である。
  2. 星 $K_{1,3}$(中心 $c$ と葉 $x,y,z$)は、$I_c=[0,10]$、$I_x=[1,2]$、$I_y=[4,5]$、$I_z=[7,8]$ とおけば区間グラフである。
  3. 完全グラフ $K_n$ は、すべての頂点に同じ区間を対応させれば区間グラフである。
  4. 頂点 $1,\dots,6$ に $[0,2],[1,4],[3,5],[3,8],[6,7],[6,9]$ を対応させたグラフの極大クリークは、点 $2,4,7$ を共有する区間の集まり $\{1,2\}$、$\{2,3,4\}$、$\{4,5,6\}$ で、この順が連続な並べ方である。クリーク数は $3$ である。
区間グラフでないグラフ
  1. $C_k$($k\ge4$)。 thm-ig-main の証明の中で、$C_k$ の極大クリークには連続な並べ方がないことを示す。$C_4$ の補グラフは辺 $2$ 本からなり、比較可能グラフである。
  2. 辺を細分した爪。 中心 $c$ に $x,y,z$ を結び、さらに $x$ に $x'$、$y$ に $y'$、$z$ に $z'$ を結んだ $7$ 頂点の木 $T$ は、閉路をもたないので弦グラフだが、区間グラフではない。

要点:道に沿った区間の和集合は区間になり、間にある葉の区間に触れてしまう。

証明を開く

2 を示す。区間表現 $(I_v)$ があるとする。$x',y',z'$ はどの 2 つも隣接しないので、区間 $I_{x'},I_{y'},I_{z'}$ は互いに交わらない。名前を付け替えて、$I_{x'}$ が $I_{y'}$ の左に、$I_{y'}$ が $I_{z'}$ の左にあるとしてよい($x,y,z$ の役割は対称である)。道 $x',x,c,z,z'$ の隣り合う頂点の区間は交わるので、5 つの区間の和集合 $U$ は区間である。$U$ は $I_{y'}$ の左端より左の点($I_{x'}$ の点)と右端より右の点($I_{z'}$ の点)を含むので、$U\supset I_{y'}$ である。よって $x',x,c,z,z'$ のどれかの区間が $I_{y'}$ と交わり、その頂点は $y'$ に隣接する。しかし $y'$ に隣接するのは $y$ だけなので矛盾である。$\square$

主定理:Gilmore–Hoffman の定理

Gilmore–Hoffman の定理

有限グラフ $G$ について、次は同値である。

  1. $G$ は区間グラフである。
  2. $G$ の極大クリークには連続な並べ方がある。
  3. $G$ は弦グラフで、$\overline G$ は比較可能グラフである。
  4. $G$ は $C_4$ を誘導部分グラフとして含まず、$\overline G$ は比較可能グラフである。

GH64 Theorem 2(p. 545)は 1 と 4 の同値を、無限グラフと一般の線形順序集合の上の区間まで含めて述べ、証明の中で 2 の並べ方を作っている(pp. 546–547)。以下は有限の場合の証明である。$G$ に頂点がないときはすべて自明に成り立つので、$V\ne\emptyset$ とする。

1 ⇒ 2。 区間表現 $(I_v)$ をとる。極大クリーク $K$ について、クリーク の記事の命題「区間グラフのクリーク」により $\bigcap_{v\in K}I_v$ は空でないので、その点を 1 つ選んで $p_K$ とする。相異なる極大クリーク $K,L$ について $p_K\ne p_L$ である。実際 $p_K=p_L=p$ なら、$K\cup L$ の区間はすべて $p$ を含むので $K\cup L$ はクリークになり、$K$ の極大性に反する。そこで極大クリークを $p_{K_1}< p_{K_2}<\cdots< p_{K_m}$ の順に並べる。$v\in K_i\cap K_k$、$i< j< k$ とすると、$p_{K_i},p_{K_k}\in I_v$ で $I_v$ は区間なので $p_{K_j}\in I_v$ である。すると $K_j\cup\{v\}$ の区間はすべて $p_{K_j}$ を含むのでクリークであり、$K_j$ の極大性から $v\in K_j$ である。
2 ⇒ 1。 連続な並べ方 $K_1,\dots,K_m$ をとる。各頂点 $v$ は $\{v\}$ を含む極大クリークに属するので、$\ell_v=\min\{i\mid v\in K_i\}$、$r_v=\max\{i\mid v\in K_i\}$ が定まる。$I_v=[\ell_v,r_v]$ とおく。$u\ne v$ が隣接すれば、$\{u,v\}$ を含む極大クリーク $K_i$ があり、$i\in I_u\cap I_v$ である。逆に $I_u\cap I_v\ne\emptyset$ なら、整数 $i=\max(\ell_u,\ell_v)$ は $\min(r_u,r_v)$ 以下なので両方の区間に入り、連続性から $u,v\in K_i$、よって $uv\in E$ である。
1 ⇒ 3。 比較可能性:区間表現について、$u\prec v$ を $b_u< a_v$($I_u$ が $I_v$ より完全に左にある)で定める。$a_u\le b_u$ なので $u\not\prec u$ であり、$b_u< a_v\le b_v< a_w$ から推移的である。相異なる $u,v$ について、$uv\notin E$、すなわち $I_u\cap I_v=\emptyset$ であることは、$b_u< a_v$ または $b_v< a_u$ であることと同じである。よって $\prec$ は $\overline G$ を比較可能グラフにする(GH64 p. 545 の必要性の議論)。
弦グラフであること:$G$ が $k\ge4$ の $C_k$ を誘導部分グラフとして含むとする。区間グラフの誘導部分グラフは区間グラフなので $C_k$ は区間グラフであり、1 ⇒ 2 から $C_k$ の極大クリークに連続な並べ方 $e_1,\dots,e_k$ がある。$C_k$ の極大クリークは $k$ 本の辺である(クリーク の記事の例「完全グラフ・閉路・完全多部グラフ」)。各頂点 $v$ はちょうど 2 本の辺に含まれ、連続性からその 2 本は隣り合う位置 $e_i,e_{i+1}$ にある。相異なる頂点 $v,w$ が同じ組 $\{e_i,e_{i+1}\}$ を使うと、$e_i,e_{i+1}$ はどちらも $v,w$ を含み、$e_i=e_{i+1}=\{v,w\}$ となって矛盾する。よって $k$ 個の頂点が $k-1$ 個の組 $\{e_i,e_{i+1}\}$($1\le i\le k-1$)を互いに異なるように使うことになり、不可能である。
3 ⇒ 4。 $C_4$ は弦のない長さ $4$ の閉路である。
4 ⇒ 2。 $\overline G$ を比較可能グラフにする狭義半順序 $\prec$ をとる。すなわち、相異なる $u,v$ が隣接しないことと、$u\prec v$ または $v\prec u$ であることが同値である。とくに、隣接する 2 頂点や同じ頂点は $\prec$ で比べられない。この性質を (P) と呼ぶ。
段階 1:異なる極大クリークの間には非隣接の組がある。 $K\ne L$ を極大クリークとする。$L\subset K$ なら $L$ の極大性から $L=K$ となるので、$b\in L\setminus K$ がある。$K$ の極大性から $K\cup\{b\}$ はクリークでなく、$a\in K$ で $a\ne b$、$ab\notin E$ となるものがある。
段階 2:向きはそろう。 $a,a'\in K$、$b,b'\in L$ で、$ab\notin E$、$a'b'\notin E$(どちらも相異なる 2 頂点)、$a\prec b$、$b'\prec a'$ となることはないことを示す。そうなったとする。$a=a'$ なら $b'\prec a\prec b$ から $b'\prec b$ で、(P) により $b,b'$ は相異なり隣接しないが、どちらも $L$ に属するので矛盾である。$b=b'$ も同様に $a\prec b\prec a'$ から矛盾する。$a=b'$ なら $b'\prec a'$ は $a\prec a'$ となり、$a'=b$ なら $a\prec b$ は $a\prec a'$ となって、どちらも $K$ がクリークであることに反する。したがって $a,a',b,b'$ は相異なり、$aa'\in E$、$bb'\in E$ である。
ここで $ab'\in E$ である。そうでなければ (P) から $a\prec b'$ か $b'\prec a$ で、前者なら $a\prec b'\prec a'$、後者なら $b'\prec a\prec b$ となり、それぞれ $K$、$L$ がクリークであることに反する。同様に $a'b\in E$ である($a'\prec b$ なら $b'\prec a'\prec b$、$b\prec a'$ なら $a\prec b\prec a'$)。すると $a,a',b,b'$ は辺 $aa',a'b,bb',b'a$ をもち、$ab,a'b'$ をもたないので、$G[\{a,a',b,b'\}]$ は $C_4$ である。これは仮定に反する。
段階 1・2 により、相異なる極大クリーク $K,L$ について、隣接しない $a\in K$、$b\in L$ をとると、$a\prec b$ となるか $b\prec a$ となるかは組の選び方によらない。前者のとき $K\lhd L$ と書く。$K\lhd L$ と $L\lhd K$ のちょうど一方が成り立つ。
段階 3:$\lhd$ は推移的である。 $K\lhd L\lhd M$ とする。$K=M$ なら $K\lhd L\lhd K$ となり段階 2 に反するので、$K\ne M$ である。隣接しない $a\in K$、$b\in L$ で $a\prec b$ となるもの、隣接しない $b'\in L$、$c\in M$ で $b'\prec c$ となるものをとる。$a\in K$、$c\in M$ が隣接せず $a\prec c$ であることを示せば、$K\lhd M$ である。

  • $b=b'$ なら $a\prec b\prec c$ から $a\prec c$ である。
  • $a=b'$ なら $a=b'\prec c$ であり、$b=c$ なら $a\prec b=c$ である。
  • $a\ne b'$ で $ab'\notin E$ なら、段階 2 により $a\prec b'$ なので $a\prec b'\prec c$ である。$b\ne c$ で $bc\notin E$ なら、同様に $b\prec c$ なので $a\prec b\prec c$ である。
    残るのは、$a,b,b',c$ が相異なり($a=c$ なら $b'\prec c=a\prec b$ から $b'\prec b$ となって $L$ に反する)、$ab'\in E$、$bb'\in E$、$bc\in E$ の場合である。$ac\in E$ なら、$a,b',b,c$ は辺 $ab',b'b,bc,ca$ をもち $ab,b'c$ をもたないので $C_4$ を誘導し、仮定に反する。よって $ac\notin E$ で、(P) から $a\prec c$ か $c\prec a$ である。$c\prec a$ なら $b'\prec c\prec a$ から $b'\prec a$ となるが、$ab'\in E$ なので (P) に反する。したがって $a\prec c$ である。
    以上で $\lhd$ は極大クリークの全体の上の狭義の全順序であり、$K_1\lhd K_2\lhd\cdots\lhd K_m$ と並べられる。

段階 4:連続性。 $v\in K_i\cap K_k$、$i< j< k$ で $v\notin K_j$ とする。$K_j$ の極大性から、$w\in K_j$ で $w\ne v$、$vw\notin E$ となるものがある。$K_i\lhd K_j$ と $v\in K_i$、$w\in K_j$ から $v\prec w$、$K_j\lhd K_k$ と $w\in K_j$、$v\in K_k$ から $w\prec v$ である。これは $\prec$ の非反射性と推移性に反する。よって並べ方は連続である。$\square$

2 から 1 への構成では、区間の端点を極大クリークの番号にとった。したがって、$m$ 個の極大クリークをもつ区間グラフは、$\{1,\dots,m\}$ に端点をもつ区間で表現できる。
4 ⇒ 2 の証明では、3 の弦グラフの条件のうち $C_4$ を含まないという部分だけを使った。実際、$\overline G$ が比較可能グラフなら、$G$ は $k\ge5$ の $C_k$ を誘導部分グラフとして含まない。$G[W]$ が $C_k$ なら、$\overline{G[W]}=\overline G[W]$ は狭義半順序を $W$ に制限して比較可能グラフであり、$C_k$ は $C_4$ を誘導部分グラフとして含まないので、4 ⇒ 3 を $G[W]$ に当てると $C_k$ が弦グラフになって矛盾するからである。

判定法の読み方

ex-ig-non-examples の木 $T$ は弦グラフだが区間グラフでないので、thm-ig-main の 3 により $\overline T$ は比較可能グラフでない。比較可能グラフそのものの判定法として、GH64 Theorem 1(p. 540)は、比較可能グラフであることが「奇数の長さのどの閉路 $a_1,\dots,a_k$ も、$a_ia_{i+2}$ の形の辺(添字は $k$ を法とする。三角の弦)をもつ」ことと同値であると述べる(閉路には同じ頂点が何度か現れてもよい。この記事では証明しない)。

彩色とパーフェクト性

区間グラフの彩色は、左端点の順に貪欲に塗るだけで最適になる。区間を講義の時間、色を教室と読むと、必要な教室の最小数は「同時に行われる講義の最大数」に等しい、という主張である。

左端点の順の貪欲彩色

$G$ を区間表現 $(I_v)$ をもつ区間グラフとし、頂点を $a_{v_1}\le a_{v_2}\le\cdots\le a_{v_n}$ と左端点の順に並べる。$v_1,v_2,\dots$ の順に、すでに色の付いた隣接頂点が使っていない最小の番号の色を付けると、使う色は $\omega(G)$ 個以下である。したがって $\chi(G)=\omega(G)$ である。

$v_j$ を塗るときに、すでに色の付いた隣接頂点 $u=v_i$($i< j$)を考える。$a_u\le a_{v_j}$ であり、$I_u\cap I_{v_j}\ne\emptyset$ から $b_u\ge a_{v_j}$ である($b_u< a_{v_j}$ なら $I_u$ は $I_{v_j}$ より完全に左にある)。よって $a_{v_j}\in I_u$ である。$v_j$ とそのような $u$ の全体の区間は点 $a_{v_j}$ を共有するのでクリークをなし(クリーク の記事の命題「区間グラフのクリーク」)、その頂点の個数は $\omega(G)$ 以下である。したがって色の付いた隣接頂点は $\omega(G)-1$ 個以下で、色 $1,\dots,\omega(G)$ のどれかが空いている。$\chi(G)\le\omega(G)$ が示され、逆向きの不等式はクリークの頂点がすべて異なる色を要することから従う。$\square$

すべての誘導部分グラフで彩色数がクリーク数に等しいグラフを パーフェクト(perfect)という(誘導部分グラフ の記事の節「彩色数とクリーク数」)。区間グラフの誘導部分グラフは区間グラフなので、prop-ig-greedy から次が従う。

区間グラフはパーフェクト

区間グラフはパーフェクトである。その補グラフもパーフェクトであり、区間グラフ $G$ では、頂点の集合を覆うクリークの最小個数が、独立集合の頂点の個数の最大値 $\alpha(G)$ に等しい。

前半は上で述べた。後半:thm-ig-main の 1 ⇒ 3 の証明の順序 $\prec$(区間が完全に左にある)について、$\overline G$ は有限半順序集合 $(V,\prec)$ の比較可能グラフである。パーフェクトグラフ定理 の記事の系「Mirsky の定理から Dilworth の定理へ」により比較可能グラフはパーフェクトなので、$\chi(\overline G)=\omega(\overline G)$ である。$\overline G$ の彩色の色ごとの集合は $G$ のクリーク、$\overline G$ のクリークは $G$ の独立集合なので、これが後半の主張である。$\square$

一般に弦グラフはパーフェクトである(Die25 Proposition 5.5.2, p. 140)。区間グラフの場合は、prop-ig-greedy のように具体的な塗り方が手に入る。

時間割の教室数

講義 $A,B,C,D,E$ の時間を $A=[9,11]$、$B=[10,12]$、$C=[11,13]$、$D=[12,14]$、$E=[13,15]$ とする(端点を共有すれば重なるとみなす)。区間グラフの辺は $AB,AC,BC,BD,CD,CE,DE$ で、時刻 $11$ に $A,B,C$、時刻 $12$ に $B,C,D$、時刻 $13$ に $C,D,E$ が重なるので $\omega=3$ である。左端点の順 $A,B,C,D,E$ に貪欲に塗ると、$A=1$、$B=2$、$C=3$、$D=1$($D$ は $A$ と重ならない)、$E=2$ となり、教室は $3$ つで足りる。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
$\overline G$ が比較可能グラフ(thm-ig-main の 3)辺を細分した爪 $T$弦グラフだが区間グラフでない
弦グラフ・$C_4$ を含まない(thm-ig-main の 3・4)$C_4$$\overline{C_4}$ は比較可能グラフだが区間グラフでない
区間が直線上にあること(thm-ig-main)円周上の 4 つの弧で $C_4$ を表したもの弧の交差グラフだが区間グラフでない
左端点の順に塗ること(prop-ig-greedy)道 $P_4$ を端点 $1,4$、内側の $2,3$ の順に塗る$\omega=2$ だが $3$ 色を使う
反例の確かめ

要点:各行の左の条件だけが外れていることを確かめる。

確かめを開く

1 行目:$T$ は木なので弦グラフで、ex-ig-non-examples の証明により区間グラフでない。thm-ig-main の 3 のうち比較可能性だけが外れている。

2 行目:$C_4$ は弦のない長さ $4$ の閉路で、$\overline{C_4}$ は辺 $2$ 本からなる。各辺の一方の端点が他方より小さいとする順序は推移的(長さ $2$ の向きの鎖がない)なので、$\overline{C_4}$ は比較可能グラフである。区間グラフでないことは thm-ig-main の証明の 1 ⇒ 3 の部分による。

3 行目:円周を 4 等分する点 $0,1,2,3$(時計回り)について、弧 $[0,1],[1,2],[2,3],[3,0]$ を頂点 $1,2,3,4$ に対応させると、隣り合う弧だけが端点で交わり、交差グラフは $C_4$ である。直線上の区間では表現できない。円周上では、どの 2 つも交わる弧の族が全体に共通の点をもつとは限らない(クリーク の記事の注意を参照)。

4 行目:$P_4$ を $1-2-3-4$ とする。$1$ に色 $1$、$4$ に色 $1$、$2$ に色 $2$($1$ と隣接)、$3$ には $2$ の色 $2$ と $4$ の色 $1$ が使われているので色 $3$ を付ける。$P_4$ は区間グラフ(ex-ig-basic の 1)なので、塗る順だけが原因である。

歴史と広がり

  • 起源。 区間グラフの特徴づけは、Hajós が最初に提起し、遺伝子の微細構造を研究した Benzer が独立に提起した問題と密接に関係する(GH64 p. 539)。Lekkerkerker と Boland は別の特徴づけを与えている(同 p. 539)。
  • Gilmore–Hoffman の論文。 GH64 は比較可能グラフの特徴づけ(Theorem 1, p. 540)と区間グラフの特徴づけ(Theorem 2, p. 545)を、無限グラフを含めて与えた。有限の区間グラフでは、すべての頂点と辺を覆う極大クリークの集まりは極大クリークの全体しかないことも示されている(p. 547)。
  • 教科書での位置。 Die25 は、区間グラフが弦グラフであることと補グラフが比較可能グラフであることを演習とし、逆が Gilmore–Hoffman の定理であると述べている(Exercise 44, p. 151)。比較可能グラフがパーフェクトであることも演習である(Exercise 43, p. 151)。
  • 2 次元の類似。 平面の単位円板の交差グラフ 単位円板グラフ では、クリークが共通の点で捉えられず、彩色数がクリーク数を超えることがある。

関連項目

参考文献

[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、Theorem 1 p. 540、Theorem 2 p. 545、pp. 546–547)
[2]
Reinhard Diestel, Graph Theory, 6th edition, Graduate Texts in Mathematics 173, Springer, 2025, §5.5:弦グラフの定義と Proposition 5.5.2(p. 140)、Exercises 43・44(p. 151)

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