単位円板グラフ
概要
単位円板グラフ（unit disk graph）とは、平面上の相異なる有限個の点を頂点とし、距離が $1$ 以下の 2 点を辺で結んだグラフ、すなわち半径の等しい閉円板の族の交差グラフのことである。$60^\circ$ の扇形の直径が $1$ であることから、1 つの頂点の近傍に互いに隣接しない頂点は 5 個以下で、彩色数はクリーク数 $\omega$ について $3\omega-2$ 以下になる。最大クリークは、中心の座標が与えられれば辺ごとの二部グラフの独立集合の問題に帰着し、多項式時間で求まる。完全グラフを含みペニーグラフを含むクラスで、単位距離グラフとは互いに他方を含まず、通信網のモデルとして使われる。
平面に同じ大きさの円板を何枚か置き、円板を頂点、重なり合う（接する場合も含む）2 枚を辺で結ぶとグラフができる。このようにして得られるグラフを 単位円板グラフ という。円板の中心でいえば、距離が $1$ 以下の 2 点を結んだグラフである。同じ出力の無線局を置いたとき、電波の届く範囲が重なる局どうしの関係がこの形になるので、通信網のモデルとしてもよく使われる。
単位円板グラフでは、どの点も近くにしか隣接頂点をもたないので、1 つの頂点の近傍は少数のクリークに分かれる。この記事では、近傍に互いに隣接しない頂点が 6 個はとれないこと（thm-udk-k16）と、彩色数がクリーク数の 3 倍未満で抑えられること（thm-udk-coloring）を証明する。また、中心の座標が与えられていれば、最大クリークが二部グラフの問題に帰着することを示す（prop-udk-lens、cor-udk-clique）。
定義
この記事では、平面 $\mathbb{R}^2$ に通常の Euclid 距離 $\lvert x-y\rvert$ を入れる（Euclid空間）。グラフは有限な単純グラフ $G=(V,E)$ とし、$\omega(G)$ をクリーク数、$\chi(G)$ を彩色数とする。
グラフ $G=(V,E)$ の 単位円板表現 とは、単射 $\varphi\colon V\to\mathbb{R}^2$ であって、相異なる $u,v\in V$ について
$$
uv\in E\iff\lvert\varphi(u)-\varphi(v)\rvert\le1
$$
を満たすものをいう。単位円板表現をもつグラフを 単位円板グラフ（unit disk graph）という。平面の有限集合 $P$ について、$P$ を頂点集合とし距離 $1$ 以下の 2 点を結んだグラフを $\mathrm{UD}(P)$ と書く。
一般に、集合の族 $(S_v)_{v\in V}$ について、相異なる $u,v$ を $S_u\cap S_v\neq\emptyset$ のときに結んだグラフを、その族の 交差グラフ（intersection graph）という。中心 $x,y$、半径 $1/2$ の 2 つの閉円板が交わることは $\lvert x-y\rvert\le1$ と同値なので、単位円板グラフとは、半径の等しい閉円板の有限族の交差グラフのことである。半径 $1$ の閉円板で「一方が他方の中心を含む」ときに結んでも同じクラスになる。実数直線の有界閉区間の交差グラフがクリーク の記事の区間グラフであり、単位円板グラフはその 2 次元版の 1 つにあたる。
半径 $r$ の円板、すなわち距離 $2r$ 以下で結ぶ規約は、点を $1/(2r)$ 倍すれば上の定義に戻る。距離が $1$ 未満の 2 点だけを結ぶ規約（開円板の交差グラフ）でも、有限グラフのクラスは変わらない。
詳細
有限集合 $P$ の相異なる 2 点の距離のうち、$1$ 未満のものの最大値を $\eta$、$1$ を超えるものの最小値を $\delta$ とする（ないときは $\eta=0$、$\delta=2$ とする）。$\eta< s< 1$ をとって $P$ を $1/s$ 倍すると、もとの距離が $1$ 未満の対はちょうど新しい距離が $1$ 以下の対になる。逆に $1< s< \delta$ をとって $P$ を $1/s$ 倍すると、もとの距離が $1$ 以下の対の新しい距離は $1/s< 1$ 以下になり、もとの距離が $1$ を超える対の新しい距離は $\delta/s> 1$ 以上になるので、もとの距離が $1$ 以下の対はちょうど新しい距離が $1$ 未満の対になる。
直感
頂点 $v$ の隣接頂点はすべて $v$ を中心とする半径 $1$ の円板の中にある。この円板を中心角 $60^\circ$ の扇形に切ると、扇形の直径は $1$ なので、同じ扇形に入った隣接頂点どうしは隣接する。円板全体は 6 枚の扇形で覆えるので、近傍は 6 個のクリークで覆われる。とくに互いに隣接しない近傍の頂点は 6 個未満である。頂点として一番左の点をとると、近傍は右半分の円板に収まり、扇形は 3 枚で足りる。これが彩色数の評価 $3\omega-2$ の源である。
単位円板グラフは単位距離グラフとよく似た名前をもつが、性質はかなり違う。単位円板グラフでは近い点はすべて結ばれるので、完全グラフはいくらでも大きくとれる一方、星形は大きくとれない。単位距離グラフはその逆である。
例と反例
- 完全グラフ $K_n$ は単位円板グラフである。点 $(i/n,0)$（$1\le i\le n$）はどの 2 点も距離 $1$ 未満である。したがって単位円板グラフは平面グラフとは限らない。
- 道グラフ $P_n$ は点 $(i,0)$（$1\le i\le n$）で表現できる。
- 閉路グラフ $C_n$（$n\ge4$）は、1 辺の長さ $1$ の正 $n$ 角形の頂点で表現できる。外接円の半径を $R$ とすると、$k$ 個先の頂点への弦の長さは $2R\sin(k\pi/n)$ で、$2\le k\le n-2$ なら $\sin(k\pi/n)\ge\sin(2\pi/n)$ だから、弦と辺の長さの比は $\sin(k\pi/n)/\sin(\pi/n)\ge2\cos(\pi/n)\ge\sqrt2>1$ である。
- 整数格子 $\mathbb{Z}^2$ の有限部分集合 $P$ について $\mathrm{UD}(P)$ は、上下左右に隣り合う点を結んだ格子グラフである。整数点の距離が $1$ 以下なのは距離がちょうど $1$ のときに限るからである。
閉路グラフ $C_5$ は単位円板グラフで（ex-udk-basic）、$\omega(C_5)=2$、$\chi(C_5)=3$ である。単位円板グラフでは、クリーク の記事の区間グラフと違って、彩色数がクリーク数に等しいとは限らない。
$K_{1,5}$ は単位円板グラフである。中心を原点に、葉を原点から距離 $1$、偏角 $0^\circ,72^\circ,\dots,288^\circ$ の点に置くと、葉どうしの距離は $2\sin36^\circ$ 以上で、$\sin36^\circ>\sin30^\circ=1/2$ より $1$ を超える。一方 $K_{1,6}$ は単位円板グラフでない（thm-udk-k16）。$K_{1,6}$ は $K_7$ の部分グラフなので、単位円板グラフの部分グラフは単位円板グラフとは限らない。
性質
- 単位円板表現を誘導部分グラフの頂点集合に制限すればよい。(2) 一方の表現を平行移動して、2 つの像の点の距離がすべて $1$ を超えるようにすればよい。(3) ペニー配置 $P$ では相異なる 2 点の距離はすべて $1$ 以上なので、距離 $1$ 以下の対はちょうど距離 $1$ の対であり、$\mathrm{UD}(P)$ は $P$ の接触グラフ（ペニーグラフ の定義「ペニーグラフの定義」）に等しい。$\square$
点 $v$ と、$v$ と異なる 2 点 $x,y$ について、角 $\angle xvy$ が $60^\circ$ 以下なら
$$
\lvert x-y\rvert\le\max\{\lvert x-v\rvert,\lvert y-v\rvert\}
$$
である。とくに $\lvert x-v\rvert\le1$、$\lvert y-v\rvert\le1$ なら $\lvert x-y\rvert\le1$ である。
$a:=\lvert x-v\rvert\ge b:=\lvert y-v\rvert>0$ としてよい。角を $\theta$ とすると $\cos\theta\ge1/2$ なので、余弦定理により
$$
\lvert x-y\rvert^2=a^2+b^2-2ab\cos\theta\le a^2+b^2-ab=a^2-b(a-b)\le a^2
$$
である。$\square$
単位円板グラフの各頂点の隣接頂点の中に、互いに隣接しない 6 個の頂点はない。言い換えると、星グラフ $K_{1,6}$ は単位円板グラフの誘導部分グラフにならない。
単位円板表現で頂点を点と同一視する。$v$ の隣接頂点 $w_1,\dots,w_6$ が互いに隣接しないとする。各 $w_i$ の $v$ から見た向き（偏角）を $[0^\circ,360^\circ)$ の値で表し、小さい順に並べ替えて $\phi_1\le\phi_2\le\dots\le\phi_6$ とする。隣り合う向きの差 $\phi_2-\phi_1,\dots,\phi_6-\phi_5$ と $360^\circ-(\phi_6-\phi_1)$ の 6 つは $0$ 以上で和が $360^\circ$ なので、どれかは $60^\circ$ 以下である。その差に対応する 2 点 $w_i,w_j$ について角 $\angle w_ivw_j$ は $60^\circ$ 以下であり、$\lvert w_i-v\rvert\le1$、$\lvert w_j-v\rvert\le1$ なので、lem-udk-angle により $\lvert w_i-w_j\rvert\le1$、すなわち $w_i$ と $w_j$ は隣接する。これは仮定に反する。$\square$
単位円板グラフ $G$ の各頂点の次数（次数(グラフ)）は $6(\omega(G)-1)$ 以下である。
頂点 $v$ の隣接頂点を、$v$ から見た偏角が $[60^\circ(i-1),60^\circ i)$（$i=1,\dots,6$）に入るものの 6 つの組に分ける。同じ組の 2 頂点の $v$ から見た角は $60^\circ$ 未満なので、lem-udk-angle により隣接する。よって各組と $v$ を合わせたものはクリークで、各組の頂点は $\omega(G)-1$ 個以下である。$\square$
一般のグラフでは、次数がどれほど大きくてもクリーク数は $2$ のままでありうる（星グラフ $K_{1,n}$）。cor-udk-degree は、単位円板グラフでは次数の大きい頂点のまわりに必ず大きなクリークがあることを述べている。
空でない単位円板グラフ $G$ について
$$
\omega(G)\le\chi(G)\le3\,\omega(G)-2
$$
である。
左の不等号は一般のグラフで成り立つ（彩色数 の命題「彩色数の基本評価」）。右の不等号を頂点数 $n$ についての帰納法で示す。$n=1$ なら $\chi=\omega=1$ である。
$n\ge2$ とし、単位円板表現で頂点を点と同一視する。$x$ 座標が最小の点の 1 つを $v$ とする。$v$ の隣接頂点 $w$ はすべて $x$ 座標が $v$ 以上なので、$w-v$ の偏角を $(-180^\circ,180^\circ]$ で測ると $[-90^\circ,90^\circ]$ に入る。この区間を 3 つの部分
$$
S_1=[-90^\circ,-30^\circ],\quad S_2=(-30^\circ,30^\circ],\quad S_3=(30^\circ,90^\circ]
$$
に分け、偏角が $S_i$ に入る隣接頂点の集合を $N_i$ とする。同じ $N_i$ の 2 頂点の $v$ から見た角は $60^\circ$ 以下なので、lem-udk-angle により隣接する。したがって $N_i\cup\{v\}$ はクリークであり、$\lvert N_i\rvert\le\omega(G)-1$ となる。よって $v$ の次数は $3(\omega(G)-1)$ 以下である。
$v$ を除いた誘導部分グラフ $G-v$ は単位円板グラフで（prop-udk-basic）、そのクリーク数は $\omega(G)$ 以下だから、帰納法の仮定により $3\omega(G)-2$ 色で塗れる。$v$ の隣接頂点が使う色は $3\omega(G)-3$ 色以下なので、残りの色を $v$ に与えれば $G$ が $3\omega(G)-2$ 色で塗れる。$\square$
証明は、点を $x$ 座標の大きい順に並べて貪欲に色を付けると $3\omega(G)-2$ 色以下で済むことを示している。単位円板表現が与えられていても、3 色で塗れるかどうかの判定は NP 完全であり（CCJ90 Theorem 2.1。証明は概略。NP完全）、上の評価は彩色数の 3 倍以内の近似を与える。
最大クリーク
距離 $1$ 以下の点が互いにすべて近い、という単位円板グラフの性質は、最大クリークを求める問題を扱いやすくする。$p,q\in\mathbb{R}^2$、$d:=\lvert p-q\rvert>0$ について
$$
L_{pq}:=\{x\in\mathbb{R}^2\mid\lvert x-p\rvert\le d,\ \lvert x-q\rvert\le d\}
$$
（2 つの閉円板の共通部分、レンズ形）とおき、$p,q$ を通る直線で $L_{pq}$ を 2 つの閉じた半分 $L_{pq}^+$、$L_{pq}^-$ に分ける。
$L_{pq}^+$ の任意の 2 点の距離は $d$ 以下である。$L_{pq}^-$ についても同じである。
要点：$L_{pq}^+$ は凸なので、距離の最大値は境界の上でとられる。境界は線分 $pq$ と、$p$・$q$ を中心とする中心角 $60^\circ$ の 2 本の弧からなり、この上の 2 点の距離を計算すれば $d$ 以下である。
詳細
座標を $p=(0,0)$、$q=(d,0)$、$L_{pq}^+$ を $y\ge0$ の側にとる。$K:=L_{pq}^+$ は 3 つの閉凸集合の共通部分なので、コンパクトな凸集合である。$K$ の境界の点は、$\lvert x-p\rvert=d$、$\lvert x-q\rvert=d$、$y=0$ のどれかを満たす。$y=0$ の点は線分 $[p,q]$ の点である。$\lvert x-p\rvert=d$ の点は $x=d(\cos\alpha,\sin\alpha)$（$0^\circ\le\alpha\le180^\circ$）と書け、$\lvert x-q\rvert^2=2d^2(1-\cos\alpha)\le d^2$ から $0^\circ\le\alpha\le60^\circ$ である。この弧を $A_p$ とする。同様に $\lvert x-q\rvert=d$ の点は $x=q+d(-\cos\gamma,\sin\gamma)$（$0^\circ\le\gamma\le60^\circ$）と書け、この弧を $A_q$ とする。
$K$ の点 $x$ を通る直線と $K$ の共通部分は線分で、その両端は $K$ の境界の点だから、$K$ の各点は境界の 2 点の凸結合である。線分 $[p,q]$ の点も $p,q$ の凸結合である。$y$ を固定したとき $x\mapsto\lvert x-y\rvert$ は凸関数なので、凸結合の値は両端の値の大きい方以下である。これを $x$ と $y$ の両方に使うと、$K$ の 2 点の距離の最大値は $T:=\{p,q\}\cup A_p\cup A_q$ の 2 点の距離の最大値以下である。
$T$ の 2 点 $s,s'$ を調べる。(i) 一方が $p$ か $q$ なら、$L_{pq}$ の定義から距離は $d$ 以下である。(ii) 両方が $A_p$ にあるなら、$p$ から見た角が $60^\circ$ 以下なので距離は $2d\sin30^\circ=d$ 以下である。$A_q$ も同じである。(iii) $s=d(\cos\alpha,\sin\alpha)\in A_p$、$s'=q+d(-\cos\gamma,\sin\gamma)\in A_q$ のとき、展開すると
$$\frac{\lvert s-s'\rvert^2}{d^2}=(\cos\alpha+\cos\gamma-1)^2+(\sin\alpha-\sin\gamma)^2=3+2\cos(\alpha+\gamma)-2\cos\alpha-2\cos\gamma$$
である。これが $1$ 以下であることは $(1-\cos\alpha)(1-\cos\gamma)\le\sin\alpha\sin\gamma$ と同値であり、半角の公式で書き直すと $4\sin^2\frac\alpha2\sin^2\frac\gamma2\le4\sin\frac\alpha2\cos\frac\alpha2\sin\frac\gamma2\cos\frac\gamma2$ となる。$\sin\frac\alpha2\sin\frac\gamma2=0$ なら明らかで、そうでなければ両辺を割って $\cos\frac{\alpha+\gamma}{2}\ge0$ と同値であり、$\frac{\alpha+\gamma}{2}\le60^\circ$ だから成り立つ。$\square$
prop-udk-lens により、$P\cap L_{pq}^+$ の 2 点も $P\cap L_{pq}^-$ の 2 点も距離が $d$ 以下であり、$d\le1$ なので $G$ で隣接する。よって $H_{pq}$ の辺は、直線 $pq$ の真に正の側の点と真に負の側の点を結ぶものだけである（直線上の点は正の側に入れる）。これは二部グラフである。
$H_{pq}$ の独立集合は $P\cap L_{pq}$ の中の $G$ のクリークなので、右辺は $\omega(G)$ 以下である。逆に、2 頂点以上の最大クリーク $C$ をとり、$C$ の中で距離が最大の 2 点を $p,q$ とする。$C$ の点はすべて $p,q$ から距離 $\lvert p-q\rvert$ 以下なので $C\subset L_{pq}$ であり、$C$ は $H_{pq}$ の独立集合である。よって等号が成り立つ。$\square$
$p=(0,0)$、$q=(1,0)$、$r=(1/2,\sqrt3/2)$、$s=(1/2,-\sqrt3/2)$ とし、$G=\mathrm{UD}(\{p,q,r,s\})$ とする。$r,s$ の距離は $\sqrt3$ で、ほかの 5 対の距離は $1$ なので、$G$ は $K_4$ から辺 $rs$ を除いたグラフである。辺 $pq$ について $L_{pq}$ は 4 点すべてを含み、$r$ は直線 $pq$ の上側、$s$ は下側にある。補グラフ $H_{pq}$ の辺は $rs$ だけで、二部グラフであり、独立数は $3$（たとえば $\{p,q,r\}$）である。$r,s$ は隣接しないので 4 点全体はクリークでなく、$\omega(G)=3$ であり、辺 $pq$ だけで最大値が得られている。
二部グラフの独立数は頂点数から最大マッチングの大きさを引いたものに等しく（独立集合 の系「二部グラフの独立数」）、最大マッチングは効率よく求まる（マッチング）。したがって中心の座標が与えられた単位円板グラフでは、辺ごとに二部グラフの最大マッチングを求めれば、最大クリークが頂点数の多項式時間で求まる（CCJ90 §3、Corollary 3.3）。一般のグラフでは最大クリークを求める問題は NP 困難であり（独立集合）、単位円板グラフでも独立集合を求める問題は NP 困難のままである（CCJ90 Theorem 4.1）。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 円板の半径がすべて等しい（thm-udk-k16） | 原点を中心とする半径 $1$ の円板と、原点から距離 $1+\varepsilon$・偏角 $360^\circ k/n$（$0\le k< n$）を中心とする半径 $\varepsilon$ の円板 $n$ 枚（$0< \varepsilon< \sin(\pi/n)$）の交差グラフ。小さい円板の中心どうしの距離は $2(1+\varepsilon)\sin(\pi/n)>2\varepsilon$ 以上 | 中心の円板の近傍に互いに隣接しない頂点が $n$ 個あり、星グラフ $K_{1,n}$ が誘導部分グラフとして現れる |
| 平面（2 次元）（thm-udk-k16） | $\mathbb{R}^3$ で距離 $1$ 以下を結ぶ。原点と、原点を中心とする半径 $1$ の球面に内接する正二十面体の 12 個の頂点 | 正二十面体の辺の長さは $4/\sqrt{10+2\sqrt5}>1$ なので 12 個の頂点は互いに隣接せず、$K_{1,12}$ が誘導部分グラフになる |
| 誘導部分グラフ（互いに隣接しない）（thm-udk-k16） | 完全グラフ $K_7$（ex-udk-basic） | $K_7$ の 1 頂点と残りの 6 頂点を結ぶ 6 本の辺は $K_{1,6}$ をなすので、誘導部分グラフでない部分グラフとしてなら $K_{1,6}$ は現れる |
補足
単位円板グラフ、単位距離グラフ、マッチ棒グラフ、ペニーグラフ は、いずれも平面上の点の距離で辺を定めるグラフのクラスである。ペニーグラフは単位円板グラフでもありマッチ棒グラフでもあるが（prop-udk-basic）、単位円板グラフと単位距離グラフは互いに他方を含まない（ex-udk-unit-distance）。半径の異なる円板の交差グラフ（円板グラフ）は単位円板グラフより広く、互いに内部が交わらない円板の接触グラフ（コイングラフ）はちょうど平面グラフになることが知られている（ペニーグラフ の補足）。
円板が 3 枚以上あると、どの 2 枚も交わるのに 3 枚に共通の点がないことがある（正三角形の頂点を中心とし、半径を 1 辺の半分にとった 3 枚）。区間グラフのようにクリークを「全員が共有する点」で数えることはできず、cor-udk-clique のようにクリークの中で最も遠い 2 点を手がかりにする必要がある。単位円板グラフの問題は離散幾何学と計算幾何学の境界にあり、通信網の周波数の割り当て（彩色）や中継局の配置（支配集合）のモデルとして研究されている（CCJ90 §1）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
