# 平面グラフ ## 定義 平面グラフ(planar graph)とは、辺同士が交差しない形で平面上に描ける単純グラフである。この直感を厳密化する定義は2通りある。第一は平面描画(planar drawing、Definition 12.2.1)で、各頂点を平面上の相異なる点に、各辺を対応する2頂点を結ぶ滑らかな曲線に対応させ、曲線が頂点以外で交わらないようにした描画として定義する。しかしこの定義は「滑らかな曲線」「複数回現れる点」といった点集合位相の概念に依存し、証明に使うには連続数学への回り道が必要になる。第二は平面埋め込み(planar embedding、Definition 12.2.2)で、平面描画に頼らず離散データ型として再帰的に定義する。連結グラフの平面描画は、その曲線群によって平面をいくつかの連結領域(連続な面、continuous face)に分割し、各連続な面の境界は(橋やドングルがなければ)グラフの閉路と対応する。この境界を閉歩道として捉えたものを離散な面(discrete face)と呼び、平面埋め込みは「離散な面の集合」として、基底部(単一頂点、面は長さ0の閉歩道)と2つの構成子(面を分割する/橋を追加する)から再帰的に組み立てられる。グラフが平面描画を持つことと、その各連結成分が平面埋め込みを持つことは同値であるが、この等価性自体は連続数学を要するため証明されない。平面埋め込みには特別な「外側の面」は存在せず、どの面も外側として描き直せる(球面上への埋め込みとして考えると直感的)。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.1–§12.2, §12.2.4) 平面グラフは辺数に強い制約を持つ。v≥3 頂点の連結な平面グラフは e ≤ 3v−6 を満たし(オイラーの公式 v−e+f=2 と、各面の境界長が3以上であること・各辺が面の境界に2回出現することから導かれる)、二部グラフに限れば奇閉路を持たない(第11章)ため各面の境界長が4以上になり e ≤ 2v−4 が成り立つ。この2つの不等式から、完全グラフ K5(v=5, e=10>9)と完全二部グラフ K3,3(v=6, e=9>8)がいずれも平面的でないことが即座に従う。逆方向の特徴づけとして Kuratowski の定理があり、グラフが平面的でないことと、頂点削除・辺削除・隣接2頂点の併合を任意回繰り返して得られるマイナー(minor)として K5 または K3,3 を含むことは同値である。また平面グラフは常に次数5以下の頂点を持ち(辺数の上界と握手補題から)、この事実を使って強帰納法によりすべての平面グラフが5-彩色可能であることが証明できる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.4–§12.6, §12.8) ## 横断的知見 - 平面グラフは第11章の単純グラフの部分クラスとして導入されるが、第11章は単純グラフを「頂点集合と無向辺集合の組」という純粋に代数的・離散的な構造として定義していたのに対し、第12章の平面性はその離散構造に対する連続幾何学的な性質(平面に描けるか)から出発する。この2つの層を橋渡しするために本章は平面描画(連続)と平面埋め込み(離散)という二重定義を用意しており、単純グラフの理論(握手補題・二部グラフの奇閉路禁止・木の定義)がそのまま平面性の議論(辺数上界の証明・K3,3の非平面性の証明)の前提として使い回されている点で、両章は独立ではなく積層した理論体系をなす。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]]) - 第11章の木(閉路を持たない連結グラフ)と第12章のマイナーの関係として、連結グラフGが木でないことと C3(3頂点の閉路)がGのマイナーであることが同値であると本章は指摘する。これは第11章で「木」を閉路の不在という性質で特徴づけていたのに対し、第12章では同じ性質をマイナー(部分グラフより強力な簡約操作)の言葉で再定式化したものであり、木という同一の対象が異なる抽象化レベル(部分グラフ的性質 対 マイナー的性質)から特徴づけられることを示している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.8) ## 未解決の問い - Kuratowski の定理の証明は本書では省略されている。証明の概略(禁止マイナーの一般理論、Wagner の定理との関係)は本書のどの章・どの参考文献で補えるか、本章単独からは分からない。 - 平面グラフの5-彩色定理から4色定理へ強化する証明技法(放電法・帰納法の仮定の強化など)は本章で触れられておらず、未解決のまま残されている。 - 単純グラフ一般に対する彩色数の計算困難性(3-彩色可能性判定がNP完全)と、平面グラフに限定した場合の計算困難性([[グラフ彩色]]が指摘する交差ガジェットによる帰着)の関係を、本章の5-彩色定理(多項式時間で構成可能)と突き合わせて整理する必要がある。 ## 関連 - 概念: [[単純グラフ]] / [[オイラーの公式]] / [[グラフ彩色]] / [[木(グラフ理論)]] / [[帰納法]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 12.