平面分離定理(planar separator theorem)とは、$n$ 頂点の平面グラフから $O(\sqrt n)$ 個の頂点を除くと、残りを互いに辺で結ばれない 2 つの部分に分け、どちらも $\frac23n$ 個以下の頂点にできるという Lipton と Tarjan の定理である。幅優先探索の木で三角形の 3 頂点の根への道を袋にとると半径 $r$ の平面グラフの木幅は $3r$ 以下になり、層を一定の間隔で除いて平面グラフの木幅が $2\sqrt{3n}$ 未満であることが従う。木分解には各成分の重みを半分以下にする袋があり、その袋が分離集合になる。格子グラフは $\sqrt n$ の程度が改善できないことを示し、木分解に沿った動的計画法で平面グラフの多くの問題が $2^{O(\sqrt n)}$ 程度の時間で解ける。
平面分離定理(planar separator theorem)は、$n$ 頂点の平面グラフから $O(\sqrt n)$ 個の頂点を除くと、残りを互いに辺で結ばれない 2 つの部分 $A,B$ に分け、どちらも $\frac23n$ 個以下の頂点にできる、という定理である。Lipton と Tarjan が 1979 年に示した(LT79)。
一般のグラフでは、こうした小さな分離集合があるとは限らない。たとえば完全グラフ $K_n$ では、2 つに分けるために $\frac n3$ 個以上の頂点を除く必要がある。平面グラフでは、$\sqrt n$ の程度の頂点を除くだけで、グラフを釣り合った 2 つの部分に切れる。$k\times k$ の格子グラフでは $\frac k3=\frac{\sqrt n}3$ 個以上が必要なので、$\sqrt n$ の程度は改善できない。分けた部分にまた定理を使う分割統治により、平面グラフの多くの問題が一般のグラフより速く解ける。
この記事では、幅優先探索の層と木分解を使って、分離集合の大きさが $2\sqrt{3n}+1$ 未満であることを証明する(thm-ps-main)。途中で、$n$ 頂点の平面グラフの 木幅 が $2\sqrt{3n}$ 未満であることも示す(prop-ps-treewidth)。
| 内容 | 場所 |
|---|---|
| 分離集合の定義 | def-ps-separator |
| 主定理 | thm-ps-main |
| 半径の小さい平面グラフの木幅 | lem-ps-radius |
| 平面グラフの木幅 | prop-ps-treewidth |
| 釣り合う袋 | lem-ps-bag |
| 格子と完全グラフ | ex-ps-grid、ex-ps-counter |
この記事のグラフは有限の単純な無向グラフとする。グラフ $G$ の頂点集合を $V(G)$ と書き、$S\subseteq V(G)$ について $G-S$ は $S$ の頂点を除いたグラフである。頂点の重み $w\colon V(G)\to[0,\infty)$ について $w(X):=\sum_{v\in X}w(v)$ とおく。
$n$ 頂点のグラフ $G$ の頂点集合 $S$ について、$V(G)\setminus S$ を $A\sqcup B$ と分け、$A$ と $B$ の間に辺がなく、$\lvert A\rvert,\lvert B\rvert\le\frac23n$ とできるとき、$S$ を $G$ の 分離集合(separator)という。
木分解 $(T,(V_t)_{t\in V(T)})$ と条件 (T1)〜(T3)、木幅 $\operatorname{tw}(G)$ は 木幅 の定義「木分解と木幅」のとおりとする。$\operatorname{tw}(G)\le w$ なら、どの袋も $w+1$ 個以下の頂点をもつ木分解がある。部分グラフの木幅は元のグラフの木幅以下である(木分解の袋をそのまま使えばよい)。
$G$ を $n\ge1$ 頂点の平面グラフ、$w\colon V(G)\to[0,\infty)$ を重みとする。頂点数が $2\sqrt{3n}+1$ 未満の集合 $S\subseteq V(G)$ で、$G-S$ のどの連結成分 $D$ も $w(D)\le\frac12w(V(G))$ をみたすものがある。とくに、$G$ は頂点数が $2\sqrt{3n}+1$ 未満の分離集合をもつ。
まず、ある頂点から距離 $r$ 以内にすべての頂点がある連結な平面グラフの木幅が $3r$ 以下であることを示す(lem-ps-radius)。次に、幅優先探索の層を $h$ 層ごとに除くと、残りは半径の小さい部分に分かれ、除いた層を全部の袋に加えて、木幅が $2\sqrt{3n}$ 未満になることを示す(prop-ps-treewidth)。最後に、どのグラフでも木分解のある袋が重みを半分以下に切ることを示し(lem-ps-bag)、成分を 2 組にまとめる。証明は prf-ps-main にまとめる。
平面に描いたグラフ(平面グラフ図)で、どの面の境界も三角形であるものを 平面三角形分割 という。3 頂点以上の平面グラフ図に、平面グラフ図であるまま辺を加えられなくなるまで加えると、平面三角形分割になる(Die25 Proposition 4.2.8、p. 100)。平面三角形分割の各辺はちょうど 2 つの相異なる面の境界にあり、頂点 $u$ のまわりでは、$u$ に接続する辺 $e_1,\dots,e_d$ と面 $\varphi_1,\dots,\varphi_d$ が交互に並び、$\varphi_{i-1}$ と $\varphi_i$ は辺 $e_i$ をはさんで隣り合う(添字は $d$ を法とする)。
連結な平面グラフ図 $G$ の 双対グラフ $G^*$ は、$G$ の面を頂点とし、$G$ の各辺 $e$ について、$e$ をはさむ 2 つの面を結ぶ辺 $e^*$ をもつ多重グラフである。$G^*$ は連結で、辺集合 $F\subseteq E(G)$ が $G$ の閉路の辺集合であることと、$F^*=\{e^*\mid e\in F\}$ が $G^*$ の極小な切断(ボンド)であることは同値である(Die25 §4.6 と Proposition 4.6.1、pp. 114–115)。
$G$ を連結な平面グラフ、$s\in V(G)$、$r\ge0$ とし、すべての頂点の $s$ からの距離が $r$ 以下であるとする。このとき $\operatorname{tw}(G)\le3r$ である。
$n:=\lvert V(G)\rvert\le2$ なら $\operatorname{tw}(G)\le n-1\le r$ である($n=2$ なら連結なので $r\ge1$)。$n\ge3$ とする。$G$ を平面に描き、平面グラフ図のまま辺を加えて平面三角形分割 $G'$ にする。辺を加えても距離は増えないので $G'$ でも各頂点は $s$ から距離 $r$ 以内にあり、$G'$ の木分解は $G$ の木分解でもある。よって $G$ 自身が平面三角形分割であるとしてよい。
袋.$s$ からの幅優先探索の木 $T$ をとる(幅優先探索)。$T$ の中で頂点 $v$ から $s$ への道の頂点の集合を $P(v)$ とすると、$\lvert P(v)\rvert\le r+1$ である。面 $\varphi$ の境界の三角形を $xyz$ として、袋を
$$
B_\varphi:=P(x)\cup P(y)\cup P(z)
$$
とおく。3 つの道は $s$ を共有するので $\lvert B_\varphi\rvert\le3r+1$ である。
木.$G$ の面の集合 $\Phi$ を頂点とし、$T$ に属さない $G$ の辺 $e$ ごとに、$e$ をはさむ 2 つの面を結んだグラフを $T^*$ とする。$T^*$ は木である。実際、$T^*$ が連結でなければ、空でも全体でもない面の集合 $\Phi'$ で、$\Phi'$ と $\Phi\setminus\Phi'$ をつなぐ $G^*$ の辺がすべて $T$ の辺の双対であるものがある。$G^*$ は連結なのでこの切断は空でなく、ボンドを含み、そのボンドは $G$ の閉路 $C$ の双対である。$C$ の辺は $T$ に属するので、木 $T$ が閉路を含むことになり矛盾する。また、Euler の公式 $n-m+\lvert\Phi\rvert=2$(平面グラフ の定理「Eulerの公式」、$m$ は辺の数)から、$T^*$ の辺の数は $m-(n-1)=\lvert\Phi\rvert-1$ である。辺が頂点より 1 少ない連結グラフは木である。
(T1)(T2).各頂点と各辺はある面の境界の三角形にあり、その面の袋に入る。
(T3).頂点 $v$ について、$v\in B_\varphi$ であることは、$\varphi$ の境界に $T$ での $v$ の子孫($v$ 自身を含む)があることと同値である。この性質をもつ面の集合を $\Phi_v$ とし、$T^*$ の中で $\Phi_v$ が連結であることを、$T$ の葉から根へ向かう帰納法で示す。
$u$ のまわりの辺 $e_1,\dots,e_d$ と面 $\varphi_1,\dots,\varphi_d$ を上のように並べ、$u$ が根でなければ親への辺を $e_d$ とする。$u$ に接続する $T$ の辺は、親への辺と子への辺だけである。$1\le i\le d-1$($u$ が根なら $1\le i\le d$)について、$\varphi_{i-1}$ と $\varphi_i$($\varphi_0:=\varphi_d$)は次のどちらかでつながる。
幅優先探索の木の中の葉が 3 つの部分木を袋にとる方法(上の証明では三角形の 3 頂点から根への道の和)は、直径 $D$ の平面グラフの木幅が $O(D)$ であることの証明の方針として Epp00 の序論(Lemma 1 とその後の説明)に述べられている。
$n\ge1$ 頂点の平面グラフ $G$ について $\operatorname{tw}(G)< 2\sqrt{3n}$ である。
連結成分ごとの木分解の木を辺で結ぶと全体の木分解になる(成分の頂点集合は交わらないので (T3) は保たれる)。成分の頂点数は $n$ 以下なので、$G$ は連結としてよい。
頂点 $s$ を 1 つとり、$s$ からの距離が $i$ の頂点の集合を $L_i$(第 $i$ 層)とする。$h:=\lceil\sqrt{n/3}\,\rceil\ge1$ とおく。$j=0,1,\dots,h-1$ について $S_j:=\bigcup_{i\equiv j\ (\mathrm{mod}\ h)}L_i$ とおくと、$\sum_j\lvert S_j\rvert=n$ なので $\lvert S_j\rvert\le n/h$ となる $j$ がある。それを 1 つ固定する。
帯に分かれること.辺の両端の層の番号の差は $1$ 以下である(幅優先探索の層の性質)。$a\equiv j\ (\mathrm{mod}\ h)$ をみたす整数 $a\ge j-h$ について、帯 $Z_a:=L_{a+1}\cup\dots\cup L_{a+h-1}$(負の番号の層は空とする)をとると、$G-S_j$ は帯 $G[Z_a]$ たちの交わらない和で、異なる帯の間に辺はない。
各帯の木幅は $3(h-1)$ 以下.$a< 0$ の帯は $L_0\cup\dots\cup L_{j-1}$ である。どの頂点も幅優先探索の木の道で $s$ と結ばれ、その道はこの帯の中にあるので、$G[Z_a]$ は連結で、各頂点の $s$ からの距離は $j-1\le h-2$ 以下である。lem-ps-radius により木幅は $3(h-1)$ 以下である。
$a\ge0$ とする。$H:=G[L_0\cup\dots\cup L_{a+h-1}]$ とし、$X:=L_0\cup\dots\cup L_a$ を 1 点 $x$ に縮約したグラフを $H/X$ とする。$X$ は幅優先探索の木の道で $s$ と結ばれるので連結であり、$H/X$ は $G$ のマイナーなので平面グラフである(グラフマイナー の定理「平面グラフの禁止マイナー」)。$L_{a+i}$($1\le i\le h-1$)の頂点 $y$ から $s$ への最短路は層 $a+i,a+i-1,\dots,a$ を順に通るので、その最後の $i$ 本の辺は $H$ の中にあり、$H/X$ で $y$ は $x$ から距離 $i\le h-1$ 以内にある。$H/X$ は連結なので、lem-ps-radius により $\operatorname{tw}(H/X)\le3(h-1)$ である。$G[Z_a]$ は $H/X$ から $x$ を除いたグラフなので、木幅は $3(h-1)$ 以下である。
$S_j$ を戻す.帯ごとの木分解の木を辺で結ぶと、$G-S_j$ の幅 $3(h-1)$ 以下の木分解になる。そのすべての袋に $S_j$ を加えると $G$ の木分解になる:$S_j$ の頂点はすべての袋に入り、$S_j$ の頂点と $S_j$ の外の頂点 $u$ を結ぶ辺は $u$ を含む袋に入るからである。よって
$$
\operatorname{tw}(G)\le3h-3+\frac nh.
$$
$h<\sqrt{n/3}+1$ から $3h-3<\sqrt{3n}$、$h\ge\sqrt{n/3}$ から $n/h\le\sqrt{3n}$ なので、$\operatorname{tw}(G)<2\sqrt{3n}$ である。$\square$
層を $h$ 層ごとに除いて半径の小さい部分に分ける方法は、Baker の近似算法の考え方として Epp00 の序論に述べられている。平面グラフの格子マイナーについての定理から、Cyg15 Corollary 7.24(p. 202)は $\operatorname{tw}(G)<\frac92\lceil\sqrt{n+1}\,\rceil$ を導いている。
グラフ $G$ の木分解 $(T,(V_t))$ と重み $w\colon V(G)\to[0,\infty)$ について、ある袋 $V_t$ があり、$G-V_t$ のどの連結成分 $D$ も $w(D)\le\frac12w(V(G))$ をみたす。
$W:=w(V(G))$ とおく。$T$ に根を定め、ノード $t$ の子孫($t$ 自身を含む)の袋の和集合を $U_t$ とする。根 $\rho$ では $U_\rho=V(G)$ なので $w(U_\rho)\ge\frac12W$ であり、$w(U_t)\ge\frac12W$ をみたすノードのうち根からの距離が最大のもの $t$ をとる。$t$ の子 $c$ では $w(U_c)<\frac12W$ である。
$G-V_t$ の連結成分 $D$ をとる。$t$ と子 $c$ を結ぶ辺について、グラフマイナー の補題「袋による分離」により、$c$ の側の頂点集合 $U_c$ と反対側の頂点集合 $U'$ の共通部分は $V_c\cap V_t\subseteq V_t$ で、$U_c\setminus U'$ と $U'\setminus U_c$ の間に辺はない。$D$ は $V_t$ と交わらず連結なので、$D\subseteq U_c\setminus V_t$ か $D\cap U_c=\emptyset$ のどちらかである。前者なら $w(D)\le w(U_c)<\frac12W$ である。すべての子 $c$ で後者なら、$D$ は $V_t$ とも交わらないので $D\cap U_t=\emptyset$ であり、$w(D)\le W-w(U_t)\le\frac12W$ である。$\square$
この補題は Cyg15 Lemma 7.19(pp. 193–194)と同じ内容で、同じ方針で証明されている。
prop-ps-treewidth により $G$ には袋の頂点数が $2\sqrt{3n}+1$ 未満の木分解がある。lem-ps-bag の袋を $S$ とすれば前半が成り立つ。
後半を示す。$w\equiv1$ として $S$ をとり、$G-S$ の連結成分の頂点数を $d_1,\dots,d_p$、$N:=n-\lvert S\rvert=\sum_id_i$ とする。各 $d_i\le\frac n2$ である。$d_i\ge\frac N3$ となる成分があれば、それを $A$、残りの成分の和を $B$ とすると $\lvert A\rvert\le\frac n2$、$\lvert B\rvert\le\frac23N$ である。どの $d_i$ も $\frac N3$ より小さければ、成分を 1 つずつ $A$ に加え、$\lvert A\rvert\ge\frac N3$ となった時点で止める。最後に加えた成分は $\frac N3$ 未満なので $\lvert A\rvert<\frac23N$ で、$B$ を残りの成分の和とすると $\lvert B\rvert\le\frac23N$ である。どちらの場合も $A,B$ の間に辺はなく、$\lvert A\rvert,\lvert B\rvert\le\frac23n$ である。$\square$
$k\times k$ の格子グラフ $G_{k,k}$($n=k^2$。格子グラフ)の分離集合 $S$ は $\lvert S\rvert\ge\frac k3=\frac{\sqrt n}3$ をみたす。実際、$\lvert S\rvert<\frac k3$ とすると、$S$ と交わらない行が $k-\lvert S\rvert$ 本以上、交わらない列が 1 本以上ある。交わらない行と列はたがいに $S$ の外の頂点で交わるので、それらの和は $G-S$ の 1 つの連結成分に入り、その成分は $k(k-\lvert S\rvert)>\frac23k^2$ 個以上の頂点をもつ。$A$ と $B$ の間に辺はないので連結成分は $A$ か $B$ の一方に含まれ、$\lvert A\rvert,\lvert B\rvert\le\frac23n$ に反する。したがって thm-ps-main の $\sqrt n$ の程度は改善できない。$G_{k,k}$ の木幅が $k$ であること(木幅 の定理「格子グラフの木幅」)も、prop-ps-treewidth の程度が改善できないことを示している。
平面グラフ図は多項式時間で求まり(平面性判定)、prf-ps-treewidth の構成(幅優先探索、三角形分割、層の選び方、縮約)もどれも多項式時間でできるので、$n$ 頂点の平面グラフについて幅 $2\sqrt{3n}$ 未満の木分解が多項式時間で得られる。木幅 の命題「独立集合の動的計画法」により、幅 $w$ の木分解に沿った表の大きさの合計は(ノードの数)$\times2^{w+1}$ 以下なので、平面グラフの独立集合の最大の大きさは $2^{O(\sqrt n)}n^{O(1)}$ 時間で求まる。頂点の部分集合をすべて調べる方法の $2^n n^{O(1)}$ 時間に比べて、指数の $n$ が $\sqrt n$ の程度に下がる。
Nac20 p. 108 は、Miller、Teng、Thurston、Vavasis が 円充填定理 を使って平面分離定理の新しい証明を与えたことを紹介している:グラフを単位球面に円充填し、Möbius 変換で正規化して原点を通る平面を無作為にとると、その平面と交わる円板の頂点の集合が、高い確率で $O(\sqrt n)$ 個の頂点からなり、残りの各成分を $\frac34n$ 個以下にする。この記事ではこの証明は扱わない。また Cyg15 演習 7.38(p. 234)は、頂点数 $\frac92\sqrt{n+1}$ 以下の集合 $S$ で、与えた頂点集合 $W$ について $G-S$ の各成分が $W$ の頂点を $\frac12\lvert W\rvert$ 個以下しか含まないものがあることを示す演習で、p. 240 のヒントは Lemma 7.19(lem-ps-bag と同じ内容)と Corollary 7.24 を使うよう述べている。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 平面グラフ(thm-ps-main) | 完全グラフ $K_n$($n\ge114$) | 頂点数 $2\sqrt{3n}+1$ 未満の分離集合がある |
| 平面グラフ(lem-ps-radius) | $K_n$($n\ge5$)と任意の頂点 $s$、$r=1$ | $\operatorname{tw}\le3r=3$ |
| 木分解の (T3)(lem-ps-bag) | 閉路 $C_n$($n\ge5$)と、辺 $v_1v_2,v_2v_3,\dots,v_nv_1$ を袋としてこの順に道に並べたもの | ある袋 $V_t$ で $G-V_t$ の各成分の頂点数が $\frac n2$ 以下 |
1 行目:$K_n-S$ は完全グラフで 1 つの連結成分なので、$A$ か $B$ の一方に入り、$n-\lvert S\rvert\le\frac23n$、つまり $\lvert S\rvert\ge\frac n3$ が要る。$n\ge114$ なら $\frac n3>2\sqrt{3n}+1$ である($\sqrt n=t$ として $\frac{t^2}3-2\sqrt3\,t-1$ は $t\ge\sqrt{114}$ で正)。
2 行目:$K_n$ のどの頂点も $s$ から距離 1 以内にあるが、$\operatorname{tw}(K_n)=n-1\ge4$ である(木幅 の例「小さなグラフの木幅」)。$K_n$($n\ge5$)は平面グラフでない。
3 行目:(T1)(T2) は成り立つが、$v_1$ は最初と最後の袋にだけ入り、その間の袋に入らないので (T3) が満たされない。どの袋も隣り合う 2 頂点からなり、それを除いた $C_n$ は $n-2$ 頂点の道で、$n\ge5$ なら $n-2>\frac n2$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する