木幅(treewidth)とは、グラフの頂点を袋と呼ぶ集合に分けて木の形に並べる木分解のうち、最大の袋の大きさから $1$ を引いた幅を最小にした値であり、グラフがどれだけ木に近いかを測る。最小次数と、互いに触れ合う連結な集合の族(bramble)の位数から $1$ を引いた値は木幅の下界であり、後者の最大値は木幅に一致する。$k\times k$ の格子グラフの木幅は $k$ で、木幅は弦グラフによる言い換え、木分解に沿った動的計画法、禁止マイナーと結びつく。
木幅(treewidth)は、グラフがどれだけ木に近いかを測る非負の整数である。グラフを「袋」と呼ぶ頂点集合に分け、袋どうしを木の形に並べる木分解をとり、いちばん大きな袋の大きさから $1$ を引いたものを、すべての木分解にわたって最小にした値として定める。森の木幅は $1$ 以下、閉路の木幅は $2$、$n$ 頂点の完全グラフの木幅は $n-1$ である。
木幅が小さいグラフは、小さな頂点集合で次々に切り分けられるので、木の上と同じように動的計画法で問題を解ける。一方、木幅が大きいことには「互いに触れ合う連結な集合の大きな族」(bramble)という障害が対応し、これが木幅の下からの評価を与える。Robertson と Seymour のグラフマイナーの理論では、木幅は中心的な量の 1 つである。
この記事では、木幅を定義し、最小次数による評価(prop-tw-degree)と bramble による評価(thm-tw-bramble)を証明し、$k\times k$ の格子グラフの木幅がちょうど $k$ であること(thm-tw-grid)を示す。さらに、弦グラフによる言い換え(prop-tw-chordal)、独立集合の動的計画法(prop-tw-dp)、禁止マイナーとの関係を扱う。木分解の基本の補題と、木幅がマイナーで増えないこと、完全グラフ・森・閉路の木幅は グラフマイナー の節「木分解と木幅」で証明されている。
| 内容 | 場所 |
|---|---|
| 定義 | def-tw-main |
| 最小次数による評価 | prop-tw-degree |
| bramble による評価(主定理の一つ) | def-tw-bramble、thm-tw-bramble |
| 格子グラフの木幅(主定理) | thm-tw-grid |
| 弦グラフによる言い換え | prop-tw-chordal |
| 動的計画法 | prop-tw-dp |
| 禁止マイナーと格子 | thm-tw-minors |
この記事では、グラフは有限で単純な無向グラフとする。$G$ の頂点集合を $V(G)$、$X\subset V(G)$ の上の誘導部分グラフを $G[X]$ と書く。
グラフ $G$ の 木分解 とは、木 $T$ と、$T$ の各ノード $t$ に対する $V(G)$ の部分集合 $V_t$(袋)の組 $(T,(V_t)_{t\in V(T)})$ で、次をみたすものである。
$T$ を 1 点、袋を $V(G)$ だけにとれば木分解になるので、木幅は定まり、$\operatorname{tw}(G)\le\lvert V(G)\rvert-1$ である。(T3) は、頂点 $v$ を含む袋のノードの集合 $T_v:=\{t\mid v\in V_t\}$ が $T$ の部分木をなすことと同じである。定義は グラフマイナー の定義「木分解と木幅」と同じで、Die25 §12.3–§12.4(pp. 367, 371)による。幅を「袋の大きさ $-1$」とするのは、森の木幅を $1$ 以下にするためである。
以下では、グラフマイナー の補題「袋による分離」を何度も使う。$T$ の辺 $t_1t_2$ を除いた森の $t_i$ を含む成分を $T_i$、$U_i:=\bigcup_{t\in T_i}V_t$ とおくと、
頂点を 1 個以上もつグラフ $G$ の最小次数を $\delta(G)$ とすると、$\operatorname{tw}(G)\ge\delta(G)$ である。
$G$ の木分解のうち、幅が $\operatorname{tw}(G)$ で、そのなかでノードの数が最小のもの $(T,(V_t))$ をとる。$T$ が 1 点なら袋は $V(G)$ で、$\lvert V(G)\rvert\ge\delta(G)+1$ なので幅は $\delta(G)$ 以上である。
$T$ が 2 点以上なら、葉 $t$ とその隣のノード $s$ をとる。$V_t\subset V_s$ なら $t$ と $V_t$ を除いても (T1)〜(T3) が成り立ち、幅は増えないので、ノードの数の最小性に反する。よって $v\in V_t\setminus V_s$ がある。$v$ を含む袋のノードの集合 $T_v$ は部分木で、$t$ を含み、$t$ の唯一の隣 $s$ を含まないので、$T_v=\{t\}$ である。$v$ に接続する各辺 $vu$ について (T2) により $v,u$ をともに含む袋があり、それは $V_t$ である。よって $v$ と $v$ の隣接頂点はすべて $V_t$ に入り、$\lvert V_t\rvert\ge\deg v+1\ge\delta(G)+1$ である。どちらの場合も幅は $\delta(G)$ 以上である。$\square$
この評価は Die25 第 12 章の演習 26(p. 407)にある。たとえば完全 2 部グラフ $K_{m,n}$($1\le m\le n$)では $\delta=m$ なので $\operatorname{tw}(K_{m,n})\ge m$ である。逆に、小さい側を $A$($\lvert A\rvert=m$)として、大きい側の頂点 $v$ ごとに袋 $A\cup\{v\}$ を道の形に並べると幅 $m$ の木分解になる($A$ の頂点はすべての袋に、$v$ は 1 つの袋に属する)。よって $\operatorname{tw}(K_{m,n})=\min(m,n)$ である。
最小次数の評価は、次数の小さい頂点が 1 つあるだけで役に立たなくなる。木幅の大きさを正確にとらえる障害が bramble である。
$G$ の頂点の部分集合 $X,Y$ が 触れ合う とは、共通の頂点をもつか、$X$ の頂点と $Y$ の頂点を結ぶ辺があることをいう。空でない頂点集合 $B$ で $G[B]$ が連結なものからなる族 $\mathcal B$ で、どの 2 つの元も触れ合うものを、$G$ の bramble という。$\mathcal B$ のすべての元と交わる頂点集合を $\mathcal B$ の 被覆 といい、被覆の頂点の数の最小値を $\mathcal B$ の 位数 という。
定義は Die25 §12.4(p. 371)による。bramble の 1 つの元 $B$ をとれば $B$ 自身が被覆なので、位数は有限である。
$\mathcal B$ を $G$ の bramble とすると、$G$ のどの木分解にも $\mathcal B$ を被覆する袋がある。とくに、$\operatorname{tw}(G)\ge(\mathcal B\text{ の位数})-1$ である。
$(T,(V_t))$ を $G$ の木分解とする。$T$ の各辺 $t_1t_2$ について $X:=V_{t_1}\cap V_{t_2}$ とおく。$X$ が $\mathcal B$ を被覆すれば、$X\subset V_{t_1}$ なので $V_{t_1}$ が求める袋である。以下、どの辺についても $X$ は $\mathcal B$ を被覆しないとする。
辺の向き.辺 $t_1t_2$ と、$X$ と交わらない $B\in\mathcal B$ をとる。(T1) により $B\subset U_1\cup U_2$ であり、$B$ は連結で $X$ と交わらないので、(S2) により $U_1$ と $U_2$ の一方としか交わらない。すなわち $B\subset U_i\setminus X$ となる $i$ がただ 1 つある。$X$ と交わらない 2 つの元 $B,B'$ について $B\subset U_1\setminus U_2$、$B'\subset U_2\setminus U_1$ となることはない。そうなら $B$ と $B'$ は共通の頂点をもたず、(S1) により間に辺もなく、触れ合わないからである。$X$ と交わらない元は少なくとも 1 つあるので、この $i$ は辺ごとに 1 つに決まる。辺を $t_i$ の向きに向ける。
行き止まりのノード.任意のノードから出発し、そこから出る向きの辺があればそれをたどることを繰り返す。木の中で辺を逆向きにたどることはない(辺はどちらか一方の向きだけをもつ)ので、たどる道は同じノードを 2 度通らず、いつか止まる。止まったノード $t$ では、$t$ に接続する辺はすべて $t$ を向いている。
$V_t$ が被覆であること.$B\in\mathcal B$ が $V_t$ と交わらないとする。$v\in B$ をとり、$v\in V_s$ とする。$v\notin V_t$ なので $s\ne t$ である。$T$ の中の $t$ から $s$ への道の最初の辺を $tt'$ とし、この辺について $t$ の側を $U_1$、$t'$ の側を $U_2$ とする。$s$ は $t'$ の側にあるので $v\in U_2$ である。一方 $B\cap(V_t\cap V_{t'})\subset B\cap V_t=\emptyset$ なので、辺 $tt'$ が $t$ を向いていることから $B\subset U_1\setminus U_2$ である。これは $v\in B\cap U_2$ に反する。よって $V_t$ は $\mathcal B$ を被覆する。
幅の評価.被覆する袋 $V_t$ について $\lvert V_t\rvert\ge(\mathcal B\text{ の位数})$ なので、どの木分解の幅も位数 $-1$ 以上であり、$\operatorname{tw}(G)\ge(\mathcal B\text{ の位数})-1$ である。$\square$
この証明は Die25 Theorem 12.4.3(p. 372)の前半の向きの証明を詳しく書いたものである。同定理(Seymour と Thomas による 1993 年の定理)は逆も述べている。
整数 $k\ge0$ について、$\operatorname{tw}(G)< k$ であることと、$G$ が位数 $k$ より大きい bramble をもたないことは同値である。言いかえれば、$\operatorname{tw}(G)$ は $G$ の bramble の位数の最大値から $1$ を引いたものに等しい。
Die25 Theorem 12.4.3(pp. 372–374)。$\operatorname{tw}(G)< k$ なら位数 $k$ より大きい bramble がないことは thm-tw-bramble である。逆向きは、木幅が $k$ 以上なら「花弁」の族から位数 $k$ より大きい bramble を組み立てる議論で、この記事では証明しない。
$k\ge1$ について、$\{1,\dots,k\}^2$ を頂点集合とし、$\lvert i-i'\rvert+\lvert j-j'\rvert=1$ となる $(i,j)$ と $(i',j')$ を辺で結んだグラフを $k\times k$ の格子 といい、$G_{k,k}$ と書く(格子グラフ の定義「長方形の格子グラフ」、Die25 p. 372)。$(i,j)$ の $i$ を行、$j$ を列と呼ぶ。
$k\ge2$ について $\operatorname{tw}(G_{k,k})=k$ である。
上からの評価.頂点を行ごとに左から右へ、上の行から順に並べて $v_1,\dots,v_{k^2}$ とする($v_{(i-1)k+j}=(i,j)$)。$m=1,\dots,k^2-k$ について袋 $W_m:=\{v_m,v_{m+1},\dots,v_{m+k}\}$ をとり、ノード $m$ と $m+1$ を結ぶ道 $T$ の上に並べる。横の辺は $v_sv_{s+1}$、縦の辺は $v_sv_{s+k}$ の形で、$s\le k^2-k$ なら $W_s$ に、横の辺で $s>k^2-k$ なら $W_{k^2-k}$ に含まれるので (T2) が成り立つ。$v_s$ を含む袋は $\max(1,s-k)\le m\le\min(s,k^2-k)$ の $W_m$ で、番号が連続しているので (T3) が成り立ち、(T1) も明らかである。袋の大きさは $k+1$ なので、$\operatorname{tw}(G_{k,k})\le k$ である。
下からの評価.位数が $k+1$ 以上の bramble を作る。$S:=\{1,\dots,k-1\}^2$ とおき、$1\le i,j\le k-1$ について
$$
C_{ij}:=\{(i,\ell)\mid 1\le\ell\le k-1\}\cup\{(\ell,j)\mid 1\le\ell\le k-1\}\subset S
$$
($S$ の中の第 $i$ 行と第 $j$ 列の和)とおく。さらに $X:=\{(k,\ell)\mid1\le\ell\le k\}$(最後の行)、$Y:=\{(\ell,k)\mid1\le\ell\le k-1\}$(最後の列から角を除いたもの)とし、$\mathcal B:=\{C_{ij}\}_{i,j}\cup\{X,Y\}$ とする。
$G_{k,k}$ の木幅が $k$ であることは Die25 第 12 章の演習 34(p. 408)で、上の証明はこの記事の独自のものである。同書 p. 372 は、$G_{k,k}$ の $k^2$ 個の「十字」(第 $i$ 行と第 $j$ 列の和)が位数 $k$ の bramble をなすことから $\operatorname{tw}(G_{k,k})\ge k-1$ を導いている(p. 375)。上の証明は、十字を $(k-1)\times(k-1)$ の部分に縮め、最後の行と列を 2 つの元に分けて位数を $1$ 上げたものである。$k=2$ では $G_{2,2}$ は 4 頂点の閉路で、$\mathcal B=\{\{(1,1)\},\{(2,1),(2,2)\},\{(1,2)\}\}$ となり、グラフマイナー の定理「木幅の基本性質」の 4 と合う。
閉路で、閉路の辺でない 2 頂点を結ぶ辺を 弦 という。長さ $4$ 以上のどの閉路も弦をもつグラフを 弦グラフ(chordal graph)という。完全グラフ・森は弦グラフで、長さ $4$ 以上の閉路は弦グラフでない。$G$ の完全部分グラフの頂点の数の最大値を $\omega(G)$ と書く。
1 は Die25 Proposition 12.3.6(p. 369)で、この記事では証明しない。
2:$H$ を $G$ を含む弦グラフとする。1 により $H$ の木分解 $(T,(V_t))$ で各 $H[V_t]$ が完全グラフのものがある。袋は $H$ の完全部分グラフなので $\lvert V_t\rvert\le\omega(H)$ である。$G$ の辺は $H$ の辺なので、同じ $(T,(V_t))$ は $G$ の木分解でもあり、$\operatorname{tw}(G)\le\omega(H)-1$ である。
逆に、$(T,(V_t))$ を幅 $\operatorname{tw}(G)$ の $G$ の木分解とし、$G$ に、同じ袋に入る 2 頂点を結ぶ辺をすべて加えたグラフを $H$ とする。$H$ の辺はどれも 1 つの袋に入るので、$(T,(V_t))$ は $H$ の木分解で、各 $H[V_t]$ は完全グラフである。1 により $H$ は弦グラフである。グラフマイナー の補題「袋による分離」の 3 により $H$ の完全部分グラフはある袋に含まれるので、$\omega(H)\le\operatorname{tw}(G)+1$ である。$\square$
2 は Die25 Proposition 12.4.4(p. 375)である。木幅を求めることは、$G$ に辺を加えて弦グラフにするときの最大クリークを最小にする問題と同じになる。
木幅が小さいグラフでは、木分解に沿って小さな表を作り、多くの問題を解ける。独立集合(どの 2 頂点も隣接しない頂点集合)の最大の大きさ $\alpha(G)$ で、その仕組みを示す。
木分解 $(T,(V_t))$ の $T$ に根 $r$ を 1 つ定め、ノード $t$ の子孫($t$ 自身を含む)のなす部分木を $T_t$、$U_t:=\bigcup_{s\in T_t}V_s$ とおく。$V_t$ の独立な部分集合 $S$ について
$$
f_t(S):=\max\{\lvert I\rvert\mid I\text{ は }G[U_t]\text{ の独立集合で }I\cap V_t=S\}
$$
とおく($I=S$ がとれるので最大値は存在する)。
要点:(T3) から、子の部分 $U_c$ どうしは $V_t$ の中でしか交わらず、$U_c\setminus V_t$ の頂点の隣接頂点は $U_c$ に入る。したがって独立集合は「$V_t$ の部分」と「各子の部分」に分けて最適化できる。
次の 3 つを使う。(a) $U_c\cap V_t=V_c\cap V_t$:$v\in V_s\cap V_t$($s\in T_c$)なら $t$ と $s$ を結ぶ道は $c$ を通るので (T3) により $v\in V_c$。(b) 子 $c\ne c'$ について $U_c\cap U_{c'}\subset V_t$:$T_c$ と $T_{c'}$ のノードを結ぶ道は $t$ を通る。(c) $x\in U_c\setminus V_t$ の隣接頂点 $y$ は $U_c$ に入る:$T_x$ は部分木で $T_c$ と交わり $t$ を含まないので $T_x\subset T_c$ であり、(T2) により $x,y$ を含む袋は $T_c$ にある。(T1) から $U_t=V_t\cup\bigcup_aU_{c_a}$ であり、(c) により $G[U_t]$ の辺は $V_t$ の中か、ある $U_{c_a}$ の中にある。
1 の「$\le$」:$I$ を $f_t(S)$ を実現する独立集合とし、$I_a:=I\cap U_{c_a}$、$S'_a:=I_a\cap V_{c_a}$ とおく。(a) により $S'_a\cap V_t=I\cap V_{c_a}\cap V_t=S\cap V_{c_a}$ である。(b) により $U_{c_a}\setminus V_t$ は互いに交わらないので $\lvert I\rvert=\lvert S\rvert+\sum_a\lvert I_a\setminus V_t\rvert$ であり、$\lvert I_a\setminus V_t\rvert=\lvert I_a\rvert-\lvert S'_a\cap V_t\rvert\le f_{c_a}(S'_a)-\lvert S'_a\cap V_t\rvert$ である。
「$\ge$」:各 $a$ で最大を与える $S'_a$ と、$f_{c_a}(S'_a)$ を実現する独立集合 $I_a$ をとり、$I:=S\cup\bigcup_aI_a$ とおく。(a) により $S\cap U_{c_a}=S\cap V_{c_a}\subset I_a$、(b) と $I_b\cap V_t=S\cap V_{c_b}\subset S$ により $I_b\cap U_{c_a}\subset S$ なので、$I\cap U_{c_a}=I_a$ は独立である。$I\cap V_t=S$ も独立で、辺は $V_t$ の中か $U_{c_a}$ の中にあるので $I$ は独立である。数え方は「$\le$」と同じで、$\lvert I\rvert$ は右辺に等しい。
2:(T1) により $U_r=V(G)$ であり、$G$ の独立集合 $I$ は $S=I\cap V_r$ についての $f_r(S)$ の候補である。
3:$f_t$ は $V_t$ の部分集合で添字づけられ、$\lvert V_t\rvert\le w+1$ である。$\square$
上の命題により、木幅が定数 $w$ 以下のグラフでは、木分解が与えられれば表の大きさは $\lvert V(T)\rvert$ の定数倍に収まり、各項目は子の表の項目を調べ尽くして求まる。同じ考え方で、袋の上の「状態」を表にする多くの問題が木分解に沿って解ける(動的計画法)。
木幅はマイナーをとっても増えない(グラフマイナー の定理「木幅の基本性質」の 1)。したがって「木幅が $k$ 未満」という性質はマイナーで閉じ、禁止マイナーで表せる。小さい $k$ と格子については次が知られている。
1 は グラフマイナー の定理「木幅の基本性質」の 3 である。2 は Die25 Proposition 12.6.2(p. 392)で、木幅 $2$ 以下なら $K_4$ を含まないことはグラフマイナー の定理「木幅の基本性質」の 5 にあり、逆はこの記事では証明しない。3 は Robertson と Seymour が 1986 年に示した Die25 Theorem 12.6.3(p. 392)で、この記事では証明しない。$k$ を $r$ の多項式でとれることは Chekuri と Chuzhoy が示した(J. ACM 63, 2016。Die25 第 12 章の注、p. 415)。4 は Die25 Corollary 12.6.4(p. 393)である。$H$ が平面グラフでなければ、格子とそのマイナーはすべて平面グラフなので $H$ をマイナーとして含まず、thm-tw-grid により木幅は有界でない。逆向きは 3 と、平面グラフが十分大きい格子のマイナーであることによる(同書 p. 393)。
4 頂点の閉路 $v_1v_2v_3v_4$ は弦グラフでない。弦 $v_1v_3$ を加えたグラフ $H$ は弦グラフで、$\omega(H)=3$ である。prop-tw-chordal の 2 により $\operatorname{tw}(C_4)\le2$ であり、$C_4$ は森でないので等号が成り立つ。$H$ の袋 $\{v_1,v_2,v_3\}$、$\{v_1,v_3,v_4\}$ による木分解は、prop-tw-chordal の 1 の「完全な袋の木分解」の例になっている。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-tw-grid の $k\ge2$ | $G_{1,1}$(1 頂点) | 木幅が $k$ であること |
| def-tw-bramble の元の連結性 | 辺のない 3 頂点のグラフと $\{\{x,y\},\{y,z\},\{x,z\}\}$ | thm-tw-bramble の評価 |
| thm-tw-minors の 4 の $H$ が平面グラフ | $H=K_5$ と格子 $G_{k,k}$ | 木幅が有界であること |
| prop-tw-dp の木分解の (T3) | 袋 $\{x\},\{y\},\{x\}$ の道($xy$ が辺でない 2 頂点) | 1 の漸化式 |
2 行目:辺のない 3 頂点 $x,y,z$ のグラフの木幅は $0$(1 点ずつの袋を道に並べる)。3 つの集合は共通の頂点をもつので互いに触れ合うが、どの 1 点もすべてとは交わらないので被覆には 2 点が要り、$0\ge2-1$ は成り立たない。
3 行目:$G_{k,k}$ は平面グラフで、平面グラフのマイナーは平面グラフなので(グラフマイナー の定理「平面グラフの禁止マイナー」)$K_5$ をマイナーとして含まない。しかし thm-tw-grid により $\operatorname{tw}(G_{k,k})=k$ は $k$ とともにいくらでも大きくなる。
4 行目:$G$ を 2 頂点 $x,y$ で辺のないグラフとし、道 $t_1t_2t_3$ に袋 $\{x\},\{y\},\{x\}$ をのせる。(T3) は成り立たない。根を $t_2$ にとると、$S=\{y\}$ について 1 の右辺は $1+(1-0)+(1-0)=3$ だが、$G$ の頂点は 2 個しかない。子の部分 $U_{t_1}$ と $U_{t_3}$ が $V_{t_2}$ の外の $x$ を共有するので、$x$ が 2 度数えられる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する