平面グラフ
平面的でないグラフ
K3,3
K5
平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。
平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。極小な非平面的グラフは、K3,3とK5である。
用語
[編集]- 面
- 平面グラフにおいて、辺で囲まれた極小な領域[1]。有界な面を有限面、有界でない面を無限面とよぶ。
- 多角形網(polygonal net)
- 平面を多角形片に分割する平面の繋がっている多角形の周の集合（これら多角形の周の辺は直線である必要はない。）
- 多角形グラフ(polygonal graph)
- その辺が平面でどの多角形も他の多角形を完全に取り囲むことのないような、多角形網を作る平面グラフ
- 多角形グラフ G の双対グラフ G* (dual graph G* of a polygonal graph G)
- その頂点が G の面に、その面が G の頂点に対応する多角形グラフG*のこと。G* の２つの頂点は G の面が一つの境界辺を共有するとき結ばれる。
- 外平面的グラフ
- すべての頂点が無限面のまわりにくるように書ける平面的グラフ[2]。このうち辺集合が極大となっているものは極大外平面的グラフと呼ばれる[3]
性質
[編集]- 平面グラフには、無限面がただ一つある[1]。
- Gが単純グラフで平面的グラフならば、Gは、次数が5以下の頂点を持つ[4]。
- Gが平面的グラフならば、|E(G)|≦3|V(G)|-6。ただし、|V(G)|≧3[5]。
- Gが平面的2部グラフならば、|E(G)|≦2|V(G)|-4。ただし、|V(G)|≧3[4]。
- Gが平面的グラフならば、|E(G)|≦(κ(|V(G)|-2))/(κ-2)が成り立つ。ここでκは内周であり、グラフGの最短の閉路長である。[6]
- 連結平面グラフについて、|V(G)|-|E(G)|+f=2 が成り立つ。ここで|V(G)|は頂点の数、|E(G)|は辺の数、fは面の数である。（オイラーの公式）[1]
- 種数gの曲面S上に描かれた連結グラフGが、Sをf個の領域に分割しているとする。このとき、|V(G)|-|E(G)|+f=2-2gが成り立つ。（オイラーの公式）
- グラフが非平面的であるのは、K3,3またはK5をマイナーとして含むとき、かつそのときに限る。（ワグナーの定理）
- グラフが平面グラフである必要十分条件は、5角形グラフあるいは6角形グラフに縮小しうるようなグラフをもとのグラフが含まないことである（クラトフスキの定理）[7]。別の表現では、グラフが平面的グラフである必要十分条件は、K5またはK3,3と位相同型な部分グラフを含まないことである[8]。
- 平面的グラフの部分グラフは総て平面的グラフである。
外平面的グラフの性質
[編集]- 極大外平面的グラフ⇔切断点がなく無限面以外の面がすべて3角形になるように平面に書ける、が成り立つ[3]
- 極大外平面的グラフGの辺e=xyについて、eが弦（無限遠に面していない辺）⇔G-{x,y}が非連結 が成り立つ[3]
- 3点以上の極大外平面的グラフには次数2の点がある[9]
- Gが2点以上の極大外平面的グラフならば、|E(G)| = 2・|G|-3が成り立つ[9]
着色の性質
[編集]- Gが外平面的グラフならば、χ(G)≦3 が成り立つ[10]
- Gが平面的グラフならば、χ(G)≦4 が成り立つ[10]。これは有名な四色定理である。
- 2-連結3-平面正則グラフは1-因子分解できる[11]。これは四色定理と同値である。
脚注
[編集]参考文献
[編集]- O.オア 著、野口 広(訳) 編『グラフ理論』 5巻〈SMSG新数学双書〉、1970年。
- 榎本彦衛『グラフ学入門』日本評論社、1988年。ISBN 4535601143。 NCID BN0192930X。
- 井上純一「2007年度 グラフ理論講義ノート」『情報科学院・情報科学研究院 雑誌発表論文等』2007年、2021年10月12日閲覧。
