平面グラフ
概要
平面グラフ（Planar graph）とは、辺どうしが共通端点以外で交わらないように平面へ埋め込めるグラフである。平面埋め込みを固定すると補集合の連結成分として面が定まり、連結な平面グラフではEulerの公式 V-E+F=2 が成り立つ。これから単純平面グラフの辺数上界 E≤3V-6 と、二部平面グラフに対する E≤2V-4 が従い、K5とK3,3の非平面性を証明できる。
前提知識: グラフ, 単純グラフ, 次数(グラフ), 閉路, 木
概要
紙の上にグラフを描くとき、辺同士が端点以外の場所で交わってしまうことがある。しかし頂点の配置を工夫すれば、交わりを完全になくして描けるグラフも多い。平面グラフとは、このように辺が互いに交差しない描き方(平面埋め込み)を少なくとも一つ持つグラフのことをいう。平面性は地図の彩色、回路の配線、グラフの可視化など、辺の交差そのものが物理的・視覚的なコストや制約になる場面で本質的な役割を果たす。
平面性は個々の描き方に依存する性質ではなく、抽象グラフGそのものが持つ性質である点に注意する。ある描き方で辺が交差していても、別の描き方で交差なく描き直せるならGは平面グラフである。以下では、特に断らない限りループも多重辺も持たない有限無向単純グラフを扱う。
定義
$G=(V,E)$ をグラフとする。$G$ の 平面埋め込み（planar embedding）とは、各頂点 $v\in V$ に平面上の相異なる点を、各辺 $e=\{u,v\}\in E$ に $u$ と $v$ に対応する点を結ぶ平面上の弧を対応させ、次を満たすものをいう。
- 異なる辺に対応する弧は、共通の端点以外で交わらない。
- 一つの辺に対応する弧は、それ自身と交わらない。
- 各辺に対応する弧の内部は、どの頂点に対応する点も通らない。
$G$ が平面埋め込みを一つでも持つとき、$G$ を 平面グラフ（planar graph）または平面的グラフという。
平面埋め込み、面、Eulerの公式に関する基本事項は Die25 Chapter 4および Wes01 Chapter 6に従う。
「平面グラフである」ことは、抽象グラフ $G$ に対する存在命題(ある平面埋め込みが存在する)である。これに対し、平面埋め込みを一つ具体的に固定して考えるとき、それを平面グラフ図（plane graph）とよんで区別する文献もある。ただしこの用語の使い分けは流儀に依存し、両者を単に「平面グラフ」と総称する教科書も多い。本記事では、埋め込みを一つ固定して面や辺数を論じる箇所では、暗黙にその固定した平面グラフ図を考えているものとする。
平面グラフ図(固定した平面埋め込みを持つグラフ)が与えられたとき、埋め込まれた図形(頂点と辺の和集合)を平面から取り除いた残りの各連結成分を、その埋め込みの 面（face）という。平面上にはちょうど一つの非有界な面が存在し、これを外側の面（outer face）という。ある辺が二つの面の境界に同時に現れるとき、その辺はそれらの面を隔てるという。
直感
平面グラフとは、地図のように辺を交差させずに紙の上へ描き切れるグラフである。
例
完全グラフ $K_4$ は平面グラフである。三頂点を三角形の頂点として配置し、残る一頂点を三角形の内部に置いて、内部の頂点から三角形の各頂点へ辺を引けば、六本の辺はどれも端点以外で交わらない。$K_4$ を「正方形とその対角線」として描くと対角線同士が交差するが、これは一つの描き方が交差を持つというだけのことであり、$K_4$ が平面グラフでないことを意味しない。平面性は、交差しない描き方が(少なくとも一つ)存在するかどうかで判定する。
完全グラフ $K_5$ と完全二部グラフ $K_{3,3}$ は平面グラフではないことが知られている。これらは平面性が破れる最小規模の障害として特に重要であり、次節でEulerの公式から完全に証明する。
性質
$G$ を連結な平面グラフとし、その一つの平面埋め込みにおいて頂点数を $n$、辺数を $m$、面の数を $f$ とする。このとき
$$
n-m+f=2
$$
が成り立つ。
辺数 $m$ に関する帰納法で示す。
基本段: $m=0$ のとき、$G$ が連結であることから頂点数は $n=1$ である。頂点も辺もない一点を平面に置いただけなので、平面には非有界な面が一つあるだけであり $f=1$。よって $n-m+f=1-0+1=2$。
帰納段: $m\geq1$ とし、辺数が $m-1$ 以下の連結平面グラフについて主張が成り立つと仮定する。
(i) $G$ が閉路を持たない場合、$G$ は木であり、次数1の頂点(葉)$v$ が存在する。$v$ に接続する唯一の辺を $e$ とし、$G':=G-v$($v$ と $e$ を取り除いたグラフ)とおくと、$G'$ は連結な平面グラフで頂点数 $n-1$、辺数 $m-1$ である。$e$ は $G$ の橋であり、その両側は同じ面に接していたから、$e$ と $v$ を取り除いても面の個数は変わらず $G'$ の面数も $f$ である。帰納法の仮定より $(n-1)-(m-1)+f=2$、これを整理すると $n-m+f=2$。
(ii) $G$ が閉路を持つ場合、閉路上の辺 $e$ を一つ選ぶ。$e$ は橋ではないので、$G':=G-e$(頂点は残し辺だけ取り除いたグラフ)は連結であり、頂点数 $n$、辺数 $m-1$ の平面グラフである。$e$ を取り除くと、$e$ を隔てとしていた二つの面が一つの面に合わさるので、$G'$ の面数は $f-1$ である。帰納法の仮定より $n-(m-1)+(f-1)=2$、これを整理すると $n-m+f=2$。
いずれの場合も主張が成り立つので、帰納法によりすべての連結平面グラフについて $n-m+f=2$ が成り立つ。
$G$ を頂点数 $n\geq3$ の単純平面グラフとする。このとき
$$
|E(G)|\leq3n-6
$$
が成り立つ。さらに $G$ が二部グラフである場合には
$$
|E(G)|\leq2n-4
$$
が成り立つ。
まず $G$ が連結な場合を示す。$G$ の一つの平面埋め込みを固定し、辺数を $m$、面数を $f$ とする。各面の境界を一周してもとに戻るまでにたどる辺の延べ本数を、その面の次数とよぶ(橋を境界に持つ面では、その橋を往復2回分として数える)。
$G$ が単純かつ $n\geq3$ なので、どの面の次数も3以上である。実際、次数1の面は自己ループを、次数2の面は(橋を挟まない限り)二重辺を要するが、単純グラフにはどちらも存在しない。各辺はちょうど二つの面の境界に現れる(橋の場合は同一の面に2回現れる)ので、全ての面の次数の総和は $2m$ に等しい。したがって
$$
3f\leq\sum_{\text{面}}(\text{次数})=2m,
$$
すなわち $f\leq\dfrac{2m}{3}$ を得る。これをEulerの公式 $n-m+f=2$ に代入すると
$$
2=n-m+f\leq n-m+\frac{2m}{3}=n-\frac{m}{3},
$$
よって $\dfrac{m}{3}\leq n-2$、すなわち $m\leq3n-6$ が従う。
二部の場合は奇閉路を持たないので、各面の境界歩道の長さは偶数であり、単純性と $n\geq3$ から各面の次数は4以上になる。同様に $4f\leq2m$ を得て、Eulerの公式と合わせると $m\leq2n-4$ が従う。
最後に $G$ が非連結な場合を示す。$G$ の各連結成分から一頂点ずつ選び、外側の面を通して交差なく結ぶことで、頂点集合が $V(G)$ に等しい連結な単純平面グラフ $G'\supset G$ を作れる。$G$ が二部グラフの場合は、連結成分ごとに二部の名称を必要に応じて交換してから、異なる側の頂点どうしを結べば、$G'$ も二部グラフにできる。$n\geq3$ なので連結の場合の結果より $|E(G')|\leq3n-6$(二部の場合は $|E(G')|\leq2n-4$)であり、$E(G)\subset E(G')$ だから $|E(G)|\leq|E(G')|\leq3n-6$(二部の場合は $2n-4$)である。
完全グラフ $K_5$ は平面グラフではない。
$K_5$ は頂点数 $n=5$、辺数 $\binom{5}{2}=10$ の単純グラフである。もし $K_5$ が平面グラフならば、単純平面グラフの辺数の上界により
$$
10=|E(K_5)|\leq3\cdot5-6=9
$$
でなければならないが、これは矛盾である。よって $K_5$ は平面グラフでない。
完全二部グラフ $K_{3,3}$ は平面グラフではない。
$K_{3,3}$ は頂点数 $n=6$、辺数 $3\cdot3=9$ の単純二部グラフである。$K_{3,3}$ は二部グラフだから三角形を持たない。もし $K_{3,3}$ が平面グラフならば、単純平面グラフの辺数の上界(二部の場合)により
$$
9=|E(K_{3,3})|\leq2\cdot6-4=8
$$
でなければならないが、これは矛盾である。よって $K_{3,3}$ は平面グラフでない。
有限グラフ $G$ が平面グラフであるための必要十分条件は、$G$ が $K_5$ の細分も $K_{3,3}$ の細分も部分グラフとして持たないことである。
$K_5$・$K_{3,3}$ の非平面性から必要性は理解できるが、この二つの細分を持たなければ平面埋め込みが存在するという十分性には別の議論が必要である。完全な証明は Die25 Chapter 4を参照する。
Wagnerの定理は、有限グラフ $G$ が平面グラフであるための必要十分条件を、$G$ が $K_5$ も $K_{3,3}$ もグラフマイナーとして持たないこと、と述べる。Kuratowskiの定理は細分部分グラフを、Wagnerの定理はマイナーを用いるので条件の字面は異なるが、どちらも平面性を特徴づける。
注意
本記事では外側の面も含めて面を数える流儀(Diestel, Westなど標準的な現代の教科書に共通)を採用した。この流儀のもとでEulerの公式は $n-m+f=2$ の形になる。外側の面を数に入れない流儀を採る文献では、対応する式は $n-m+f=1$ の形で書かれることがあるので、面の個数を扱う際は定義を確認する必要がある。
グラフ $H$ の細分とは、$H$ の辺を次数2の頂点を挟む道で置き換えて得られるグラフである。$G$ が $H$ の細分を部分グラフとして持つならば、$G$ は $H$ をグラフマイナーとして持つが、逆は一般には成り立たない。
平面グラフの頂点数・辺数に対する上の評価は、平面グラフには次数が低い頂点が必ず存在することを保証する。この事実は五色定理・四色定理の証明(いずれも四色定理が正本として担当し、五色定理は要約のみを掲載する)における帰納法の出発点になる。また、平面グラフの各面を頂点、隣接する面を結ぶ辺からなるグラフを考えると双対グラフが得られ、地図の彩色問題は双対グラフの頂点彩色問題に翻訳できる。平面性を保ったまま辺を最大まで付け加えたグラフは極大平面グラフとよばれ、すべての面が三角形になる。また、すべての頂点を外側の面の境界上に配置できる平面グラフは外平面グラフという、より強い制約を持つ部分クラスをなす。与えられたグラフが平面グラフかどうかを効率よく判定する問題は平面性判定として独立に扱われ、線形時間アルゴリズムが知られている。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
