ペニーグラフ

同義語：penny graph最小距離グラフ

概要

定義

本記事では、平面 $\mathbb{R}^2$ に通常の Euclid距離 $|p-q|$ を入れて考える。グラフは特に断らない限り有限な単純グラフとし、2 点 $p,q$ を結ぶ線分を $[p,q]$ と書く。

ペニーグラフの定義

平面の有限部分集合 $P\subset\mathbb{R}^2$ がペニー配置（penny configuration）であるとは、相異なる任意の 2 点 $p,q\in P$ について $|p-q|\ge1$ が成り立つことをいう。ペニー配置 $P$ の接触グラフ（contact graph）$G(P)$ とは、$P$ を頂点集合とし、$|p-q|=1$ となる 2 点 $p,q$ を辺で結んだグラフ
$$G(P):=\bigl(P,\ \{\{p,q\}\mid p,q\in P,\ |p-q|=1\}\bigr)$$
のことをいう。あるペニー配置の接触グラフと同型（グラフ同型）なグラフをペニーグラフ（penny graph）という。

$P$ の各点を中心とする半径 $1/2$ の閉円板を考えると、$|p-q|\ge1$ は 2 つの円板の内部が交わらない（重なり合わない）ことを、$|p-q|=1$ は 2 つの円板がちょうど 1 点で接することを意味する。すなわちペニーグラフとは、同じ大きさの硬貨（ペニー）を机の上に重ならないように並べ、硬貨を頂点、接している 2 枚の硬貨の組を辺として得られるグラフである。半径 $1/2$ の代わりに任意の半径 $r>0$ の円板を用いても、配置を $2r$ 倍すれば同じことなので、ペニーグラフの概念は変わらない。文献によっては単位円板（半径 $1$、中心間の距離 $2$ で接する）を用いる。

最小距離グラフ

2 点以上からなる平面の有限部分集合 $P$ に対し、$\delta(P):=\min\{|p-q|\mid p,q\in P,\ p\neq q\}$ を $P$ の最小距離といい、$P$ を頂点集合とし、$|p-q|=\delta(P)$ となる 2 点 $p,q$ を辺で結んだグラフを $P$ の最小距離グラフ（minimum distance graph）という。

辺を持つペニーグラフはちょうど最小距離グラフに同型なグラフである（prop-penny-min-distance）。このためペニーグラフは最小距離グラフ、最近点対グラフ（closest-pairs graph）ともよばれる。

直感

ペニーグラフは、硬貨を平面に重ならないように並べたときの「接している」という関係だけを取り出したグラフである。硬貨どうしは重なれないので、1 枚の硬貨に接する硬貨は 6 枚までであり、並べ方全体はおおむね三角格子（六角形状の詰め込み）に近づくほど接触が多くなる。同じ幾何学的制約を持つマッチ棒グラフ（長さ $1$ の棒を交差しないように並べる）と比べると、ペニーグラフでは接していない硬貨どうしも距離 $1$ 以上離れていなければならないという制約が加わり、その分だけクラスは狭く、次数・辺数・彩色数に関して強い制限が成り立つ。

例と反例

道・閉路・格子のペニーグラフ

点 $(1,0),(2,0),\dots,(n,0)$ はペニー配置であり、その接触グラフは道グラフ $P_n$ である。
$n\ge3$ のとき、1 辺の長さ $1$ の正 $n$ 角形の頂点はペニー配置であり（外接円の半径を $1$ に正規化すると、辺に沿って $k$ 個先の頂点を結ぶ弦の長さは $2\sin(k\pi/n)$（$2\le k\le n-2$）で、辺長 $2\sin(\pi/n)$ より大きい。比は相似で変わらない。$n=3$ では対角線はない）、接触グラフは閉路グラフ $C_n$ である。
正方格子 $\mathbb{Z}^2$ の有限部分集合 $P$ はペニー配置である。$(a,b)\in\mathbb{Z}^2$、$(a,b)\neq(0,0)$ について $a^2+b^2\ge1$ であり、等号は $(a,b)\in\{(\pm1,0),(0,\pm1)\}$ のときに限るので、接触グラフは $P$ の点のうち上下左右に隣り合うものを結んだ格子グラフである。
三角格子 $\Lambda=\{mp+nq\mid m,n\in\mathbb{Z}\}$（$p=(1,0)$、$q=(1/2,\sqrt{3}/2)$）の有限部分集合もペニー配置であり、接触グラフは三角格子グラフの誘導部分グラフである（マッチ棒グラフの記事の定義「三角格子グラフ」）。特に、1 辺の長さ $s$ の正六角形状の部分 $H_s$ は $3s^2+3s+1$ 個の頂点と $9s^2+3s$ 本の辺を持つペニーグラフである（マッチ棒グラフの記事の例「三角格子の六角形状の部分」）。

六角形の車輪

原点 $v$ と、原点から距離 $1$ で偏角 $0^\circ,60^\circ,\dots,300^\circ$ の 6 点 $w_0,\dots,w_5$ からなる集合はペニー配置である。$w_i$ と $w_{i+1}$（添字は $6$ を法として考える）の距離は $2\sin30^\circ=1$、$w_i$ と $w_{i+2}$ の距離は $2\sin60^\circ=\sqrt{3}$、$w_i$ と $w_{i+3}$ の距離は $2$ だから、接触グラフは中心 $v$ が 6 頂点の閉路 $w_0w_1\cdots w_5w_0$ のすべての頂点と隣接する車輪グラフ $W_6$ である。$v$ の次数は $6$ であり、prop-penny-max-degree の上界を達成する。

反例：星グラフ $K_{1,7}$

星グラフ $K_{1,7}$（完全二部グラフ）はマッチ棒グラフであるが（マッチ棒グラフの記事の例「星グラフの表現」）、中心の頂点の次数が $7$ なので prop-penny-max-degree によりペニーグラフではない。満たす性質：マッチ棒グラフである。満たさない性質：ペニーグラフである。破る含意：「マッチ棒グラフ ⇒ ペニーグラフ」は成り立たない（逆向きは prop-penny-matchstick により成り立つ）。

反例：ペニーグラフの部分グラフ

ex-penny-hexagonal-wheel の車輪 $W_6$ から 1 本の辺 $vw_5$ を取り除いたグラフ $G$ は、ペニーグラフ $W_6$ の部分グラフであるが、ペニーグラフではない。実際、$G$ がペニー配置 $P$ の接触グラフと同型であるとし、頂点とその像を同一視する。$w_0,\dots,w_4$ はいずれも $v$ から距離 $1$ にあり、$w_i$ と $w_{i+1}$（$0\le i\le3$）の距離は $1$ だから、$w_{i+1}$ は $v$ を中心とする単位円周上で $w_i$ から偏角が $\pm60^\circ$ だけ離れた 2 点のいずれかである。$w_0$ の偏角を $0^\circ$ とすると、$w_1$ の偏角は $\pm60^\circ$ であり、対称性により $60^\circ$ としてよい。$w_2$ の偏角は $0^\circ$ または $120^\circ$ であるが、$w_2\neq w_0$ なので $120^\circ$ である。同様に $w_3$、$w_4$ の偏角はそれぞれ $180^\circ$、$240^\circ$ である。$w_5$ は $w_4$ と $w_0$ の両方から距離 $1$ にある。$|w_4-w_0|=2\sin60^\circ=\sqrt{3}$ であり、三角形 $vw_4w_0$ の辺 $w_4w_0$ に対する高さは $1/2$ だから、$w_4$ と $w_0$ の両方から距離 $1$ にある点は $v$ と、直線 $w_4w_0$ に関する $v$ の鏡像 $v'$ の 2 点であり、$|v-v'|=1$ である。$w_5\neq v$ なので $w_5=v'$ となり $|v-w_5|=1$、すなわち $v$ と $w_5$ は接触グラフにおいて隣接する。これは $G$ に辺 $vw_5$ がないことに反する。
満たす性質：ペニーグラフの部分グラフである（さらに、マッチ棒グラフの部分グラフなのでマッチ棒グラフでもある）。満たさない性質：ペニーグラフである。破る含意：「ペニーグラフの部分グラフ ⇒ ペニーグラフ」は成り立たない。ペニーグラフの誘導部分グラフはペニーグラフである（prop-penny-induced）が、辺だけを取り除くことは一般に許されない。接触グラフでは、距離 $1$ の 2 点は必ず辺で結ばれるからである。

性質

ペニーグラフはマッチ棒グラフである

$P$ をペニー配置とすると、包含写像 $P\to\mathbb{R}^2$ は接触グラフ $G(P)$ のマッチ棒表現である。したがってペニーグラフはマッチ棒グラフであり、特に平面グラフかつ単位距離グラフである。

マッチ棒表現の 3 条件（マッチ棒グラフの記事の定義）を確かめる。包含写像は単射であり、各辺 $pq$ について $|p-q|=1$ だから条件 1 が成り立つ。
条件 3：頂点 $w\in P$ が、$w$ に接続しない辺 $pq$ の線分 $[p,q]$ 上にあるとすると、$w\neq p,q$ で $|p-w|+|w-q|=|p-q|=1$ となり、$|p-w|,|w-q|$ の一方は $1/2$ 以下となって $P$ がペニー配置であることに反する。
条件 2：相異なる 2 辺 $pq$、$rs$ をとる。両者が端点を共有する場合、たとえば $p=r$ なら、線分 $[p,q]$ と $[p,s]$ は $p$ から出る 2 本の長さ $1$ の線分であり、$q\neq s$ なので同一の半直線上にはなく、共通部分は $\{p\}$ だけである。端点を共有しない場合、$p,q,r,s$ は相異なる 4 点であり、線分 $[p,q]$ と $[r,s]$ が点 $x$ を共有すると仮定する。条件 3 の議論により $x$ は $p,q,r,s$ のいずれでもないので、$x$ は両線分の内部の点である。三角不等式により
$$|p-r|+|q-s|\le(|p-x|+|x-r|)+(|q-x|+|x-s|)=(|p-x|+|x-q|)+(|r-x|+|x-s|)=|p-q|+|r-s|=2$$
である。$|p-r|\ge1$ かつ $|q-s|\ge1$ だから両辺は $2$ に等しく、2 つの三角不等式はともに等号で成り立つ。すなわち $x\in[p,r]$ かつ $x\in[q,s]$ であり、$p,x,r$ は同一直線上、$q,x,s$ も同一直線上にある。$x$ は $[p,q]$ の内部の点でもあるので $p,x,q$ も同一直線上にあり、結局 $p,q,r,s,x$ はすべて 1 本の直線 $L$ 上にある。$L$ 上で、長さ $1$ の 2 つの線分 $[p,q]$、$[r,s]$ が内部の点 $x$ を共有し、かつ $\{p,q\}\neq\{r,s\}$ だから、一方の線分の端点が他方の線分の内部にある。たとえば $r\in(p,q)$ なら $|p-r|+|r-q|=1$ となって $|p-r|<1$ または $|r-q|<1$ となり、ペニー配置であることに反する（他の場合も同様）。よって端点を共有しない 2 辺の線分は交わらない。$\square$

誘導部分グラフと非交和

ペニーグラフの任意の誘導部分グラフはペニーグラフである。また 2 つのペニーグラフの非交和（グラフの記事の $G\cup H$）はペニーグラフである。

$P$ をペニー配置とし、$Q\subset P$ とすると、$Q$ もペニー配置であり、$G(Q)$ は $G(P)$ の $Q$ による誘導部分グラフである（$Q$ の 2 点が $G(Q)$ で隣接することと $G(P)$ で隣接することは、どちらも距離が $1$ であることと同値）。非交和については、マッチ棒グラフの記事の命題「マッチ棒グラフの基本性質」と同様に、一方のペニー配置を十分遠くへ平行移動して、2 つの配置に含まれる点の間の距離をすべて $1$ より大きくすればよい。このとき合併はペニー配置であり、異なる配置の点の間には辺が生じないので、接触グラフは 2 つの接触グラフの非交和である。$\square$

最小距離グラフによる特徴付け

少なくとも 1 本の辺を持つグラフ $G$ について、$G$ がペニーグラフであることと、$G$ が平面のある有限部分集合の最小距離グラフと同型であることは同値である。辺を持たないグラフ $E_n$（$n\ge2$）はペニーグラフであるが、最小距離グラフと同型ではない。

$G$ が辺を持つペニーグラフであるとし、$G\cong G(P)$ となるペニー配置 $P$ をとる。$P$ の相異なる 2 点の距離は $1$ 以上だから $\delta(P)\ge1$ であり、$G(P)$ が辺を持つので距離 $1$ の 2 点があり $\delta(P)=1$ である。よって $G(P)$ は、距離がちょうど $\delta(P)=1$ の 2 点を結んだグラフ、すなわち $P$ の最小距離グラフに等しい。
逆に、$G$ が 2 点以上の有限集合 $P$ の最小距離グラフに同型であるとする。$P':=\{p/\delta(P)\mid p\in P\}$ とおくと、$P'$ の相異なる 2 点の距離は $1$ 以上、すなわち $P'$ はペニー配置であり、$p,q\in P$ について $|p-q|=\delta(P)$ であることと $|p/\delta(P)-q/\delta(P)|=1$ であることは同値だから、$p\mapsto p/\delta(P)$ は $P$ の最小距離グラフから $G(P')$ への同型である。よって $G$ はペニーグラフである。
最後に、点 $(2,0),(4,0),\dots,(2n,0)$ はペニー配置であり、相異なる 2 点の距離は $2$ 以上なので接触グラフは $E_n$ である。一方、2 点以上の有限集合の最小距離グラフは、最小距離を実現する 2 点を結ぶ辺を必ず持つので、$E_n$ と同型ではない。$\square$

単位円周上の点の間の角

点 $v\in\mathbb{R}^2$ から距離 $1$ にある相異なる 2 点 $w,w'$ について、$|w-w'|\ge1$ であることと、$w,w'$ の $v$ を中心とする偏角の差 $\theta\in(0^\circ,180^\circ]$ が $60^\circ$ 以上であることは同値である。

二等辺三角形 $vww'$ において $|w-w'|=2\sin(\theta/2)$ であり、$\theta/2\in(0^\circ,90^\circ]$ の範囲で $\sin$ は単調増加だから、$2\sin(\theta/2)\ge1=2\sin30^\circ$ と $\theta/2\ge30^\circ$ は同値である。$\square$

最大次数の上界

ペニーグラフの各頂点の次数（次数(グラフ)）は $6$ 以下である。上界 $6$ は ex-penny-hexagonal-wheel により達成される。

$P$ をペニー配置、$v\in P$ とし、$v$ の隣接頂点を $v$ を中心とする偏角の順に $w_0,w_1,\dots,w_{k-1}$ とする（$k=\deg v$）。$k\ge7$ と仮定する。隣り合う 2 点 $w_i,w_{i+1}$（$w_k:=w_0$）の偏角の差 $\theta_i$ は正で、$\sum_{i=0}^{k-1}\theta_i=360^\circ$ だから、ある $i$ について $\theta_i\le360^\circ/7<60^\circ$ である。$w_i,w_{i+1}$ はともに $v$ から距離 $1$ にあるので、lem-penny-angle により $|w_i-w_{i+1}|<1$ となり、$P$ がペニー配置であることに反する。$\square$

次数が 3 以下の頂点の存在

空でないペニーグラフには次数が $3$ 以下の頂点が存在する。したがってペニーグラフは $3$-退化（退化数が $3$ 以下）である。

$P$ をペニー配置とする。$|P|=1$ なら唯一の頂点の次数は $0$ である。$|P|\ge2$ とし、$P$ の凸包の頂点を一つとり $v$ とする。$v$ は凸包の頂点だから、$v$ を頂点とする角度 $\alpha<180^\circ$ の閉じた扇形 $S$ で $P\subset S$ となるものがある（$P$ の点がすべて 1 直線上にあるときは $v$ をその端の点にとり、$S$ は $v$ から出る半直線、$\alpha=0^\circ$ とする）。$v$ の隣接頂点 $w_1,\dots,w_k$ を、$S$ の一方の境界の半直線から測った偏角 $\phi_1<\phi_2<\cdots<\phi_k$ の順に並べると、$0^\circ\le\phi_1$、$\phi_k\le\alpha$ であり、$w_i,w_{i+1}$ は $v$ から距離 $1$ で互いの距離が $1$ 以上だから、lem-penny-angle により $\phi_{i+1}-\phi_i\ge60^\circ$ である（偏角の差は $\alpha<180^\circ$ 以下なので補題が適用できる）。よって $60^\circ(k-1)\le\phi_k-\phi_1\le\alpha<180^\circ$ となり、$k-1<3$、すなわち $k\le3$ である。
後半について、ペニーグラフの誘導部分グラフはペニーグラフだから（prop-penny-induced）、空でない任意の誘導部分グラフに次数 $3$ 以下の頂点があり、これは $3$-退化であることの定義である。$\square$

ペニーグラフの 4-彩色可能性

ペニーグラフは 4 色で頂点彩色できる。すなわち彩色数は $4$ 以下である。

頂点数 $n$ に関する数学的帰納法で示す。$n=0$ なら示すことはない。$n\ge1$ のとき、prop-penny-degree-three により次数 $3$ 以下の頂点 $v$ をとる。$v$ を取り除いた誘導部分グラフ $G-v$ はペニーグラフであり（prop-penny-induced）、帰納法の仮定により 4 色で彩色できる。$v$ の隣接頂点は 3 個以下なので、それらに使われていない色が 4 色の中に少なくとも 1 色あり、その色を $v$ に与えれば $G$ の 4-彩色が得られる。$\square$

ペニーグラフは平面グラフなので、4-彩色可能性は四色定理からも従うが、上の証明はそれによらない初等的なものである。
ペニーグラフの辺数については、頂点数だけで決まる正確な最大値が知られている。

ペニーグラフの辺数の最大値

$n\ge1$ 個の頂点を持つペニーグラフの辺数は $\lfloor3n-\sqrt{12n-3}\rfloor$ 以下である。さらに、各 $n$ についてちょうど $\lfloor3n-\sqrt{12n-3}\rfloor$ 本の辺を持つ $n$ 頂点のペニーグラフが存在する。

辺数の最大値の出典と証明の概略

この定理は、Reutter が 1972 年に問題として提出し（Reutter1972）、Harborth が 1974 年に証明した（Harborth1974）。証明は PA95 定理 13.12 にも掲載されている。同じ上界は任意のマッチ棒グラフについても成り立つことが、2024 年に Lavollée と Swanepoel によって証明された（LS24）。$n=3s^2+3s+1$ のときは ex-penny-basic の六角形状の部分 $H_s$ が等号を与える。
上界の証明の概略は次のとおりである（詳細は上の文献に譲る）。$n$ に関する帰納法を用いる。$n=1$ なら $|E|=0=3-\sqrt{9}$、$n=2$ なら $|E|\le1\le\lfloor6-\sqrt{21}\rfloor$ で成り立つので、以下 $n\ge3$ とし、$n$ 頂点で辺数が最大のペニーグラフ $G$ をとる。$G$ が連結でない場合は、成分に分けて $G=G_1\cup G_2$（頂点数 $m_1,m_2\ge1$、$m_1+m_2=n$）とすると、帰納法の仮定と平方根の凹性から $|E|\le 3n-(3+\sqrt{12n-15})\le 3n-\sqrt{12n-3}$ となる（後者は $(3+\sqrt{12n-15})^2=12n-6+6\sqrt{12n-15}\ge 12n-3$、$n\ge2$、から従う）。$G$ が連結で切断点を持つ場合は、切断点 $v$ を両側に含めて $G=G_1\cup G_2$（頂点数 $m_1,m_2\ge2$、$m_1+m_2=n+1$）と分けると、帰納法の仮定から $|E|\le 3(m_1+m_2)-\sqrt{12m_1-3}-\sqrt{12m_2-3}=3n+3-(\sqrt{12m_1-3}+\sqrt{12m_2-3})$ となり、平方根の凹性から右辺の括弧内は $m_1=2$ で最小、$\sqrt{21}+\sqrt{12n-15}\ge 3+\sqrt{12n-3}$（$n\ge3$）を用いて所望の上界を得る。そうでない場合には、$B:=|E|$ とおき、$G$ の外側の境界をなす閉路 $C$（長さ $a$）をとり、lem-penny-angle によって $C$ 上の各頂点の内角が（次数 $-1$）$\times60^\circ$ 以上であることと、$a$ 角形の内角の和が $(a-2)\times180^\circ$ であることから、$C$ 上の各頂点 $v$ について次数から $2$ を引いた量の総和 $\sum_{v\in C}(\deg v-2)$ が $2a-6$ 以下であると評価する（$C$ の弦は両端で 2 回数えられる）。$n=a$（全頂点が外側閉路上。辺は $C$ の $a$ 本と、両端で数えて $2a-6$ 以下だから $a-3$ 本以下の弦）の場合を含め、$B\le 2n-3$ の場合は、$2n-3\le 3n-\sqrt{12n-3}$（$(n+3)^2-(12n-3)=(n-3)^2+3>0$ から従う）により直接従う。以下 $B\ge 2n-2$ とする（このとき下で示す $n-a\ge B+3-2n$ から $n-a\ge1$）。$C$ を取り除いた残りの $n-a$ 頂点に帰納法の仮定を用い、さらに Euler の公式（Eulerの公式(平面グラフ)）から得られる $a$ と辺数の関係を組み合わせると、辺数 $B$ が $B\le3n-6-\sqrt{12(n-a)-3}$ および $n-a\ge B+3-2n$ を満たすことがわかり、$a$ を消去して $(B-3n)^2\ge12n-3$、すなわち $B\le3n-\sqrt{12n-3}$ を得る。

認識問題の計算量

与えられた有限グラフがペニーグラフかどうかを判定する問題は NP困難である。

認識問題の出典

この結果は Eades と Whitesides（EW96）による。証明は本記事の範囲を超えるので割愛する。ペニーグラフの認識と対照的に、与えられた点集合の最小距離グラフ（prop-penny-min-distance）は、最近点対を求めるアルゴリズムによって効率よく計算できる。

補足

ペニーグラフはマッチ棒グラフの部分クラスであり（prop-penny-matchstick）、また半径の等しい円板の交差グラフである単位円板グラフの部分クラスでもある。ペニーグラフでは円板の内部が交わることを許さないのに対し、単位円板グラフでは円板が重なる 2 頂点を隣接させる。平面上の円板を（半径が異なってもよいものとして）重ならないように配置したときの接触グラフをコイングラフ（coin graph）といい、Koebe の円充填定理によって、コイングラフはちょうど平面グラフである（PA95）。したがってペニーグラフは、円板の半径をすべて等しくしたコイングラフである。
本記事のペニーグラフの記述は、おおむね Pach と Agarwal の教科書 PA95 第 13 章に従った。